What's It Called When...

This is a discussion on What's It Called When... within the General Discussions forums, part of the Community Boards category; ...let's say I have four lines (four sets of two coordinates). Together they make a square. Is there a name ...

  1. #1
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,266

    Question What's It Called When...

    ...let's say I have four lines (four sets of two coordinates). Together they make a square. Is there a name for the process of identifying that a square can be made?

    Obviously I'm thinking of a more complex scenario where I have a CSV of thousands of lines and I want to find all the closed polygons that can be made. I'm sure this has a name though, trying to describe it to Google dosn't work.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    This is basically the same as cycle detection in graph theory. In your case, you have a list of edges, with the two vertices they're connected to as the endpoints of the line. I don't know if there's something better to search for, but that should give you a good start.

  3. #3
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,415
    O_o

    Are you trying to determine if a set of coordinates represent a closed or open polygon?
    Are you trying to determine if a set of coordinates represent a regular or irregular polygon?
    Are you trying to determine if a set of coordinates represent a simple of complex polygon?

    Are the coordinate pairs making a line ordered?
    Are the coordinate pairs making a line winding?
    Are the coordinate pairs making a line striped?

    ;_;

    I don't understand what you are really doing, but it seems like a simpler problem when reinterpreted as a database problem instead of graphing problem.

    Soma

  4. #4
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,266
    I can guarantee* that the input lines represent a closed polygon.
    * Input is based on whatever a user provides, I don't want to seize up if that assumption is found to be false

    I think that this is just a sorting problem: pick a starting line (to my preference, starting from the lowest x and then y) and sort so that the line that begins at the end of the last line is next.

    The end result is a closed path that can easily be represented in SVG format, instead of the individual lines.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    Quote Originally Posted by SMurf View Post
    I think that this is just a sorting problem: pick a starting line (to my preference, starting from the lowest x and then y) and sort so that the line that begins at the end of the last line is next.
    Is it possible for two polygons to share an edge? If so, how will your solution handle that?

  6. #6
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,266
    Luckily, in my case the CSV has three columns: starting coord, ending coord and an index that identifies a polygon. So I already know what lines make up which polygon, I just need the most succinct way of describing them (continuous line).

    Polygons that are touching have two lines with the same coords (order reversed: start -> end and end -> start). I did think this was inefficient but there's no easy way of sorting one line into two arrays with different sort criteria.

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    If you're working in 3D space, then more than two polygons can share an edge, in which case your "reverse the start and end coordinates" trick wont work. But I get the impression that's not the case for you. Still, another potential issue for your "reverse the start coordinates" trick is that you have to reverse all the other line segments for that polygon (if they aren't already), otherwise, the "end" coordinate of one line segment wont jive with the start of another. However, this is all moot if you already have multiple entries for shared line segments, each with their own polygon number/ID. That will make each of them unique, so reversing the start/end is unnecessary. It also supports more than two polygons sharing a line segment.

    That being said, the algo you mentioned in post #4 should more or less do it. It's probably obvious, but it would help to sort by polygon number/ID first, grouping segments for one polygon together. Then, you can order each of those sub-lists. Note, picking the lowest (x, y) coord to start will not matter, just the order of the coords/line segments are drawn in.

  8. #8
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,077
    Quote Originally Posted by SMurf View Post
    ...let's say I have four lines (four sets of two coordinates). Together they make a square. Is there a name for the process of identifying that a square can be made?

    Obviously I'm thinking of a more complex scenario where I have a CSV of thousands of lines and I want to find all the closed polygons that can be made. I'm sure this has a name though, trying to describe it to Google dosn't work.
    I'm a little uncertain what you're looking for as far as identifying all of the closed polygons. Do you mean all of the closed squares, four sided polygons, or just any polygon at all? Is a square still a square if the square is intersected by another square with a different ID? Is it a guarantee that two squares will never overlap? Or are you just simply trying to find out in a list of 1000 sets of four lines, how many sets represent a square shape?
    Sent from my iPadŽ

  9. #9
    Intranasal Heroin User Xterria's Avatar
    Join Date
    Sep 2001
    Location
    Buffalo, NY
    Posts
    1,035
    Damn, SMurf, Sly! The old-breed is still here! Heya fellas!

  10. #10
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    The way in which you have described this problem is a bit vague. However this sounds exactly like the old school polygon fill algorithm. That algorithm sorted points by their lowest Y value and then attempted to go clockwise (pointToCheck.x > currentPoint.x ) or counterclockwise (pointToCheck.x < currentPoint.x) and sorted them into left/right lists accordingly. Then you start from top and connect left[n, n +1, n+2, ...] to right [n, n+1, n+2, ...] and scan convert the lines created by connecting them....while interpolating texture coordinates across the line. You also interpolate texture coordinates as you move down the left/right list so that the starting texture coordinate is correct for each scan converted line. So it is a bilinear interpolation for texels and pixels that creates the final polygon.

    However I can tell you that since you have not defined what type of polygon you are looking for I, too, can guarantee that if your input set has at least 3 points it will create a polygon (IE: a triangle). So the answer to your question is that there is no answer given your criteria. You must narrow down what type of polygons you are looking for (convex, concave, etc.) and if they are regular, irregular, complex or simple.

    Since Soma has already covered all of this I wont repeat him and will say that I agree with his post. More information and judging criteria are needed to solve this problem or the problem is too complex to solve since the solution set is theoretically infinite.
    Last edited by VirtualAce; 06-24-2013 at 11:25 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 05-08-2012, 12:39 AM
  2. destructor not called?
    By waysgoose in forum C++ Programming
    Replies: 3
    Last Post: 04-11-2010, 02:08 AM
  3. Called TlsFree but it's still there!
    By 6tr6tr in forum C++ Programming
    Replies: 8
    Last Post: 04-23-2008, 04:49 AM
  4. Don't know what it's called
    By toonlover in forum Windows Programming
    Replies: 5
    Last Post: 08-02-2006, 10:08 PM
  5. What's it called?
    By SMurf in forum Tech Board
    Replies: 4
    Last Post: 11-28-2003, 06:40 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21