Graphics Reference
In-Depth Information
Figure 6.8.
Surrounding test based on parity.
indicate a few details in the planar case. In this case the ray from
p
is usually chosen
to be parallel to the x-axis with direction vector (0,1). To avoid the problem case where
a vertex of
Q
actually lies on the ray, one pretends that all such points lie slightly above
the ray. Next, one can easily tell if the ray intersects an edge. If the y-coordinates of
the endpoints have the same signs, then the ray does not intersect. If they have oppo-
site signs, then there will be an intersection if both x-coordinates are to the right of
the x-coordinate of
p
. If the x-coordinates straddle the point, then one must compute
the intersection and check on which side of
p
it lies.
The Angle Counting Test.
This test, which applies only to planar polygons
Q
, is
based on the topological concept of winding number that counts how many times one
object “winds around” another. See Section 9.3 in [AgoM05]. The test, due to Weiler
([Weil94]), was motivated by the solution to a slightly different problem, which we
shall describe first.
Let
W
be a rectangular “window” in the plane. Assume that
Q
also lies in the plane
and that the boundaries of
W
and
Q
are disjoint. The question we want to answer is
whether the two spaces are disjoint. Just because their boundaries are disjoint does
not mean that the spaces are since one could contain the other. We present an algo-
rithm ([Roge98]) that involves counting certain angles. In the topological case we
would have to sum up infinitesimal angles, but here we do not have to be that accu-
rate. Let us number the “octants” around
W
as shown below:
321
4 0
567
For a point
p
, let c(
p
) denote the number of the octant into which it falls. For each
oriented polygon edge
e
, define the recursive angle increment function dq(
e
) by
real function d
q
(edge e)
begin
real
d;
Assume that
e
= [
p
,
q
];
d := c(
q
)
-
c(
p
);
if
d
>
4
then
d := d
-
8;
if
d
<-
4
then
d := d
+
8;
