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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

Edit:

Другой подход состоит в том, чтобы сначала разделить каждый многоугольник на набор треугольников, с которыми легче иметь дело. Теорема о двух ушах Гэри Х. Мейстера делает свое дело. Эта страница в 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

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

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

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

Answer 8

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

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

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

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

Answer 9

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

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

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