Graphics Reference
In-Depth Information
sists of straight line segments but if the polygon is nonconvex there may be curved
arcs as Figure 5.24(a) shows. There is a close relation between the medial axis and
the Voronoi diagram of an object ([ShAR96]).
The medial axis for a polyhedron has a natural partition into cells. Determining
the medial axis basically reduces to determining its cell decomposition. In two dimen-
sions the cells are called
arcs
and
junctions
. For example, in Figure 5.24(a)
BC
and
CD
are arcs and the points
A
,
B
, and
C
are called junctions. In the nondegenerate
case, junctions are the points where the maximal disk has three or more contact points
with the boundary. The maximal disks at endpoints of arcs that lie in the boundary,
like point
D
, have one contact point with the boundary. In three dimensions the cells
are called
sheets
,
seams
, and
junctions
. The sheets are surface patches. These are
further subdivided into
wing sheets
and
body sheets
. Wing sheets are those with points
in their boundary where the maximal disk makes contact with the boundary at only
one point, such as
ABCD
in Figure 5.24(b). Body sheets are the remaining sheets,
such as
ABEF
. The seams are curves that typically are the intersection of two or more
sheets where the maximal disk has three or more contact points with the boundary.
Junctions are points that are the intersections of three or more sheets. See [BBGS99].
Next, consider discrete objects. We could give the same definitions because all that
we need is a metric which we have. However, there are several natural metrics to
choose from in this case and so it is possible to play around with the definition a bit
and choose a variant which may be more suitable for a particular discrete problem.
We follow [RosK76].
Definition.
Let
X
Õ
U
Õ
Z
n
. The
medial axis
(
MA
) or
skeleton
or
symmetric axis
of
X
with respect to
U
is the set of points whose distances from the complement
U
-
X
are a local maximum, that is, no neighboring point has a greater distance to the com-
plement. The
distance function
for the medial axis is the real-valued function that
assigns to each point of the medial axis its distance to
U
-
X
.
In practice, the “universe”
U
is a rectangle when n = 2 (the pixel case) and a rec-
tangular box when n = 3 (the voxel case). Figure 5.25 shows the medial axes for a 7
¥ 8 discrete rectangle in
Z
2
. In Figure 5.25(a) we used the taxicab metric and in Figure
5.25(b), the max metric. The medial axes are the numbered points with the numbers
giving the distance of the point to the complement.
Figure 5.25.
Discrete medial axes.
