Graphics Reference
In-Depth Information
Figure 6.10.
Example showing need for care
in angle counting.
Figure 6.11.
Surrounding test based on angle
counting.
With our choice of inequalities, the point
p
falls into quadrant 2 and the other points
on the vertical or horizontal axis in Figure 6.11 are encoded by the number of the
quadrant to the left or below it, respectively. The actual program that computes the
total angle W that is traced out by
Q
about
p
is quite simple. We start with a value of
0 and then add to W the difference dq in quadrant values from one vertex to the next.
The only problem is that we will again have to worry about moves between diagonal
quadrants (too large of an angle). Therefore, increments will have to be adjusted using
the function adjustDelta below. To compute the adjustment, one also needs a func-
tion that determines when a polygon edge passes to the left or right of
p
at y-level y
0
.
Here are the functions we need:
Assume that
p
= (x
0
,y
0
) and that
e
= [
q
1
,
q
2
] is an oriented edge of
Q
and
q
i
= (x
i
,y
i
).
{Find x-intercept of polygon edge e with horizontal line through y
0
.}
x_intercept (
e
) = x
2
-
(y
2
-
y
0
)
*
((x
1
-
x
2
)/(y
1
-
y
2
))
{d
q
= quadrant (
q
2
)
-
quadrant (
q
1
)}
adjustDelta (d
q
,
e
) =
case
(d
q
)
of
3 : d
q
=
-
1; {we are crossing between quadrants 0 and 3}
-
3 : d
q
= 1; {we are crossing between quadrants 0 and 3}
2,
-
2 : {we are crossing between diagonal quadrants}
if
(x_intercept (
e
)
>
x
0
)
then
d
q
=
-
d
q
;
end
;
The reader can find a C program for computing W in [Weil94]. The main result is then
the following:
