Graphics Reference
In-Depth Information
if
|d| = 4
then
begin
Split
e
into two edges e
1
and e
2
at a window edge;
d := d
q
(e
1
)
+
d
q
(e
2
)
end
;
return
d;
end
;
Define the
total angle
W by
Â
()
W=
q
eQ
d
e
.
(6.4)
edge
of
One can prove the following:
6.3.1 Theorem.
The polygon
Q
will be disjoint from the window
W
if W is 0 and
surround the window if W=±8n.
Figure 6.9 shows some examples. Figure 6.10 shows the need for the adjustment
to dq in the |dq| = 4 case.
We now return to our original problem about when a point
p
belongs to a
polygon
Q
, Weiler's angle counting algorithm. Weiler basically takes the algorithm
described above, shrinks the window
W
to a point
p
, and adjusts the algorithm accord-
ingly. Now we classify the vertices of
Q
with respect to the quadrant into which they
fall with respect to
p
= (x
0
,y
0
). See Figure 6.11. The quadrants are encoded via inte-
gers 0, 1, 2, or 3. Given a point (x,y), define
(
(
)
)
=
quadrant
x y
,
0
1
2
3
if
x
>
x
and
y
>
y
0
0
=
if
x
£
x
and
y
>
y
0
0
=
if
x
£
x
and
y
£
y
0
0
=
if
x
>
x
and
y
£
y
.
0
0
Figure 6.9.
Window surrounding test based on angle counting.
