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

Question

У меня есть объект System.Windows.Shapes.Polygon, макет которого полностью определяется рядом точек. Мне нужно определить, является ли этот многоугольник самопересекающимся; т. е. если какая-либо из сторон многоугольника пересекает любую из сторон в точке, не являющейся вершиной. Есть ли простой/быстрый способ вычислить это?

Answer 1

• Легкие, медленный, низкий объем памяти: сравнить каждый сегмент от всех остальных и проверить наличие пересечений. Сложность O (n).

• Немного быстрее, область памяти средней памяти (модифицированная версия выше): храните края в пространственных «ведрах», а затем выполняйте выше алгоритм на основе каждого ковша. Сложность O (n/m) для m ведра (при условии равномерного распределения).

• Быстрого & высокой память след: использовать пространственную хэш-функцию для разделения края в ведро. Проверьте наличие столкновений. Сложность O (n).

• Быстрый & низкая память след: использовать алгоритм развертки строки, такие, как один описанный here (или here). Сложность O (п журнал п)

Последняя моя любимая, как это имеет хорошую скорость - баланс памяти, особенно Bentley-Ottmann algorithm. Реализация также не слишком сложна.

Answer 2

Проверьте, не пересекаются ли какие-либо пары непересекающихся сегментов линии.

Answer 3

Для полноты я добавлю еще один алгоритм для этого обсуждения.

Предполагая, что читатель знает о выровненных по горизонтали ограничительных прямоугольниках (это Google, если нет). Быстро найти пары ребер, столкнувшихся с AABB, можно с помощью «Sweep and Prune Algorithm». (погугли это). Затем на этих парах вызывается процедура пересечения.

Преимущество в том, что вы можете даже пересечь не прямолинейный край (круги и сплайны), а подход является более общим, хотя и почти таким же эффективным.