Как я комбинирую сложные полигоны?

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

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

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

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

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

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

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

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