Intersection between a point and a planar implicit curve is defined
as:
(5.2)
where
is usually a polynomial and
represents an
algebraic curve. In an exact arithmetic context,
we can substitute
in
and verify if
the results are zero. Similarly, we could handle
(5.3)
where
represents an implicit 3-D space
curve. However, if floating point arithmetic is used in evaluating
, the result will not be exactly zero due to round off errors.
Now let us examine the distance between a point
and a planar implicit curve
.
The geometric
distance is given by:
(5.4)
where
must satisfy
. The
true geometric distance is difficult and expensive to compute
(especially if we need to deal with a large set of points as in
inspection problems). As an alternative, we can compute an approximate
distance. We Taylor expand
about
up to the
first order as follows:
(5.5)
where
and
. From the stationary
condition of the distance
, we can
deduce the orthogonality condition
(5.6)
Since we do not know the footpoint
on the implicit curve
which gives the minimum distance, we will also Taylor expand
and
about
up to the first order as follows:
(5.7)
(5.8)
After substituting (5.7) and
(5.8) into (5.6) and neglecting
the second order terms we have
(5.9)
Equations (5.5) and (5.9)
form a linear system in
and
which can be solved
as
(5.10)
provided the denominators are not zero.
Therefore the first order approximation to the true geometric
distance (5.4) reduces to
(5.11)
provided that
0. Consequently if the algebraic distance
1 where
is a small positive constant and
is normalized so
that
in the domain of interest including
, then an approximate
minimum distance check can be performed by evaluating the non-algebraic distance (5.11).
Figure 5.6:
Algebraic curves meet at small angle
Having evaluated the approximate minimum distance
(5.11), we can now address a complex point to point
intersection problem which further elucidates the notion of geometric
distance for use in intersection problems. We discuss an intersection
problem, where we need to check if the intersection point of the two
planar algebraic curves crossing at a small angle, intersects a
point
as illustrated in Fig. 5.6 or
more precisely
(5.12)
where
(5.13)
evaluated at the intersection point
.
Even if
and
satisfy
(5.14)
(5.15)
it is not enough to guarantee proximity of
to
the intersection of
,
as shown in
Fig. 5.6.
Figure 5.7:
Algebraic curves approximated by straight lines
In such cases, using a linear approximation, and letting
(5.16)
be the angle of intersection as in Fig. 5.7 near the
intersection point, a better criterion for evaluating if
is near the intersection of
and
is given by
(5.17)
Next: 5.4.2 Point/rational polynomial parametric
Up: 5.4 Point/curve intersection
Previous: 5.4 Point/curve intersection
Contents Index
December 2009