CODEWITHSUNDEEP
algorithmgraphgeometrygraph-theorypolygons
Rahul
Rahul

Reputation: 512

Find all polygon faces given a few diagonals

We have a polygon, given as a list of vertex in counter-clockwise direction starting from the bottom most(points). Some diagonals of the same polygon are given(none of them intersect), as a set of pair of points(diagonals).

We have to find all the faces the polygon is cut into(as a list of vertex for each face).

Example: An example polygon and diagonals

The output would include the following faces:

face1 = [(-68,-36), (-53,-40), (-39,44)]
face2 = [(-53,-40), (-21,37), (-12, 6), (-5,49)]
...

As you might have noticed, the diagonals cut the polygon into monotone polygons with respect to x-axis. If this might help in anyway.

I have been at this problem for several hours now. I can't seem to find any problem even related to it. Any help would be appreciated, thanks.

Edit: The problem can be reduced to finding all simple cycles in a graph(i.e. chordless cycles). I found these similar questions:

Finding polygons within an undirected Graph

Find all chordless cycles in an undirected graph

However, the accepted solution in the second one does not seem to work.

Upvotes: 2

Views: 221

Answers (1)

maraca
maraca

Reputation: 8743

  1. Start with the whole polygon.

  2. Take the first diagonal and divide the polygon into two. One will have the points up to the first point of the diagonal and then all points after (including) the 2nd point of the diagonal. The other will have the first point of the diagonal and all points up to (including) the 2nd point of the diagonal.

  3. Take the next diagonal, decide which polygon will get divided (it can only be one because the diagonals don't cross) and divide it like described in step 2.

  4. Repeat 3. until all diagonals are processed.

Upvotes: 2

Related Questions