Для многоугольника, определенного как последовательность точек (x, y), как определить, сложна она или нет? Сложный многоугольник имеет пересечения с самим собой, как показано:
Есть ли лучшее решение, чем проверка каждой пары, которая имела бы временную сложность O (N 2)?
Существуют методы развертки, которые могут определять это намного быстрее, чем метод грубой силы. Кроме того, их можно использовать для разбиения непростого многоугольника на несколько простых многоугольников.
Подробнее см. в этой статье, в частности, этот code to тест для простого полигона.
См. Bentley Ottmann Algorithm для метода O ((N + I) log N) для развертки. Где N - количество сегментов линии, а я - количество точек пересечения.
Фактически это можно сделать в линейном алгоритме триангуляции Chazelle с использованием времени. Он либо триангулирует многоугольник, либо обнаруживает, что многоугольник не прост.