Find all non-overlapping polygons in a list of edges/vertices

Question

I have a list of edges and a list of vertices. Each edge references two vertices, each vertex maintains a list of edges.

I want to find all non-overlapping polygons produced from this graph.

An example would be

0,0) (4,0) (4,2) (4,4) (2,4) (2,2) (4,2) (6,2) (6,6) (0,6) (0,0)

This path should describe each unique edge with collisions on some verticies. In the actual graph, the vertices are distinct. The two polygons I would need from this set are (0,0) (4,0) (4,2) (2,2) (2,4) (4,4) (4,2) (6,2) (6,6) (0,6) and (2,2) (2,4) (4,4) (4,2)

I assume from your description that the edges/vertices are associated with points in space? — templatetypedef, Aug 29 '11 at 21:47
When you say "non-overlapping polygons," what happens if you have edges that describe two overlapping polygons? Do you report that as one polygon consisting of their intersection, or do you report neither of them? — templatetypedef, Aug 29 '11 at 21:53
The path forming the polygon should choose the tightest closed loop. This prevents the polygons from overlapping. — Josh C., Aug 29 '11 at 21:56
Oh, and I do not care about holes. Disjoined polygons that overlap are permissible. — Josh C., Aug 29 '11 at 21:58
What do you do when the edges don't describe polygons at all, such as if no two edges intersect? — templatetypedef, Aug 29 '11 at 21:59
Can the polygon be self-intersecting? For example: (0, 0) -> (1, 1) -> (1, 0) -> (0, 1) -> (0, 0)? — Ted Hopp, Aug 29 '11 at 22:14
No, in preprocessing the intersecting edges would be broken down into non-intersecting edges. — Josh C., Aug 29 '11 at 22:17

score 3 · Answer 1 · edited May 23 '17 at 11:50

3

What you are describing is the problem of finding all minimal circuits in a graph. (That it happens to have a geometric model is irrelevant, I think.) There's a paper here for finding a minimal circuit. You can build on that by removing the edges of the minimal circuit and running the algorithm again.

The problem is also discussed in this thread for the case of directed graphs. You can turn your graph into a directed graph by making a copy of each edge with the vertices reversed and then treating it as directed. The only problem will be that each polygon will be found twice, once in each traversal direction. You can clean that up with a post-process step or perhaps by some clever bookkeeping while the algorithm is running.

edited May 23 '17 at 11:50

Community

1
1

answered Aug 29 '11 at 22:23

Ted Hopp

232,168
48
399
521

I think that the positions do indeed matter, since you could have a cycle that is positioned in space so that each edge crosses the other in a way where the resulting polygon is not actually made of the circuit edges, but out of a greater number of edges based on where the edges in that circuit intersect. This might also have trouble with non-planar graphs. I may be wrong about this (perhaps I misread your answer), but for these reasons I don't think this solution works. – templatetypedef Aug 29 '11 at 22:26
@Ted Hopp, I may be mistaken, but I don't think that is quite the right algorithm. Let's say I had a set of edges: (0,0) (4,0) (4,2) (4,4) (2,4) (2,2) (6,2) (6,6) (6,0) (0,0). In this case, the greater polygon is self-intersecting. I don't want a self intersecting polygon. Instead, I want two polygons: one described by(0,0) (4,0) (4,2) (2,2) (2,4) (4,4) (4,2) (2,6) (6,6) (6,0), and the other being (2,2) (2,4) (4,4) (4,2). In this case, I would need to resuse all of the edges in the smallest circuit. – Josh C. Aug 29 '11 at 22:34
@Josh C: Then you need to do a first pass to detect all line segment intersections. Once you've done that and split up all the edges into non-overlapping edges, you can do cycle finding to get all the polygons out of it. – Mikola Aug 29 '11 at 22:39
I have already set up my graph with non-overlapping edges. It looks like this problem is commonly called "Polygon Detection". Sometimes the hardest part in finding the algorithm is knowing the name of the problem. – Josh C. Aug 29 '11 at 22:46
@templatetypedef - In the comments to the original question, Josh said that intersecting edges would be removed in preprocessing. Wouldn't that preclude the scenario you describe? Josh - the first of the two solutions in your comment include an edge between (4,2) and (2,2), but there is no such edge in your input. – Ted Hopp Aug 29 '11 at 22:52
@Ted Hopp, I'm sorry if I mis-described the situation. If I have an edge spanning from (4,0) to (4,4) but other edges intersect it, I then break the edge down into sub edges where each intersection is a vertex linking the sub edges. – Josh C. Aug 29 '11 at 22:59
In that case, the algorithms I linked to should work. They find _minimal_ circuits. – Ted Hopp Aug 29 '11 at 23:00
@Mikola, in further investigation of minimum cycles, I think I would generate an invalid polygon for the points described above. The smallest cycle would be (2,2) (2,4) (4,4) (4,2). The next smallest cycle would be (0,0) (4,0) (4,2) (2,6) (6,6) (6,0). This would create a polygon that would inclue the previous one. I need something that paths around the previous polygon. – Josh C. Aug 29 '11 at 23:02
@Ted Hopp, Ok, I'm a bit confused. I assume the minimum circuit is one with the fewest number of edges. Won't that create an overlapping polygon in my scenario? – Josh C. Aug 29 '11 at 23:05
@Josh - back to the example in your comment: wouldn't the edge (6,6)(6,0) be split because of the vertex at (6,2)? Likewise, wouldn't the edge (6,0)(0,0) be split at (4,0)? Then the minimum polygons would be (4,2)(2,2)(2,4),(4,4) and (4,0)(4,2)(6,2)(6,0). The edges (0,0)(4,0) and (6,2)(6,6) are not really part of any regular polygon. (If you allow degenerate polygons, then wouldn't the solution be just each edge by itself as a degenerate polygon?) – Ted Hopp Aug 30 '11 at 00:36
@Ted Hopp, I messed up... I am reposting the list of points (0,0) (4,0) (4,2) (4,4) (2,4) (2,2) (4,2) (6,2) (6,6) (0,6) (0,0) This path should describe each unique edge with collisions on some verticies. In the actual graph, the vertices are distinct. The two polygons I would need from this set are (0,0) (4,0) (4,2) (2,2) (2,4) (4,4) (4,2) (6,2) (6,6) (0,6) and (2,2) (2,4) (4,4) (4,2) – Josh C. Aug 30 '11 at 00:54
I see. That is rather different than what I understood from your earlier description. I'll have to think about that. I suggest that you edit your original question and add this as an example, so others can see the problem without reading all these comments. – Ted Hopp Aug 30 '11 at 02:31
Given this more elaborate discussion, this answer does seem promising. Out of curiosity, wouldn't you need to find *all* cycles, not just the smallest? – templatetypedef Aug 30 '11 at 03:05
Yes, I need all non-overlapping polygons. – Josh C. Aug 30 '11 at 03:44

Josh C. · Accepted Answer · 2011-08-30T15:03:35.377

Well, I was thinking...

The only vertices of particular interest are ones with more than two edges. To find all vertices with more than two edges is O(n). Then to find the tighest closed loop is the same as finding the smallest theta between a given an edge and another edge at a given vertex (if the vertices are ccw, this is the smallest angle clockwise from the current edge). In order to find all tightest closed loops, I need to check all edge ccw edge pairs at a vertex where the edge count is greater than 2. This is the initialization of the trace. From that point on, the trace will always pick the next edge with the smallest theta clockwise. Once the path is returned, I move to the next edge pair in the root vertex, and path again. Once all pairs are checked, I move to the next vertex with an edge count greater than 2. Now, if I can only determine if I am falling into a known loop and not trace. Maybe if the first two vertices of a path occur in the same order in an already known polygon...

How does that sound? I know it's no djikstra, but it will work, and hopefully faster than finding all cycles brute force.

Find all non-overlapping polygons in a list of edges/vertices

2 Answers2

Linked