Graphics Reference
In-Depth Information
// 'Delete' vertex v[i] by redirecting next and previous links
// of neighboring verts past it. Decrement vertex count
next[prev[i]] = next[i];
prev[next[i]] = prev[i];
n--;
// Visit the previous vertex next
i = prev[i];
} else {
// Current vertex is not an ear; visit the next vertex
i = next[i];
}
}
}
In some cases it is desirable to support polygons with holes. One way of handling
such polygons is described next.
12.5.1.1 Triangulating Polygons with Holes
To be able to triangulate polygons with holes, a reasonable representation must first
be established. A common representation is as a counterclockwise outer polygon
boundary plus one or more clockwise inner hole boundaries. The drawing on the left
in Figure 12.19 illustrates a polygon with one hole.
Figure 12.19
Handling holes by cutting a zero-width “channel” from the outer (CCW)
boundary to the (CW) hole boundary. (The endpoint vertices of the channel coincide, but
are shown slightly separated to better illustrate the channel formation.)
