Разделение многоугольника на выпуклые части

В этом разделе представлен алгоритм, который делит невыпуклый многоугольник на выпуклые:

void convexParts ( CArrRef<Vector2d> & poly, List< ListItem<ShevList> > & res );
Входными данными являются: ссылка на массив вершин многоугольника poly и ссылка на список res, куда будет записываться результат. Каждый элемент результата описывает полученную выпуклую часть и представляет собой список индексов вершин.
Вначале исходный многоугольник разбивается на треугольники. Затем соседние треугольники объединяются, если в результате будет выпуклый многоугольник. Этот алгоритм не всегда даёт минимальное к-во выпуклых частей.

Описание класса Vector2d смотрите в разделе Вектора на плоскости.
Описание шаблона CArrRef находится здесь.
Описание класса ShevList находится здесь.
Описание шаблонов List и ListItem находится здесь.
Исходники алгоритма находятся в файле trian2d.cpp.
В приложении DEMO можно посмотреть результат деления.

Наверх
Hosted by uCoz