Graphics Reference
In-Depth Information
CH(S)
S
Figure 3.15
Convex hull of a concave polygon. A good metaphor for the convex hull is a
large rubber band tightening around the polygonal object.
one or more concave vertices is necessarily concave, but a polygon with only convex
vertices is not always convex (see the next section). The triangle is the only
n
-sided
polygon always guaranteed to be convex. Convex polygons can be seen as a subset
of the concept of
convex point sets
in the plane. A convex point set
S
is a set of points
wherein the line segment between any two points in
S
is also in
S
. Given a point set
S
, the
convex hull
of S, denoted
CH
(
S
), is the smallest convex point set fully containing
S
(Figure 3.15).
CH
(
S
) can also be described as the intersection of all convex point
sets containing
S
.
Related to the convex hull is the
affine hull
,
AH
(
S
). The affine hull is the lowest
dimensional hyperplane that contains all points of
S
. That is, if
S
contains just one
point,
AH
(
S
) is the point; if
S
contains two points,
AH
(
S
) is the line through them; if
S
contains three noncollinear points,
AH
(
S
) is the plane determined by them; and if
S
contains four (or more) non co-planar points,
AH
(
S
) is all of
3
.
In addition to the explicit vertex representation, convex polygons can also be
described as the intersection of a finite number of halfspaces. This representation
is convenient for, for example, point containment tests. For the implicit polygon rep-
resentation, a point lies inside the polygon if it lies inside all halfspaces. Figure 3.16
illustrates a triangle expressed as the intersection of three halfspaces. An alternative
definition for point set convexity is therefore that a point set
S
is convex if and only if
S
is equal to the intersection of all halfspaces that fully contain
S
. For polygons (and
polyhedra), this is an operative definition in the sense that it can be directly used to
implement a convexity test.
Two or more polygons can be joined at their edges to form a
polygon mesh
.Ina
polygon mesh, the
degree
of a vertex corresponds to the number of edges connected
to the vertex. In this text, a mesh will be considered
closed
if all polygons have been
joined such that each edge is part of exactly two polygons.
R
