34 bestTriangulation=NULL;
41 delete[] bestTriangulation;
42 bestTriangulation=NULL;
50 if(vertices.size()==3)
53 triangles[0].idx[0]=0;
54 triangles[0].idx[1]=1;
55 triangles[0].idx[2]=2;
58 else if(vertices.size()==4)
66 tIndex[0][0].idx[0]=0;
67 tIndex[0][0].idx[1]=1;
68 tIndex[0][0].idx[2]=2;
69 tIndex[0][1].idx[0]=2;
70 tIndex[0][1].idx[1]=3;
71 tIndex[0][1].idx[2]=0;
73 tIndex[1][0].idx[0]=0;
74 tIndex[1][0].idx[1]=1;
75 tIndex[1][0].idx[2]=3;
76 tIndex[1][1].idx[0]=3;
77 tIndex[1][1].idx[1]=1;
78 tIndex[1][1].idx[2]=2;
84 p1=vertices[tIndex[i][j].idx[1]]-vertices[tIndex[i][j].idx[0]];
85 p2=vertices[tIndex[i][j].idx[2]]-vertices[tIndex[i][j].idx[0]];
86 CrossProduct(p1,p2,n);
87 area[i] += Real( Length(n) );
91 triangles[0]=tIndex[1][0];
92 triangles[1]=tIndex[1][1];
96 triangles[0]=tIndex[0][0];
97 triangles[1]=tIndex[0][1];
101 if(bestTriangulation)
102 delete[] bestTriangulation;
105 bestTriangulation=NULL;
107 size_t eCount=vertices.size();
108 bestTriangulation=
new Real[eCount*eCount];
109 midPoint=
new int[eCount*eCount];
110 for(
size_t i=0;i<eCount*eCount;i++)
111 bestTriangulation[i]=-1;
112 memset(midPoint,-1,
sizeof(
int)*eCount*eCount);
113 GetArea(0,1,vertices);
115 GetTriangulation(0,1,vertices,triangles);
117 template <
class Real>
120 if(bestTriangulation)
121 delete[] bestTriangulation;
124 bestTriangulation=NULL;
126 int eCount=vertices.size();
127 bestTriangulation=
new double[eCount*eCount];
128 midPoint=
new int[eCount*eCount];
129 for(
int i=0;i<eCount*eCount;i++)
130 bestTriangulation[i]=-1;
131 memset(midPoint,-1,
sizeof(
int)*eCount*eCount);
132 return GetArea(0,1,vertices);
138 size_t eCount=vertices.size();
144 ii=midPoint[i*eCount+j];
147 tIndex.idx[0] = int( i );
148 tIndex.idx[1] = int( j );
149 tIndex.idx[2] = int( ii );
150 triangles.push_back(tIndex);
151 GetTriangulation(i,ii,vertices,triangles);
152 GetTriangulation(ii,j,vertices,triangles);
160 size_t eCount=vertices.size();
161 size_t idx=i*eCount+j;
167 bestTriangulation[idx]=0;
170 if(midPoint[idx]!=-1)
171 return bestTriangulation[idx];
173 for(
size_t r=j+1;r<ii;r++)
176 size_t idx1=i*eCount+rr,idx2=rr*eCount+j;
178 p1=vertices[i]-vertices[rr];
179 p2=vertices[j]-vertices[rr];
180 CrossProduct(p1,p2,p);
181 temp = Real( Length(p) );
182 if(bestTriangulation[idx1]>=0)
184 temp+=bestTriangulation[idx1];
187 if(bestTriangulation[idx2]>0)
188 temp+=bestTriangulation[idx2];
190 temp+=GetArea(rr,j,vertices);
194 if(bestTriangulation[idx2]>=0)
195 temp+=bestTriangulation[idx2];
197 temp+=GetArea(rr,j,vertices);
200 temp+=GetArea(i,rr,vertices);
209 bestTriangulation[idx]=a;