Graphics Reference
In-Depth Information
6.3.2 Theorem.
If
p
does not lie on the boundary of
Q
, then it is outside polygon
Q
if W is 0 and inside if W=±4. If
p
lies on the boundary, then the algorithm will
return 0 or ±4 depending on whether the interior of
Q
was to the left or right of
p
with respect to the orientation of ∂
Q
.
Weiler's angle counting algorithm extends to polygons
Q
with holes if one knows
which is the outside boundary. The point
p
must be inside the outside boundary and
outside the hole boundaries. There is also an extension to nonsimple polygons, such
as polygons that intersect themselves.
Finally, we would to point the reader to the paper by Haines ([Hain94]) that
analyzes a variety of “point-in-planar-polygon” tests with some detailed conclu-
sions about which algorithm to use in which situation. Both the time and the
amount of extra storage that is needed must be taken into account. Choosing effi-
cient implementations of the algorithms is obviously also important. Haines has code
for a parity algorithm, two versions of algorithms using normals, and an algorithm
based on grids. A reader who is looking for the most efficient algorithm really
needs to read Haines' paper, but a rough summary of his recommendations is the
following:
No preprocessing or extra storage:
use the parity test
Some preprocessing and extra storage:
convex polygon:
few sides:
use a normals type test on triangle fans
many sides:
use the wedge test
arbitrary polygon:
few sides: use a normals type test on triangle fans
many sides: use the parity test
Lots of preprocessing capability and extra storage:
use a test based on grids (see
[Hain94])
6.4
Orientation-Related Facts
When is a polygon
P
convex? The answer to this question is clear if
P
is defined as
the intersection of halfplanes, but the more typical way that polygons are presented
is via their boundary, that is, by a sequence of points. Therefore, the “real” question
is “When does a sequence of points (in a plane) define a convex polygon?” One test is
based on whether segments keep “turning” in one direction.
Definition.
Two linearly independent vectors
u
and
v
in
R
2
are said to determine a
left turn
if the ordered basis (
u
,
v
) determines the standard orientation. Otherwise, we
say that they determine a
right turn
. If the vectors are linearly dependent, then we will
say that they determine
both
a left and right turn.
The notion of left or right turning vectors leads to the following intuitively obvious
convexity test:
