Проверка, является ли многоугольник простым или сложным

Question

Для многоугольника, определенного как последовательность (x, y) точек, как я могу определить, является ли он сложным или нет? Сложный многоугольник имеет пересечения с самим собой, как показано:

Есть ли лучшее решение, чем проверка каждой пары, которая имеет временную сложность O (N ² )?

Answer 1

Существуют методы развертки, которые могут определить это намного быстрее, чем метод грубой силы.Кроме того, их можно использовать для разбиения непростого многоугольника на несколько простых многоугольников.

Подробнее см. в этой статье , в частности, этот код для проверки на наличиепростой многоугольник .

Answer 2

См. Алгоритм Бентли-Оттмана , где описывается метод O ((N + I) log N) развертки для этого.Где N - количество отрезков, а I - количество точек пересечения.

Answer 3

На самом деле, это можно сделать за линейное время, используя алгоритм триангуляции Шазеля. Он либо триангулирует многоугольник, либо обнаруживает, что многоугольник не прост.