Graphics Reference
In-Depth Information
order of 2
n
such tests. The overall complexity of the algorithm thus becomes
O
(
n
2
).
The following code fragment implements this triangulation algorithm.
// Triangulate the CCW n-gon specified by the vertices v[]
void Triangulate(Point v[], int n)
{
// Set up previous and next links to effectively form a double-linked vertex list
int prev[MAX_VERTICES], next[MAX_VERTICES];
for(inti=0;i<n;i++) {
prev[i]=i-1;
next[i]=i+1;
}
prev[0]=n-1;
next[n - 1] = 0;
// Start at vertex 0
inti=0;
// Keep removing vertices until just a triangle left
while (n > 3) {
// Test if current vertex, v[i], is an ear
int isEar = 1;
// An ear must be convex (here counterclockwise)
if (TriangleIsCCW(v[prev[i]], v[i], v[next[i]])) {
// Loop over all vertices not part of the tentative ear
int k = next[next[i]];
do {
// If vertex k is inside the ear triangle, then this is not an ear
if (TestPointTriangle(v[k], v[prev[i]], v[i], v[next[i]])) {
isEar = 0;
break;
}
k = next[k];
} while (k != prev[i]);
} else {
// The 'ear' triangle is clockwise so v[i] is not an ear
isEar = 0;
}
// If current vertex v[i] is an ear, delete it and visit the previous vertex
if (isEar) {
// Triangle (v[i], v[prev[i]], v[next[i]]) is an ear
...output triangle here...
