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

Question

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

Answer 1

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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