Printable View
...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. :o
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.
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
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.
Is it possible for two polygons to share an edge? If so, how will your solution handle that?Quote:
Originally Posted by SMurf
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.
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.
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?Quote:
Originally Posted by SMurf
Damn, SMurf, Sly! The old-breed is still here! Heya fellas!
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.