Нахождение общего контура нескольких полигонов

Question

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

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

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

РЕДАКТИРОВАТЬ: вроде как в выпуклом корпусе, но смотрит наребра не в вершинах, желтая точка, вероятно, находится на продолжении ребер, как я на это смотрю.

EDIT2: Хорошо, мне нужно нарисовать границу заданного размера вокруг многоугольников, но таким образом, что еслидва многоугольника ближе к размеру границы, они будут иметь общую границу, которая является своего рода суммой двух границ без «внутренней» ее части, и эти два многоугольника будут рассматриваться как одна фигура.Поэтому я пытаюсь найти этот красный многоугольник, который будет использоваться для рисования этой границы вокруг него.

Answer 1

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

Соедините новые вершины с расширенными ребрами. Это даст вам полигональную сетку.

Теперь приходит хитрость:

Начало условие:

• Выберите самую верхнюю левую вершину, может быть только одна!

• Укажите ребро с наименьшим уклоном, которое соединяется с вершиной, найденной на 1, и продолжается вправо. Этот край всегда будет по периметру вашего конечного многоугольника.

Итерация:

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

Конечное условие:

• Остановитесь, как только вы снова достигнете верхней левой вершины.

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

Answer 2

Я бы искал "наилучшим образом подходящую ограничивающую рамку", как в http://www.comp.nus.edu.sg/~tancl/Papers/DAS06/39-oyuanbuusu.pdf и, конечно, библиографию этого, рекурсивно.