|
Триангуляция с минимальной суммой проведённых хорд
Дано многоугольник в порядке обхода против часовой стрелки и количество точек
Разбить данный многоугольник на треугольники
Используем динамическое програмирование. Нам нужно будет слегка изменить нашу функцию IsCrossS.
Функция имеет вид MinChordTriangulate(p,T).
T - массив результат - размер матрицы count x 3, содержит вершины триангуляции.
Функция разбивает многоугольник на треугольники, но в этом разбиении сумма проведённых хорд минимальна.
Листинг C++
bool IsCrossS(point p1,point p2,point p3,point p4)
{
return SignAreaTriang(p1,p2,p3)*SignAreaTriang(p1,p2,p4) < 0 &&
SignAreaTriang(p3,p4,p1)*SignAreaTriang(p3,p4,p2) < 0;
}
int count_triangle=0;
void path_triangle(polygon p,int K[][100],int i,int j,point T[][3])
{
if(i == j || i == (j-1)%p.n || i == -1 || j == -1)return;
T[count_triangle][0]=p.p[i];
T[count_triangle][1]=p.p[K[i][j]];
T[count_triangle][2]=p.p[j];
++count_triangle;
path_triangle(p,K,i,K[i][j],T);
path_triangle(p,K,K[i][j],j,T);
}
int MinChordTriangulate(polygon p,point T[][3])
{
double D[100][100]={0},M[100][100]={0};
int i,j,k,s,K[100][100]={0};
for(i=0;i<p.n;++i)
for(j=0;j<p.n;++j)
{
D[i][j]=(DiagInPolygon(p.p,p.n,i,j) || i == (j+1)%p.n || i == (j-1)%p.n ? dist(p.p[i],p.p[j]) : 1e9);
K[i][j]=-1;
}
for(i=0;i<p.n-1;++i)
{
M[i][i]=0; M[i][i+1]=D[i][i+1];
}
M[i][i]=0;
for(s=2;s<p.n;++s)
for(i=0;i<p.n-s;++i)
{
j=(i+s)%p.n;
M[i][j]=1e7;
for(k=i+1;k<j;++k)
{
double t=M[i][k]+M[k][j]+D[i][k]+D[k][j]+D[i][j];
if(t<M[i][j])
{
M[i][j]=t;
K[i][j]=k;
}
}
}
path_triangle(p,K,0,p.n-1,T);
return count_triangle;
}
25.06.2007, 18:24
По всем вопросам обращаться: rumterg@gmail.com