Graphics Reference
In-Depth Information
the interior and exterior swap roles. This is convenient in many situations. For
example, imagine a polygon-shaped hole in a piece of metal. The interior of this
polygon can (by suitable ordering of the vertices) be made to be the rest of the
metal sheet. A light ray, trying to get from one side of the metal sheet to the other,
is occluded exactly if it meets the interior of this polygon.
P
3
P
1
Q
P
2
We can test whether a point in the plane is in the interior or exterior of a poly-
gon, as shown in Figure 7.19, by casting a ray from the point in any direction.
We find all intersections of the ray with polygon edges, and classify each as either
entering
(if the direction vector of the ray and the outward edge normal for the
edge have a positive inner product) or
leaving
(if the inner product is negative).
A point with more leaving intersections than entering ones is inside. Indeed, the
difference between the number of leaving intersections and the number of enter-
ing intersections is called the
winding number
of the polygon about the point,
and captures the notion of “how many times the polygon wraps around the point,
counting counterclockwise.” The simple description above depends on the inter-
sections of the ray and the polygon being a finite set. It doesn't work when the
ray actually contains an entire edge, and the answer, when the test point lies
on
an edge, depends on one's definition of the intersection of a ray and a segment
(as does the answer when the ray passes through a vertex of the polygon). This
ray-casting approach to computing the winding number implicitly uses a strong
theorem that says that the ray-casting computation results in the same value as
the computation of the winding number itself, which is defined in a very different
way: For a polygon with vertices
P
1
,
P
2
,
P
4
P
0
Figure 7.19: To test whether Q
is in the interior of the polygon,
we cast a ray in an arbitrary
direction, and then count enter-
ing and leaving intersections with
the edges. In this case, there
are two leaving intersections (the
first and third) and one enter-
ing intersection, so the point is
inside.
,
P
n
, the winding number about a point
Q
is defined by considering the angles between successive rays from
Q
to each
P
i
.
If these angles sum to 2
...
π
, the winding number is 1; if they sum to 4
π
, it's 2, etc.
Formally,
cos
−
1
(
P
i
+
1
−
.
n
)=
1
2
Q
)
·
(
P
i
−
Q
)
WindingNumber
(
Q
,
{
P
1
,
P
2
,
...
,
P
n
}
π
P
i
+
1
−
Q
P
i
−
Q
i
=
1
(7.121)
Note that this is undefined if
Q
happens to be one of the vertices
P
i
, because the
denominator is then zero. We also treat it as undefined when the argument to
cos
−
1
is
1; this occurs when
Q
is on an edge of the polygon.
With these various definitions of the winding number, one can think of a curve
as dividing the plane into a collection of regions. Within each region, the winding
number is a constant; the labeling of regions by their winding numbers goes back
to Listing, a student of Gauss [Lis48].
−
Inline Exercise 7.16:
(a) Develop a small program to test whether a point
is in the interior of a
convex
polygon by testing whether it's strictly on the
proper side of each edge. What's the running time in terms of the number
n
of
polygon vertices? (b) Assuming that you want to test
many
points to determine
whether they're inside or outside a
single
convex polygon, you can afford to
do some preprocessing. Using a ray-casting test like the one described in this
chapter, and a horizontal ray, show how you can create an O
(log
n
)
algorithm
for inside/outside testing. Hint: Because the polygon is
convex,
you need only
test ray intersection with a small number of edges. If you sort the vertices by
their
y
-coordinates, how can you quickly find those edges?
