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

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

Триангуляция - Алгоритм Ван Гога

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

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


Листинг C++

bool isTriangCut(point p[],int n,int i,int j,int k)
{
        if(cw(p[i],p[j],p[k]))return 0;
        for(int m=0;m<n;++m)
                if(m != i && m != j && m != k && inTriangPoint(p[i],p[j],p[k],p[m]))
                        return 0;
        return 1;
}
int VanGog(point p[],int n,int T[][3])
{   
        int *l=new int[n];
        int *r=new int[n];
        int i,j,count=0;
        for(i=0;i<n;++i)
        {
                l[i]=(i-1+n)%n;
                r[i]=(i+1+n)%n;
        }
        for(i=r[n-1];count<n-2;i=r[i])
                if(isTriangCut(p,n,l[i],i,r[i]))
                {
                        T[count][0]=l[i];
                        T[count][1]=i;
                        T[count][2]=r[i];
                        l[r[i]]=l[i];
                        r[l[i]]=r[i];
                        ++count;
                }
        return count;
}

22.06.2007, 14:26