#algorithm #geometry #polygon
Вопрос:
Я ищу алгоритм, который генерирует линии (или полилинии, если необходимо) , соединяющие полигоны.
Входные данные: содержит N полигонов с координатами их вершин. Полигоны не пересекаются, но могут находиться внутри друг друга.
Вывод: Вершины для N-1 линий (или полилиний, если необходимо), соединяющих
Правила:
- Соединительные линии не могут пересекаться друг с другом
- Соединительные линии не могут пересекать многоугольники
- Соединительные линии могут касаться линий/вершин полигонов
Пример изображения:
Есть какие-нибудь предложения?
Ответ №1:
Позаимствовав трюк из учебника Крускала, в то время как есть еще один многоугольник,
- Найдите ближайшую пару полигонов (в общем случае многоугольник на самом деле может быть набором полигонов с соединительными мостами);
- Соедините их в ближайших точках отрезком прямой линии.
Выбрав самое близкое соединение, мы можем гарантировать, что его внутренняя часть не касается того, чего не должна касаться (в противном случае пересечение приведет к более короткому соединению).