Graphics Reference
In-Depth Information
Figure 17.6.
Box intersections with sweeping.
the plane, we need to find the intersection of the rectangles R(z) with the query rec-
tangle [a,b] ¥ [c,d]. Of course, we are only interested in zs in the interval [e,f]. For a
very large negative z the set R(z) will be empty. Then as z increases one needs to add
and delete rectangles from R(z). We sort the z-values of the bottom and top face of
all the boxes to rapidly find the z-values where R(z) changes and use interval trees for
the sets R(z).
The sweeping technique can also be used to find intersections of rectangles in the
plane.
17.5
Convex Set Problems
This section considers some related problems dealing with convex sets. We first
describe a simple algorithm for testing whether two convex linear polyhedra inter-
sect. We then apply this result to the well-known problem of determining the vertices
of a convex hull. The results are based on the fact that disjoint convex sets can be
separated by a hyperplane (see [Vale64] or [Rock70]) and that there is a straight-
forward algorithm for determining whether such a hyperplane exists or not.
Notation.
Let
p
and
n
be a point and nonzero vector of
R
n
, respectively. Let
H
(
p
,
n
)
and i
H
(
p
,
n
) denote the halfplane and open halfplane, respectively, defined by
(
)
=
{
(
)
≥
0
Hpn
,
q n• p q
-
and
(
)
=
{
(
)
>
0.
i
Hpn
,
q n• p q
-
Let
P
(
p
,
n
) denote the hyperplane
(
)
=
(
)
«-
(
)
=
{
(
)
=
}
Ppn
,
Hpn
,
Hp n
,
q n• p q
-
0
.
Definition.
Two subsets
X
and
Y
of
R
n
are said to be
linearly separable
if there is a
hyperplane
P
(
p
,
n
) so that
X
Õ
H
(
p
,-
n
) and
Y
Õ
H
(
p
,
n
). The hyperplane is said to
sep-
