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

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

two polygons to find outline

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

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

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

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

6
задан Pax0r 10 July 2011 в 13:15
поделиться