Graphics Reference
In-Depth Information
Figure
.
.
Delaunay triangulation
Figure
.
.
Convex hull
he convex hull of a set of points X is the intersection of all convex sets contain-
ing X.
here are several algorithms for computing the convex hull. Since the convex hull
consists of the outer edges of the Delaunay triangulation, we can use an algorithm
for the Voronoi/Delaunay problem and then pick the outer edges. Its computation
thus can be O
(
nlog n
)
.
Nonconvex Hull
A nonconvex hull is a hull that is not a convex hull. his class includes simple shapes
like a star convex or monotone convex hull, but it also includes some space-filling,
snaky objects and some that have disjoint parts. In short, we are interested in a gen-
