0
$\begingroup$

enter image description here

On a 2D plane there is a set of vertices V and segments S. Each segment has 2 vertices, and each vertex knows segments that use it. That creates a kind of a graph.

I would like to find all polygons as is depicted above. A polygon P is a set of n segments.

I tried BFS for each vertex with first cycle detection and duplicates removing. It unfortunately doesn't work for specific cases, for example it won't find P5 on picture below.

enter image description here

$\endgroup$
  • $\begingroup$ You should represent the segments by directed half-edges as in a DCEL, so that each region is represented by the half-edges on its boundary. Then an appropriate search over the edges will find all enclosed polygonal regions. $\endgroup$ – Discrete lizard May 10 at 8:49
  • $\begingroup$ Your problem is a simpler version of cs.stackexchange.com/questions/90880/… , but the answer there does not go into the details on how to perform the final search. $\endgroup$ – Discrete lizard May 10 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.