Имеется векторный полигон в программе (в виде команд его рисования). Задача - расширить этот полигон во все стороны на заданное расстояние. То есть, получить его контур или окаёмку с учётом возможных внутренних коллизий. Интересует, собственно, алгоритм сего действа. Желательно, не особо ресурсоёмкий. Либо просто литература, где про это можно почитать. Самое, что интересное: обработка самопересечений в замкнутых областях (как внутренняя дырка в букве "я" - заполнилась целиком). закругления в углах. Как сделать без закруглений более-менее понятно (провести параллельные линии на заданном расстоянии). Или концы отрезков с помощью безье соединить?.. Чёрным обозначена исходная область, а синим - итоговая (для различной толщины контура). В крайнем случае, можно отталкиваться и от готового растра исходного полигона.
Ответ
Векторный случай Если предположить, что вы уже перешли к векторному формату, то: рассматриваете последовательно ребра полигона в одном направлении (например, против часовой стрелки). Это важно, т.к. повлияет на ориентацию направляющих векторов ребер полигона. Для каждого ребра вычисляете нормаль (это нормализованный вектор, перпендикулярный направляющему вектору ребра). В вашем случае также следует проследить, чтобы нормаль была направлена "от" полигона, а не "внутрь" него. умножаете каждую нормаль на коэффициент "расширения" k. прибавляете нормаль к начальной (u) и к конечной (v) вершинам ребра (вершины рассматриваем как векторы, исходящие из начала координат). Получаем "расширенные" вершины u' и v'. Эти вершины определяют начало и конец "расширенного" ребра. Кроме того, в итоге на каждую вершину полигона будет получено по две (в общем случае неколлиниарных) "расширенных" вершины u' и u'' (они будут вычислены для смежных ребер с общей вершиной u). Их можно использовать, чтобы сделать "закругление" (наиболее очевидный способ: строить промежуточные вершины поворотом u' к u'' малым угловым шагом). Нужно еще выявлять ситуации самопересечений и обрабатывать их. Боюсь соврать, но по-моему тут надо смотреть знаки смешанных произведений нормалей ребер и вектора (0,0,1). При выбранном направлении обхода полигона знак этого произведения должен меняться только для "вогнутых" пар ребер (образующих "невыпуклости" полигона). Кажется так.. Почитать можно что-то по аналитической геометрии и векторной арифметике. UPD: Как вариант можете еще глянуть эту книгу: Steven M. LaValle. Planning Algorithms. В ней охвачен широчайший спектр вопросов, в т.ч. и работа с полигонами. Растровый случай Думаю, практически в любом случае есть смысл заняться преобразованием в векторное представление. Для определения границ можно попробовать использовать алгоритм пересечения полигона отрезком, паралелльным какой-либо оси координат + читать цвета пикселей. Еще один вариант - как-то попробовать модифицировать алгоритм заливки полигона. Тут уже менее очевидно, надо думать или искать готовый векторизатор:)
Комментариев нет:
Отправить комментарий