CODEWITHSUNDEEP
algorithmgeometrycomputational-geometry
user3510049
user3510049

Reputation: 23

Computational Geometry (Polygons)

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

Answers (2)

user3146587
user3146587

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

Timothy Shields
Timothy Shields

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

Related Questions