2

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.

Community
  • 1
  • 1
Rahul
  • 502
  • 7
  • 16
  • Does this help? http://stackoverflow.com/a/16558622/4014959 – PM 2Ring Apr 05 '17 at 12:50
  • @PM2Ring , counting all cycles would not help here, since one face can be part of many cycles. The polygon is a cycle itself. – Rahul Apr 05 '17 at 12:57
  • Fair point. I figured you could find all cycles, and then reduce those to the base cycles. However, you _don't_ have an undirected graph, you have a directed one, which makes the task a lot easier. – PM 2Ring Apr 05 '17 at 13:04
  • Picking this up as a directed graph still gives problems. Take the leftmost diagonal `(-53,-40) -> (-68,-36)`. I have taken the direction as right to left. Now, this diagonal will be a part of the lowermost face, but `face1` would not be a cycle anymore(the polygon is anticlockwise) – Rahul Apr 05 '17 at 13:09

1 Answers1

2

  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.

maraca
  • 8,468
  • 3
  • 23
  • 45
  • Thanks! This worked and was easy to implement. Nice use of the fact that diagonal cuts every face into only two pieces. – Rahul Apr 06 '17 at 04:18
  • @Rahul This fact is the ["Jordan Curve Theorem"](https://en.wikipedia.org/wiki/Jordan_curve_theorem) – MT0 Apr 06 '17 at 11:50