Graphics Reference
In-Depth Information
sphere containing a set of n points. There are optimal
O
(n) algorithms known for
doing this using Voronoi diagrams. See [PreS85].
6.3
Surrounding Tests
Along with finding intersections, determining whether or not a point belongs to a two-
or three-dimensional region is another common task. This section looks at some
simple tests to answer the question
“Does the point
p
belong to the linear polyhedron
Q
?”
We call them “surrounding” tests because the question could also be thought of as
one that asks whether a point is inside a closed curve or surface (the boundary of the
polyhedron
Q
in this case). Surrounding tests fall naturally into two classes—those
that deal with convex polyhedra and those that handle arbitrary polyhedra. Our dis-
cussion will also separate these two cases, but the reader should note the following:
In either of these two cases it is usually a good idea to use a bounding box
B
for
Q
and first check whether
p
belongs to
B
or not. The reason is that it is very easy to
check if a point belongs to a box. If
p
does not belong to
B
, then it will not belong to
Q
and there would be no need to do a lot of work to test
p
against
Q
.
We begin with tests for a convex polyhedron
Q
.
The Normals Test (Convex Q).
A convex polyhedron
Q
is the intersection of a col-
lection of halfplanes associated to the faces of
Q
. Suppose that we are given a normal
vector
n
i
and vertex
q
i
for the ith face, so that the ith halfplane can be expressed in
the form
{
(
)
}
qq q
-
•
n
≥
0
.
i
i
The point
p
will belong to
Q
if and only if
(
)
pq n
-
•
≥
0
i
i
for all i. As a trivial example, suppose that
Q
is the unit square [0,1] ¥ [0,1]. It has
four faces. Let
=
()
=-
(
)
(
)
=
()
n
01
,,
n
10
, ,
n
=-
0
,
1
,
n
10
, ,
0
1
2
3
=
(
)
=
(
)
=
(
)
=
(
)
q
00
,,
q
40
,,
q
44
,,
and
q
04
,.
0
1
2
3
See Figure 6.5. If
p
= (x,y), then
(
)
pq n
pq n
pq n
pq n
-
•
≥
0
means that y
means that x
means that y
≥
0
,
0
0
(
)
-
•
≥
0
£
4
,
1
1
(
)
-
•
≥
0
£
4
,
and
2
2
(
)
-
•
≥
0
means that x
≥
0
.
3
3
