Graphics Reference
In-Depth Information
where
a
,
b
, and
c
are the column vectors
a
=
(
v
×
w
)/(
u
·
(
v
×
w
)),
b
=
(
w
×
u
)/(
u
·
(
v
×
w
)), and
c
=
(
u
×
v
)/(
u
·
(
v
×
w
)).
In general, whenever the inverse of
A
,inv(
A
), exists, it can always be factored as
1
det(
A
)
M
,
inv(
A
)
=
where
M
is called the
adjoint matrix
of
A
, denoted adj(
A
).
3.1.6
Determinant Predicates
Determinants are also useful in concisely expressing geometrical tests. Many, if not
most, geometrical tests can be cast into determinant form. If a determinant can be
robustly and efficiently evaluated, so can the geometrical test. Therefore, the evalua-
tion of determinants has been well studied. In particular, the sign of a determinant
plays a special role in many geometrical tests, often used as topological predicates to
test the orientation, sidedness, and inclusion of points. Note that direct evaluation
of determinant predicates (without, for example, applying common subexpression
elimination) does not, in general, result in the most efficient or robust expressions.
Also note that determinant predicates implemented using floating-point arithmetic
are very sensitive to rounding errors and algorithms relying on a correct sign in degen-
erate configurations are likely not to work as intended. For more on robustness errors
and how to handle them, see Chapters 11 and 12. With that caveat, as an application
of determinants, the next few sections illustrate some of the more useful of these
topological predicates.
3.1.6.1 ORIENT2D(
A
,
B
,
C
)
Let
A
=
(
a
x
,
a
y
),
B
=
(
b
x
,
b
y
), and
C
=
(
c
x
,
c
y
) be three 2D points, and let
ORIENT2D(
A
,
B
,
C
) be defined as
a
x
a
y
1
a
x
−
c
x
a
y
−
c
y
ORIENT2D(
A
,
B
,
C
)
=
b
x
b
y
1
=
.
b
x
−
c
x
b
y
−
c
y
c
x
c
y
1
