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

Question

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

Answer 1

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

Answer 2

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

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

тогда я буду действовать как алгоритм сканирования Грэма , но с еще одним ограничением.

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

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

Примечание:

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

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

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

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

: * Замечания 1030 *

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

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

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

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

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

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

надеюсь, мне ясно

Answer 3

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

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

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