Как объединить сложные полигоны?

Ответ 1

Это очень хороший вопрос. Я реализовал тот же алгоритм на С# некоторое время назад. Алгоритм строит общий контур двух многоугольников (т.е. Создает объединение без отверстий). Вот оно.

Шаг 1. Создайте граф, описывающий многоугольники.

Вход: первый многоугольник (n точек), второй многоугольник (m точек). Выход: график. Вершина - точка многоугольника точки пересечения.

Мы должны найти пересечения. Перейдем через все стороны многоугольника в обоих многоугольниках [O (n * m)] и найдем любые пересечения.

• Если пересечение не найдено, просто добавьте вершины и соедините их к краю.

• Если какие-либо пересечения найдены, отсортируйте их по длине до их начальной точки, добавьте все вершины (начало, конец и пересечения) и соединить их (уже в отсортированный порядок) к краю.

Шаг 2. Проверьте построенный граф

Если бы мы не нашли точек пересечения при построении графика, мы имеем одно из следующих условий:

• Polygon1 содержит polygon2 - return polygon1
• Polygon2 содержит polygon1 - return polygon2
• Polygon1 и polygon2 не пересекаются. Возвращать polygon1 и polygon2.

Шаг 3. Найдите левую нижнюю вершину.

Найдите минимальные координаты x и y (minx, miny). Затем найдите минимальное расстояние между (minx, miny) и точками многоугольника. Этот пункт будет левым нижним.

Шаг 4. Построить общий контур.

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

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

Я вычисляю два вектора: vector1 для текущего края и vector2 для каждого следующего невидимого края (как показано на рисунке).

Для векторов вычисляю:

• Скалярный продукт (точечный продукт). Он возвращает значение, связанное с углом между векторами.
• Векторный продукт (кросс-продукт). Он возвращает новый вектор. Если z-координата этого вектор положителен, скалярное произведение дает прямой угол в   против часовой стрелки. Else (z-координата отрицательная), я   рассчитать угол между векторами как 360 - угол от скалярного   продукт.

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

Я добавляю в список результатов каждую переданную вершину. Список результатов - это многоугольник объединения.

Примечания

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

Ответ 2

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

Ответ 3

Это сложная, но хорошо понятая тема, которая часто идет под названием "регуляризованные булевы операции на многоугольниках". Вы можете посмотреть на этот ответ MathOverflow, который включает цифру ниже (из библиотека обрезки Алана Мурты), с розовым соединением OP объединяются:

Ответ 4

Хороший вопрос! Я никогда не делал этого раньше, но сейчас я взломаю его.

Сначала: вам нужно знать, где эти две формы перекрываются. Чтобы сделать это, вы можете посмотреть каждое ребро в многоугольнике A и увидеть, где оно пересекается, и ребро в многоугольнике B. В этом примере должны быть две точки пересечения.

Затем: Сделайте форму соединения. Вы можете взять все вершины в и B, а также точки пересечения, а затем исключить вершины, которые содержатся в окончательной форме. Чтобы найти эти точки, похоже, вы могли бы просто найти любую вершину из A, которая находится внутри B, и любой текст из B, который находится внутри A.

Ответ 5

Попробуйте gpc.

Ответ 6

Решение, которое я видел с использованием деревьев BSP, описано здесь здесь.

В основном, он описывает пересечение в терминах объединения ребер многоугольника A, которые находятся внутри многоугольника B (включая частичные ребра и рассчитаны с использованием Дерево BSP). Затем вы можете определить A  /  B как ~ (~ A  /\ ~ B), где ~ обозначает обратное обмотку многоугольника,/обозначает объединение и /\ обозначает пересечение.

Ответ 7

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

Ответ 8

Мне нужно было решить эту же проблему сегодня и нашел решение с этим lib: http://www.cs.man.ac.uk/~toby/alan/software/.

В нем много языковых реализаций список здесь, включая Java, Obj-C, С#, Lua, python и т.д.