Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Триангуляция с количеством треугольников - (n-2)

Дано многоугольник в порядке обхода против часовой стрелки и количество точек
Разбить данный многоугольник на треугольники

Используем стнадартный рекурсивный алгоритм.
Основная идея его состоит в отрезании многоугольника на две части по хорде если это не треугольник.
Функция имеет вид triangulate(p,T).
T - массив результат - размер матрицы count x 3, содержит вершины триангуляции.
Функция рабивает многоугольник на n-2 треугольника.


Листинг C++

int count_triang=0;
void triangulate(polygon &p,point T[][3])
{
        if(p.n <= 3)
        {
                for(int i=0;i<p.n;++i)
                        T[count_triang][i]=p.p[i];
                ++count_triang;
                return;
        }
        int i,j;
        bool end=0;
        for(i=0;i<p.n && !end;++i)
                for(j=0;j<p.n && !end;++j)
                        if(DiagInPolygon(p,i,j)){ end=1;i=i-1; break;}
        polygon p1,p2;
        CutPolygonD(p,i,j,p1,p2);
        triangulate(p1,T);
        triangulate(p2,T);
}

23.06.2007, 14:46