У меня есть объект System.Windows.Shapes.Polygon, макет которого полностью определяется рядом точек. Мне нужно определить, является ли этот многоугольник самопересекающимся; т.е. если какая-либо из сторон многоугольника пересекает любую из сторон в точке, не являющейся вершиной. Есть ли простой/быстрый способ вычислить это?
Проверьте, является ли многоугольник самопересекающимся
Ответ 1
-
Легкий, медленный, низкий объем памяти: сравнивайте каждый сегмент со всеми остальными и проверяйте пересечения. Сложность O (n 2).
-
Немного быстрее, средний размер памяти (модифицированная версия выше): храните края в пространственных "ковшиках", а затем выполняйте выше алгоритм на основе каждого байта. Сложность O (n 2/m) для m ведер (при условии равномерного распределения).
-
Быстрая и высокая площадь памяти: используйте пространственную хеш-функцию для разделения краев на ведра. Проверьте наличие столкновений. Сложность O (n).
-
Быстрое и низкое пространство памяти: используйте алгоритм развертки, такой как описанный здесь (или здесь). Сложность O (n log n)
Последний мой любимый, поскольку он имеет хорошую скорость - баланс памяти, особенно алгоритм Бентли-Оттмана. Реализация также не слишком сложна.
Ответ 2
Проверьте, не пересекается ли какая-либо пара сегментов несмежных.
Ответ 3
Для полноты я добавлю еще один алгоритм для этого обсуждения.
Предполагая, что читатель знает о выровненных по горизонтали ограничивающих прямоугольниках (Google это, если нет). Быстро найти пары ребер, у которых есть AABB, может быть очень эффективным, используя "Sweep and Prune Algorithm". (погугли это). Затем на этих парах вызываются подпрограммы пересечения.
Преимущество в том, что вы можете даже пересечь не прямолинейный край (круги и сплайны), а подход более общий, хотя и почти аналогично эффективный.