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