Объединение "смежных полилиний, содержащих кривые Безье"

Question

Конкретный пример: возьмите карту европейских стран и список указателей на «Пути, которые представляют страны в Европейском союзе», и выведите один «Путь, представляющий Европейский союз».

напримересли у меня есть три входных пути: красный, зеленый и синий.

1. Красный состоит только из отрезков прямых линий
2. Зеленый состоит из отрезков и линий Безье
3. Синий состоит только из Безье

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

ДОПОЛНИТЕЛЬНО, мне нужночтобы справиться с некоторой погрешностью во входных данных - см. изображение ниже, есть некоторые очень маленькие «промежутки» между входными формами.На изображении нижняя цифра (красная) - это желаемый результат.

Это может легко пойти не так, и я потратим недели на то, чтобы я не сработал.Я пытаюсь найти относительно простой подход, который может быть «достаточно хорошим», но в настоящее время я застрял на:

1. Как вы вообще начинаете объединяться с Безье?
2. Какой умный способ справиться с «пробелами» / допустимым пределом ошибок - я уверен, что есть что-то хитрое, если просто округлить мои координаты с плавающей точкой - но я не вижу этого: (

Наконец ... целевой платформой является iPhone - так что у меня есть доступ ко всем Apple Quartz / QuartzCore / CoreAnimation / и т. Д., Которые предоставляют некоторые служебные методы - но обратите внимание: даже официальный от AppleРеализация основ, таких как «Пересекает ли путь A путь B?», во многих случаях довольно сильно нарушена / неверна, поэтому она не очень надежна: (.

Answer 1

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

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

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

Извините, больше ничего не могу набрать на этом телефоне :-(

Answer 2

ИДЕЯ того, как этого добиться (возможно) - но я тоже не знаю, как это сделать:

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

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

Чтобы сделать это, я подумал, может быть:

1. Возьмите выпуклые оболочки каждой из форм
2. любые отрезки воболочки , которые перекрывают другие оболочки ... являются "внутренними"
3. ... считывание обратно в точки в исходной форме, которые создали каждый сегмент линии корпуса (ИЛИ были аннулированы этим сегментом)... эти точки являются «внутренними по отношению к союзу»

?