Graphics Reference
In-Depth Information
6.4.1 Theorem.
(Convexity test for polygons) Assume that a planar polygon
P
is
defined by a sequence of points
p
0
,
p
1
,...,
p
n
,
p
n+1
=
p
0
. The polygon
P
will be convex
if and only if the vectors
p
i
p
i+1
and
p
i+1
p
i+2
either all determine left turns or all right
turns.
Another way to express this test is to say that as one traverses the boundary of
the polygon, successive edges either all make left or right turns. Alternatively, vertices
of the polygon always lie on the same side of the previous edge as the one before.
There is a simple test for when two vectors
u
and
v
determine a left turn: It
happens if and only if
u
v
Ê
Ë
ˆ
¯
(
)
≥
det
=
euv
•
¥
0
.
3
Therefore, the convexity test above is easy to program.
Next, suppose that the polygon
F
is the face of a solid
S
in
R
3
and that
p
is a point
in the interior of
F
.
Definition.
Let
n
be any normal for
F
. We say that
n
is an
inward-pointing normal
to
F
with respect to the solid
S
, if the segment [
p
,
p
+e
n
] is entirely contained in the
solid for some e>0. In that case, -
n
is called an
outward-pointing normal
for
F
with
respect to
S
.
There is an easy way to determine if a normal is inward- or outward-pointing
for a convex solid
S
. If
q
is any point in the interior of
S
, then
n
will be an outward-
pointing normal for
F
if
nqp
•
≥ 0
,
otherwise it is inward-pointing.
Definition.
If
P
is a polygon in a plane
X
, an
orientation
of
P
is an orientation of
X
.
An
oriented polygon
is a pair (
P
,o), where
P
is a polygon and o is an orientation of
P
.
A choice of a normal vector
n
to a face
F
of a solid defines an orientation of the
face. Choose an ordered basis (
u
,
v
) for the plane
X
generated by the face so that (
u
,
v
,
n
)
induces the standard orientation of
R
3
. The orientation of
X
induced by (
u
,
v
) is well-
defined.
Definition.
The orientation [
u
,
v
] of
X
is called the
orientation of
F
induced by
n
.
Conversely, an orientation o = [
u
,
v
] of the face determines the well-defined unit
normal vector
1
n
=
uv
uv
¥
.
¥
Definition.
The vector
n
is called the
normal vector of
F
induced by the orientation o
.
