Как делить самопересекающийся многоугольник на простые многоугольники?

Question

У меня есть один многоугольник, определяемый списком точек. Этот многоугольник может быть самопересекающимся с более чем одной точкой пересечения. Я нашел все точки грубой силой. (Метод развертки Bentley-Ottmann еще не реализован). Например, http://i.imgur.com/3F3LbfB.png У меня есть 4 вершины и край 1-2 пересекаются с краем 4-0 (точка A), а край 2-3 пересекается с ребром 4-0 (точка B). Я вижу простой многоугольник 0-1-A-0 и остаюсь, этот остаток также делит на два многоугольника: A-B-2-A и B-3-4-B Как общий алгорифм?

Answer 1

Простым подходом является вычисление planar straight-line graph (PSLG) путем разбиения сегментов многоугольника в точках пересечения (Bentley - Ottmann естественно распространяется, чтобы сделать это одновременно), а затем перечислить его конечные грани. Последнее можно выполнить, подготовив комбинаторное вложение, а затем traversing it as described in this previous answer of mine.