Простой алгоритм пересечения полигонов

Question

Я ищу очень простой алгоритм для вычисления пересечения / отсечения полигонов. То есть с учетом полигонов P, QЯ хочу найти многоугольник T который содержится в P И в Qи я желаю T быть максимальным среди всех возможных многоугольников.

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

Но для меня действительно важно, чтобы алгоритм был простым (более дешевое тестирование) и предпочтительно коротким (меньше кода).

редактировать: пожалуйста, обратите внимание, я хочу получить многоугольник, который представляет пересечение. Мне не нужен только логический ответ на вопрос о том, пересекаются ли два полигона.

Answer 1

Я понимаю, что оригинальный постер искал простое решение, но, к сожалению, простого решения не существует.

Тем не менее, я недавно создал бесплатную библиотеку отсечения с открытым исходным кодом (написанную на Delphi, C++ и C#), которая обрезает все виды полигонов (включая самопересекающиеся). Эта библиотека довольно проста в использовании: http://sourceforge.net/projects/polyclipping/.

Answer 2

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

Одна из реализаций обрезки полигонов, которую вы можете использовать для поиска в вашей любимой поисковой системе, - это Weiler-Atherton. статья в википедии о Вейлере-Атертоне

Алан Мурта имеет полную реализацию полигонального клипсатора GPC.

Редактировать:

Другой подход состоит в том, чтобы сначала разделить каждый многоугольник на набор треугольников, с которыми легче иметь дело. Теорема о двух ушах Гэри Х. Мейстера делает свое дело. Эта страница в McGill хорошо объясняет подразделение треугольника.

Answer 3

Если вы используете C++ и не хотите создавать алгоритм самостоятельно, вы можете использовать Boost.Geometry. Он использует адаптированную версию алгоритма Вейлера-Атертона, упомянутого выше.

Answer 4

Вы не дали нам свое представление о многоугольнике. Поэтому я выбираю (больше похоже на предложение) один для вас:)

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

Теперь, учитывая два полигона в этом представлении, вы можете вычислить пересечение как:

Вычислить пересечение больших выпуклых многоугольников, чтобы сформировать большой многоугольник пересечения. Затем "вычтите" пересечения всех меньших из обоих, чтобы получить список вычтенных многоугольников.

Вы получаете новый многоугольник, следуя тому же представлению.

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

Кажется, что это должно сработать, но я не задумывался о том, насколько это правильно / сложность времени / пространства.

Answer 5

Вот подход, основанный на триангуляции, который довольно прост в реализации и может быть выполнен для работы в O (N²).

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

1. Сначала триангулируйте каждый многоугольник.

2. Сравните все треугольники из P попарно со всеми треугольниками из Q, чтобы обнаружить пересечения. Любая пара пересекающихся треугольников может быть разбита на меньшие треугольники, каждый из которых находится в P, в Q или на пересечении. (Все, что вы использовали в шаге 1, можно использовать повторно, чтобы помочь с этим.) Сохраняйте только те треугольники, которые находятся на пересечении.

3. Вычислите соседей каждого треугольника, сравнив их попарно, и построите граф смежности. Этот граф будет содержать один связанный подграф для каждого многоугольника на пересечении P и Q.

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

Answer 6

Вот простой и глупый подход: при вводе дискретизируйте свои полигоны в растровое изображение. Пересечь, И растровые изображения вместе. Чтобы получить выходные полигоны, отследите неровные границы растрового изображения и сгладьте неровности, используя алгоритм аппроксимации полигонов. (Я не помню, дает ли эта ссылка наиболее подходящие алгоритмы, это всего лишь первое попадание в Google. Вы можете воспользоваться одним из инструментов для преобразования растровых изображений в векторные представления. Может быть, вы могли бы вызвать их без повторной реализации алгоритма?)

Я думаю, что самой сложной частью будет выявление границ.

Кстати, еще в начале 90-х я столкнулся с чем-то вроде этой проблемы на работе. Я приглушил это: я придумал (совершенно другой) алгоритм, который будет работать с координатами действительного числа, но, казалось, натолкнулся на совершенно не поддающееся обработке множество вырожденных случаев перед лицом реалий с плавающей запятой (и шумного ввода), Возможно, с помощью Интернета я бы сделал лучше!

Answer 7

Если многоугольники не выровнены, их необходимо выровнять. Я бы сделал это, найдя центр многоугольника (среднее по X, среднее по Y), затем постепенно поворачивая многоугольник с помощью преобразования матрицы, проецируя точки на одну из осей и используя угол минимального стандартного отклонения для выравнивания форм (вы может также использовать главные компоненты). Для поиска пересечения простой алгоритм будет определять сетку точек. Для каждой точки ведите подсчет точек внутри одного многоугольника, другого многоугольника или обоих (объединение) (для этого есть простые и быстрые алгоритмы, например http://wiki.unity3d.com/index.php?title=PolyContainsPoint). Подсчитайте точки polygon1 и polygon2, разделите на количество точек в polygon1 или Polygon2, и вы получите приблизительную (в зависимости от выборки сетки) оценку доли перекрывающихся полигонов. Площадь пересечения задается точками объединения.

Answer 8

То, как я работал над той же проблемой

1. разбить многоугольник на отрезки
2. найти пересекающуюся линию, используя IntervalTrees или же LineSweepAlgo
3. найти закрытый путь, используя GrahamScanAlgo найти замкнутый путь со смежными вершинами
4. Перекрестная ссылка 3. с DinicAlgo растворить их

примечание: мой сценарий был другим, учитывая, что полигоны имели общую вершину. Но надеюсь, это поможет

Answer 9

Если вас не волнует предсказуемость времени выполнения, вы можете попробовать сначала разделить полигоны на объединение выпуклых многоугольников, а затем попарно вычислить пересечение между суб-полигонами.

Это даст вам набор выпуклых многоугольников, объединение которых будет точным пересечением ваших начальных многоугольников.

Answer 10

У меня нет очень простого решения, но вот основные шаги для реального алгоритма:

1. Создайте собственный двойной связанный список для вершин и ребер многоугольника. С помощью std::list не будет делать, потому что вы должны поменять местами следующий и предыдущий указатели / смещения для специальной операции на узлах. Это единственный способ иметь простой код, и это даст хорошую производительность.
2. Найдите точки пересечения, сравнивая каждую пару ребер. Обратите внимание, что сравнение каждой пары ребер даст время O(N²), но впоследствии будет легко улучшить алгоритм до O(N·logN). Для некоторой пары ребер (скажем, a → b и c → d) точка пересечения определяется с помощью параметра (от 0 до 1) на ребре a→b, который задается как tₐ=d₀/(d₀-d₁) где d₀ равно (ca)×(ba), а d₁ равно (da)×(ba). × является двумерным перекрестным произведением, таким как p×q=pₓ·qᵧ-pᵧ·qₓ. Найдя tₐ, нахождение точки пересечения использует ее в качестве параметра линейной интерполяции на отрезке a→b: P=a+tₐ(ba)
3. Разделите каждое ребро, добавив вершины (и узлы в вашем связанном списке), где сегменты пересекаются.
4. Затем вы должны пересечь узлы в точках пересечения. Это операция, для которой вам нужно было создать собственный двойной связанный список. Вы должны поменять местами пару следующих указателей (и соответственно обновитьпредыдущие указатели).

Тогда у вас есть необработанный результат алгоритма разрешения пересечения многоугольников. Как правило, вы хотите выбрать какой-либо регион в соответствии с номером обмотки каждого региона. Найдите номер обмотки многоугольника для объяснения этого.

Если вы хотите сделать алгоритм O(N·logN) из этого алгоритма O(N²), вы должны сделать то же самое, за исключением того, что вы делаете это внутри алгоритма линейной развертки. Ищите алгоритм Бентли Оттмана. Внутренний алгоритм будет таким же, с той лишь разницей, что у вас будет уменьшенное количество ребер для сравнения внутри цикла.

Answer 11

Это может быть огромным приближением в зависимости от ваших полигонов, но вот один:

• Вычислить центр масс для каждого многоугольника.
• Вычислите минимальное или максимальное или среднее расстояние от каждой точки многоугольника до центра масс.
• Если C1C2 (где C1/2 - центр первого / второго многоугольника) >= D1 + D2 (где D1/2 - расстояние, которое вы вычислили для первого / второго многоугольника), тогда эти два многоугольника "пересекаются".

Хотя это должно быть очень эффективным, поскольку любое преобразование в многоугольник применяется точно так же к центру масс, а расстояния между центрами узлов могут быть вычислены только один раз.