7.2.1 Definition of the distances between two point sets
The definitions of the squared distance
function for five cases described in Sect. 7.1
are given as follows:
The squared distance function between a point
and an arbitrary point on a parametric curve
in three
dimensional Cartesian space is
defined by
(7.1)
The squared distance function between a point
and a parametric surface patch
in
three dimensional Cartesian space is defined by
(7.2)
The squared distance function between two parametric curves
and
in three-dimensional Cartesian space is defined by
(7.3)
The squared distance function between a parametric curve
and a parametric surface patch
in three dimensional Cartesian space is defined
by
(7.4)
The squared distance function between two parametric surface patches
and
in three dimensional Cartesian space is defined by
(7.5)
The parameters
,
,
,
in (7.1) -
(7.5) satisfy the following inequalities
. The general approach to locate local minima
of the squared distance function is to search for zeros of the
gradient vector field
and then examine if at those zeros
the squared distance function attains minima. For each of the five
cases, the condition
becomes
The stationary points of the squared distance function between a point
and an arbitrary point on a parametric
curve
satisfy the following equation
When the parametric curves and surfaces are in rational form, the squared
distance
between two point sets can be represented by:
(7.16)
where
is the vector
. For the
problems considered in this chapter,
. The
gradient of
is given by
(7.17)
If
, the numerator of the above
expression should be zero. Since the numerator in
(7.17) is a polynomial vector field, our problem is
reduced to finding the singular points of an
-dimensional
polynomial vector field, i.e. the roots of a system of
nonlinear
polynomial equations in
unknowns within a given
-dimensional
box [392,300]. The solution of this problem
is discussed in Chap.
4.
Because the curves and surfaces involved in these distance problems
are bounded, it is necessary to break up the distance computation
problem into a number of subproblems which deal with interior and
boundary points of the geometric objects separately. The major steps
of the algorithm are outlined below:
Find the minimal and maximal distances in the interior
domain of point sets.
Find the distances at four corner points of the
surface
if one point set is a surface.
Find the minimal and maximal distances along the four
edges of the surface if one point set is a surface.
Find the distances at end points
if one point set is a curve.
Compare the distances to get the absolute minimum and maximum.