Reputation: 23
If we are given a set S of segments , Can we design an algorithm that will test if the segments in set S can form a polygon , i am not interested if they are intersecting polygons or not , i just want to know on what criteria can i test ,
any suggestions
Upvotes: 0
Views: 177
Reputation: 4330
For the record, here is a possibly more direct solution (the first answer is constructing the dual graph which may be less obvious).
Construct a graph where each (distinct) endpoint from the given segments is a vertex and each given line segment is an edge. Do a depth-first-search traversal of this graph to find cycles. These cycles are candidate polygons.
Upvotes: 0
Reputation: 79631
Construct a graph data structure in which nodes represent segments in your set S. Connect segment A and segment B with an edge if A and B intersect. Do a traversal of the graph to determine if there are any cycles. Each cycle corresponds to a candidate polygon.
Upvotes: 2