Контур произвольного полигона

#2d #алгоритм #графика

Имеется векторный полигон в программе (в виде команд его рисования).
Задача - расширить этот полигон во все стороны на заданное расстояние. То есть, получить
его контур или окаёмку с учётом возможных внутренних коллизий. Интересует, собственно,
алгоритм сего действа. Желательно, не особо ресурсоёмкий. Либо просто литература, где
про это можно почитать.
Самое, что интересное:

обработка самопересечений в замкнутых областях (как внутренняя дырка в букве "я"
- заполнилась целиком).
закругления в углах. Как сделать без закруглений более-менее понятно (провести параллельные
линии на заданном расстоянии). Или концы отрезков с помощью безье соединить?..


Чёрным обозначена исходная область, а синим - итоговая (для различной толщины контура).
В крайнем случае, можно отталкиваться и от готового растра исходного полигона.    

Ответы

Ответ 1

Векторный случай

Если предположить, что вы уже перешли к векторному формату, то:

рассматриваете последовательно ребра полигона в одном направлении (например, против
часовой стрелки). Это важно, т.к. повлияет на ориентацию направляющих векторов ребер
полигона.
Для каждого ребра вычисляете нормаль (это нормализованный вектор, перпендикулярный
направляющему вектору ребра). В вашем случае также следует проследить, чтобы нормаль
была направлена "от" полигона, а не "внутрь" него.
умножаете каждую нормаль на коэффициент "расширения" k.
прибавляете нормаль к начальной (u) и к конечной (v) вершинам ребра (вершины рассматриваем
как векторы, исходящие из начала координат). Получаем "расширенные" вершины u' и v'.
Эти вершины определяют начало и конец "расширенного" ребра.
Кроме того, в итоге на каждую вершину полигона будет получено по две (в общем случае
неколлиниарных) "расширенных" вершины u' и u'' (они будут вычислены для смежных ребер
с общей вершиной u). Их можно использовать, чтобы сделать "закругление" (наиболее очевидный
способ: строить промежуточные вершины поворотом u' к u'' малым угловым шагом).
Нужно еще выявлять ситуации самопересечений и обрабатывать их. Боюсь соврать, но
по-моему тут надо смотреть знаки смешанных произведений нормалей ребер и вектора (0,0,1).
При выбранном направлении обхода полигона знак этого произведения должен меняться только
для "вогнутых" пар ребер (образующих "невыпуклости" полигона). Кажется так..

Почитать можно что-то по аналитической геометрии и векторной арифметике.
UPD: Как вариант можете еще глянуть эту книгу: Steven M. LaValle. Planning Algorithms.
В ней охвачен широчайший спектр вопросов, в т.ч. и работа с полигонами.
Растровый случай
Думаю, практически в любом случае есть смысл заняться преобразованием в векторное
представление. Для определения границ можно попробовать использовать алгоритм пересечения
полигона отрезком, паралелльным какой-либо оси координат + читать цвета пикселей. Еще
один вариант - как-то попробовать модифицировать алгоритм заливки полигона. Тут уже
менее очевидно, надо думать или искать готовый векторизатор:)