0. Пояснение: Я не уверен, предоставляются ли зеленые соединения между выпуклыми многоугольниками как часть ввода или программа должна определить соответствующие зеленые соединения как кратчайшие пути между самими многоугольниками. Я только что заметил, что в вашем изображении отсутствует зеленый край в верхнем правом углу (это будет частью внешней границы, если это разрешено).
1. Решение: всегда выбирайте следующее ребро. Если ваш ввод определяет, какие зеленые линии разрешены, а какие нет, то вы просто пересекаете границу внешнего компонента, находя одну начальную точку (например, беря угол многоугольника с наименьшим x- координаты), упорядочивая зеленые ребра, которые отходят от многоугольника этой текущей точки, в направлении против часовой стрелки и выбирая ребро сразу после текущей точки в порядке CCW . Теперь возьмите другой конец этого ребра в качестве «текущей точки» и повторите тот же метод, чтобы найти следующее ребро ... пока вы не вернетесь к первому многоугольнику.
2. Решение: Начните с выпуклой оболочки. Если вы разрешите все возможные зеленые линии, они вам не нужны. Выпуклая оболочка всех ребер многоугольника является первым приближением к вашему решению (подробности поиска - см. Далее): выпуклая оболочка содержит реальные ребра многоугольника (давайте подумаем о них как о «черных»: они являются частью вашего окончательного решения , уже в правильном порядке) и ребра, соединяющие многоугольники (давайте подумаем о них как о красном: их нужно заменить зелеными ребрами и, возможно, частями других многоугольников).
Завершение второго решения: разделяй и властвуй: Теперь нам нужно заменить каждое красное ребро комбинацией зеленого и черного ребер. Мы просто фокусируемся на одной красной линии за раз (и применяем один и тот же метод для каждой красной линии, которая у нас может быть).
Таким образом, у нас есть одна красная линия, которая содержит два многоугольника с одной зеленой линией (самая короткая связь между ними) - четыре ребра этих двух линий определяют четырехугольник. Если ни один из других углов многоугольника не входит в этот четырехугольник, все готово: замените красный край зеленым и все черные края на многоугольниках, чтобы добраться до точек соединения.
Но если вы найдете многоугольник в четырехугольнике, выберите из них ближайший к красному краю. Переместите красный край к этой точке - так, чтобы новая точка разрезала красный край на два красных края. Эти два новых красных края заменяют один старый красный край: примените этот метод рекурсивно к обоим из них. Их соответствующие четырехугольники намного меньше и содержат меньше ребер многоугольника.
Поскольку вы продолжаете применять этот метод «разделяй и властвуй», в конечном итоге у вас не останется красных краев (потому что вы теряете один красный край каждый раз, когда находите пустой четырехугольник).
Выпуклая оболочка: Это сложная проблема в n измерениях, но простая в двух измерениях: если вы будете искать в сети или просматривать SO, вы наверняка найдете лучшее решение, чем я могу себе представить, но вот что приходит на ум (опять же: разделяй и властвуй): найдите одну точку A с максимальной координатой x и одну точку B с минимальной координатой x, соедините их двумя направленными «синими» ребрами: A-> B и B -> A. Разделите ваши точки на два набора: те, которые находятся на правой стороне края A-> B, и те, что на левой стороне (которая действительно является правой стороной от B-> A). Мы неоднократно заменяем каждый синий край, пока не найдем выпуклый корпус:
Возьмите один синий край A-> B и посмотрите на точки с правой стороны. Если их нет, то этот синий край действительно черный (часть вашего решения). В противном случае, возьмите точку C, расположенную дальше всего справа от синего края, и замените край A-> B на два синих края A-> C и C-> B. Разделите точки, которые были с правой стороны от A-> B, на точки, которые находятся с правой стороны от A-> C, на те, которые находятся на правой стороне от C-> B, и те, которые не являются ни игнорируются). Повторяйте, пока все синие края не будут заменены.