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



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

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

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

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

779   9  

9 ответов:

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

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

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

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

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

Edit:

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

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

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

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

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

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

вы получаете новый полигон, следующий за тем же представлением.

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

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

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

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

  1. во-первых, определить каждого полигона.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Ничего не найдено.

Добавить ответ:
Отменить.