The polygons arising from vertex removal in a grid hierarchy have a special property: they are star-shaped. Star-shaped polygons are less general than simple polygons which can be retriangulated in linear time [Chaz91].
The simple cutting-off algorithm used in this implementation to
retriangulate the polygons is shown in Algorithm 7.3. Note that for
any polygon 
with 
vertices there must be at least one angle of less
than or equal to 
degrees. Fig. 7.11 illustrates the
retriangulation process.
Figure: Retriangulation of a star-shaped polygon. Starting from an arbitrary
point, the angle enclosed by the following two edges is examined. Point 
is
selected because angle 
is less than degrees. The process
is repeated with the new polygon consisting of 
points until only three
points (the final triangle) are left.
This algorithm has the advantageous property that the ``old'' triangles to be referenced from the newly generated ones are easily determined: If the removed point (i.e. the star center) lies inside the newly generated triangle, this triangle has to reference all ``old'' triangles of the previous triangulation. If this is not the case, the new triangle simply references those two triangles which have the cut-off point in common, or in other words, the two triangles which have one edge in common with the two cut-off polygon edges. But if an interior triangle is generated, it references all the triangles which have boundary edges lying between the two polygon points joined by the cut edge. Fig. 7.12 tries to illustrate this fact.
Figure: Generating references from the newly
generated to the removed triangles. A boundary scan for the new triangle 13
yields references to triangles 8, 1, 2 and 3. Since the star center point lies
in triangle 14, this new triangle references all triangles contained in the
initial star triangulation.
