Первый алгоритм делит невыпуклый многоугольник на выпуклые части: bool convexParts ( CCArrRef<Vector2d> & vert, Suite<nat> & cntr, Suite<nat> & index );На вход поступает массив вершин невыпуклого многоугольника (vert), а на выходе получаем количество вершин (cntr) и индексы (index) выпуклых частей. Этот алгоритм не всегда даёт минимальное к-во выпуклых частей. Второй алгоритм делит многоугольник с дырками на многоугольники без дырок: bool splitPolygon ( CCArrRef<nat> & cntr, CCArrRef<Vector2d> & vert, Suite<nat> & cntr2, Suite<nat> & index );Здесь cntr - это количества вершин многоугольников, vert - общий массив всех вершин, cntr2 и index - количества вершин и индексы полученных многоугольников. Внешний многоугольник должен иметь обход вершин против часовой стрелки, а внутренние - по часовой. Порядок перечисления многоугольников произвольный. В обоих алгоритмах вначале исходный многоугольник разбивается на треугольники, а затем соседние треугольники объединяются, пока не буден получен результат. Описание класса Vector2d смотрите в разделе Вектора на плоскости.
|