Graphics Reference
In-Depth Information
To be able to triangulate the polygon, the outer and inner boundaries must be
merged into a single continuous chain of edges. This can be done by cutting a zero-
width“channel”from the outer boundary to each inner boundary. Cutting this channel
consists of breaking both the inner and outer boundary loops at a vertex each and
then connecting the two vertices with two coincident edges in opposite directions
such that the outer boundary and the hole boundary form a single counterclockwise
continuous polygon boundary. Figure 12.19 shows how a hole is effectively resolved
by this procedure. Multiple holes are handled by repeating the cutting procedure for
each hole.
Sometimes the boundaries are given with arbitrary orientation and it is not known
which boundary is the outer boundary and which are the hole boundaries. In these
cases, the outer boundary can be assumed to be the one defining the polygon with
the largest area and the remaining boundaries correspond to the holes. Once the
outer boundary has been determined, a counterclockwise ordering for it, and clock-
wise ordering for the holes, is easily enforced by reversing the vertex order, if
necessary.
Several triangulation programs are publicly available on the Internet. The perhaps
best, most robust, program is due to Jonathan Shewchuk. Its implementation is
discussed in [Shewchuk96b]. A good discussion of robust triangulation is also given
in [Held01].
12.5.2
Convex Decomposition of Polygons
As shown in Chapter 5, an intersection test between a ray and a quadrilateral is no
more expensive than against a triangle. Allowing collision geometry to consist not
just of triangles but quadrilaterals or even arbitrary convex polygons can therefore
provide a potential speedup at the cost of some extra complexity maintaining poly-
gons of different order.
Although triangulation of a simple polygon is quite straightforward, its decomposi-
tion into a set of convex polygons is more complicated, much more so for an algorithm
for computing an optimal decomposition. In fact, in order to achieve a decomposi-
tion into the smallest number of convex pieces additional vertices —
Steiner points
—
may have to be introduced. Figure 12.20 shows two polygons that when partitioned
using diagonals alone result in at best five and three convex pieces, but which can
decompose into four and two pieces, respectively, by introducing Steiner points.
An algorithm that performs a minimal convex decomposition of a simple polygon
(without the use of Steiner points) is presented in [Keil02]. The time and space
complexity of this algorithm is
O
(
n
O
(
n
3
), where
n
is the number of
vertices of which
r
are concave vertices. An implementation by the authors is available
on the Internet. Pseudocode is also given in [Schneider02].
A simpler algorithm for convex decomposition is due to Hertel and Mehlhorn
[Hertel83]. Starting with a triangulation of the simple polygon, the Hertel-Mehlhorn
algorithm considers each diagonal one at a time. If the diagonal can be removed
r
2
min(
r
2
,
n
))
+
=
