Алгоритм объединения кругов в многоугольник

Каков наилучший способ объединения перекрывающихся кругов в многоугольники?

Мне присваивается список центральных точек окружностей с фиксированным диаметром.

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

Это кажется довольно распространенной проблемой (системы ГИС, векторы и т.д.). Это можно сделать через API Карт Google, но я ищу фактический алгоритм.

Я попытался решить эту проблему, вычислив точки вокруг каждого круга.

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

Это дает мне правильный список точек в желаемом многоугольнике.

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

Надеюсь, у вас есть идеи, чтобы либо сделать это решение, либо другим алгоритмом, который достигнет желаемого результата.

Спасибо заранее!

Ответ 1

Вы можете использовать оценку так:

Сначала укажите круги, принадлежащие к одной группе перекрывающихся кругов. Очевидно, что два круга перекрываются, если абсолютное расстояние их центров меньше их объединенных радиусов. Для каждого круга сохраните круги, которые он использует в файле hashmap/dictionary. (Вы можете распространить это на целые группы кругов с помощью алгоритма union-find или непересекающихся наборов, но это действительно не нужно.)
При создании точек, принадлежащих одному кругу, запоминайте левого и правого соседей каждой точки. Вы получаете это бесплатно, просто сохраняя их в упорядоченном массиве.
Удалите "внутренние" точки, т.е. те, которые ближе одного радиуса к любому из центров окружностей, пересекающих первый круг.
Отметьте соседей тем внутренним точкам, которые не удаляли "свободные концы" кругов.
Соедините точки, которые не были удалены, включая свободные концы, с их исходными левыми и правыми соседями.
Для каждой свободной конечной точки найдите ближайший свободный конец другого круга в той же группе и соедините их.

Вот изображение, иллюстрирующее подход.

Красные точки - это "внутренние" точки, которые удалены.
Синие точки "свободные концы" , будучи соседями по "внутренним" точкам; каждый "свободный конец" имеет еще один "свободный конец" другого круга, который меньше, чем два "дистанции на расстоянии".
Зеленые точки легко могут быть подключены к соседям (включая "свободные концы" ) по порядку, в котором они были расположены вокруг круга.

Вы можете дополнительно уменьшить количество возможных комбинаций, разделив левый и правый свободные концы и используя тот факт, что каждый оставшийся свободный конец одного круга должен быть подключен к правому свободному концу другого круга. Для n кругов в группе, которая оставляет только (n-1)! способы соединения этих кругов независимо от количества точек на круг.

И даже это можно уменьшить, если вы рассматриваете только те круги в группе, которые фактически пересекают круг со свободным концом (просто сохраните их в hashmap/dictionary). Поэтому, если у вас есть круги n, которые в среднем пересекаются с k другими кругами, тогда возможны только n*k возможные комбинации.

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

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

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

Ответ 2

Здесь представлен эскиз алгоритма O (n log n) -time.

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

_{Если кто-либо из Google читает это, обратите внимание, что я не смотрел соответствующий код.}