Триангуляция - Алгоритм Ван Гога
Дано многоугольник в порядке обхода против часовой стрелки и количество точек
Разбить данный многоугольник на треугольники
Используем алгоритм Ван Гога (метод отрезания ушей).
Основная идея его состоит в последовательном отрезании треугольников.
Функция имеет вид 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
По всем вопросам обращаться: rumterg@gmail.com