Многоугольник без отверстий

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

Ответ 1

Удалите все вершины многоугольников, которые лежат внутри другого полигона: http://paulbourke.net/geometry/insidepoly/
Выберите начальную точку, которая, как гарантируется, будет в объединенном многоугольнике (один из крайностей будет работать)
Проведите по краям многоугольника против часовой стрелки. Это точки вашего союза. Проследите, пока вы не нажмете пересечение (обратите внимание, что ребро может пересекаться с более чем одним краем другого многоугольника).
Найдите первое пересечение (если их больше одного). Это точка в вашем Союзе.
Вернемся к шагу 3 с другим полигоном. Следующая точка должна быть точкой, которая делает наибольший угол с предыдущим краем.

Ответ 2

Вы можете действовать следующим образом:

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

тогда я бы продолжил, как алгоритм сканирования graham, но с еще одним ограничением.

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

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

Примечание:

это похоже на нахождение выпуклой оболочки ваших точек.

Например, алгоритм graham scan поможет вам найти выпуклую оболочку множества точек в O (N * ln (N)), где N - количество точек.

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

Надеюсь, что это поможет.

Замечания:

(*) из википедии:

Первый шаг в этом алгоритме - найти точку с наименьшим у-координаты. Если самая низкая у-координата существует в более чем одной точке в множестве точка с наименьшей координатой x из кандидаты должны быть выбраны. Назовите эту точку P. Этот шаг принимает O (n), где n - количество рассматриваемых точек.

Затем набор точек должен быть отсортирован в порядке возрастания угол их и точку P составляют с осью x. Любой универсальный для этого подходит алгоритм сортировки, например, heapsort (который O (n log n)). Чтобы ускорить расчеты, это не необходимо вычислить фактический угол, который эти точки составляют с помощью ось х; вместо этого достаточно вычислить косинус этого угла: он является монотонно убывающей функцией в рассматриваемой области (от 0 до 180 градусов, из-за первого шага) и может быть рассчитанный с помощью простой арифметики.

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

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

и вы снимаете ограничение угла наклона менее 180 °

надеюсь, что я свободен

Ответ 3

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

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

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