next up previous contents index
Next: 7.2.2 Geometric interpretation of Up: 7.2 Problem formulation Previous: 7.2 Problem formulation   Contents   Index


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:

  1. The squared distance function between a point $ {\bf p}_o=(x_o\ y_o\ z_o)^T$ and an arbitrary point on a parametric curve $ {\bf r}(t)$ in three dimensional Cartesian space is defined by
    $\displaystyle D(t)=\vert{\bf p}_o - {\bf r}(t)\vert^2 = ({\bf p}_o - {\bf r}(t))\cdot({\bf p }_o - {\bf r}(t))\;.$     (7.1)

  2. The squared distance function between a point $ {\bf p}_{o}=(x_o\ y_o\ z_o)^T$ and a parametric surface patch $ {\bf r}={\bf r}(u,v)$ in three dimensional Cartesian space is defined by
    $\displaystyle D(u, v) = \vert {\bf p}_{o} - {\bf r}(u,v) \vert^2 = ({\bf p}_o - {\bf r}(u,v)) \cdot ({\bf p}_o - {\bf r}(u,v))\;.$     (7.2)

  3. The squared distance function between two parametric curves $ {\bf p}={\bf p}(u)$ and $ {\bf q}={\bf q}(v)$ in three-dimensional Cartesian space is defined by
    $\displaystyle D(u, v) = \vert {\bf p}(u) - {\bf q}(v) \vert^2 = ({\bf p}(u) - {\bf q}(v)) \cdot ({\bf p}(u) - {\bf q}(v))\;.$     (7.3)

  4. The squared distance function between a parametric curve $ {\bf p}={\bf p}(t)$ and a parametric surface patch $ {\bf q}={\bf q}(u,v)$ in three dimensional Cartesian space is defined by
    $\displaystyle D(t, u, v) = \vert {\bf p}(t) - {\bf q}(u,v) \vert^2 = ({\bf p}(t) - {\bf q}(u,v)) \cdot ({\bf p}(t) - {\bf q}(u,v))\;.$     (7.4)

  5. The squared distance function between two parametric surface patches $ {\bf p}={\bf p}(\sigma,t)$ and $ {\bf q}={\bf q}(u,v)$ in three dimensional Cartesian space is defined by
    $\displaystyle D(\sigma, t, u, v) = \vert {\bf p}(\sigma,t) - {\bf q}(u,v) \vert... ... ({\bf p}(\sigma,t) - {\bf q}(u,v)) \cdot ({\bf p}(\sigma,t) - {\bf q}(u,v))\;.$     (7.5)

The parameters $ \sigma$ , $ t$ , $ u$ , $ v$ in (7.1) - (7.5) satisfy the following inequalities $ 0 \leq \sigma, t,u, v \leq 1$ . The general approach to locate local minima of the squared distance function is to search for zeros of the gradient vector field $ \nabla D$ and then examine if at those zeros the squared distance function attains minima. For each of the five cases, the condition $ \nabla D= {\bf0}$ becomes
  1. The stationary points of the squared distance function between a point $ {\bf p}_o=(x_o\ y_o\ z_o)^T$ and an arbitrary point on a parametric curve $ {\bf r}(t)$ satisfy the following equation
    $\displaystyle D_t(t)=0\;,$     (7.6)

    which can be rewritten using (7.1) as
    $\displaystyle ({\bf p}_o-{\bf r}(t))\cdot{\bf r}_t(t)=0\;.$     (7.7)

  2. The stationary points of the squared distance function between a point $ {\bf p}_{o}=(x_o\ y_o\ z_o)^T$ and a parametric surface patch $ {\bf r}={\bf r}(u,v)$ satisfy the following two equations
    $\displaystyle D_u(u,v)=D_v(u,v)=0\;,$     (7.8)

    which can be rewritten using (7.2) as
    $\displaystyle ({\bf p}_o-{\bf r}(u,v))\cdot{\bf r}_u(u,v)= ({\bf p}_o-{\bf r}(u,v))\cdot{\bf r}_v(u,v)=0\;.$     (7.9)

  3. The stationary points of the squared distance function between two parametric curves $ {\bf p}={\bf p}(u)$ and $ {\bf q}={\bf q}(v)$ satisfy the following two equations
    $\displaystyle D_u(u,v)=D_v(u,v)=0\;,$     (7.10)

    which can be rewritten using (7.3) as
    $\displaystyle ({\bf p}(u) - {\bf q}(v))\cdot{\bf p}_u(v)= ({\bf p}(u) - {\bf q}(v))\cdot{\bf q}_v(v)=0\;.$     (7.11)

  4. The stationary points of the squared distance function between a parametric curve $ {\bf p}={\bf p}(t)$ and a parametric surface patch $ {\bf q}={\bf q}(u,v)$ satisfy the following three equations
    $\displaystyle D_t(t,u,v)=D_u(t,u,v)=D_v(t,u,v)=0\;,$     (7.12)

    which can be rewritten using (7.4) as
    $\displaystyle ({\bf p}(t) - {\bf q}(u,v))\cdot{\bf p}_t(t)=({\bf p}(t) - {\bf q... ... q}_u(u,v) %\nonumber \\ = ({\bf p}(t) - {\bf q}(u,v))\cdot{\bf q}_v(u,v)=0\;.$     (7.13)

  5. The stationary points of the squared distance function between two parametric surfaces $ {\bf p}={\bf p}(\sigma,t)$ and $ {\bf q}={\bf q}(u,v)$ satisfy the following four equations
    $\displaystyle D_\sigma(\sigma,t,u,v)=D_t(\sigma,t,u,v)=D_u(\sigma,t,u,v) =D_v(\sigma,t,u,v)=0\;,$     (7.14)

    which can be rewritten using (7.5) as
    $\displaystyle ({\bf p}(\sigma,t) - {\bf q}(u,v))\cdot{\bf p}_\sigma(\sigma,t)= ({\bf p}(\sigma,t) - {\bf q}(u,v))\cdot{\bf p}_t(\sigma,t)=0\;,$      
    $\displaystyle ({\bf p}(\sigma,t) - {\bf q}(u,v))\cdot{\bf q}_u(u,v)= ({\bf p}(\sigma,t) - {\bf q}(u,v))\cdot{\bf q}_v(u,v)=0\;.$     (7.15)

When the parametric curves and surfaces are in rational form, the squared distance $ D({\bf u})$ between two point sets can be represented by:

$\displaystyle D({\bf u})=\frac{P({\bf u})}{Q({\bf u})}\;,$     (7.16)

where $ {\bf u}$ is the vector $ ( u_1\ u_2\ \ldots\ u_n)^{\rm T}$ . For the problems considered in this chapter, $ n \in \{1, 2, 3, 4\}$ . The gradient of $ D({\bf u})$ is given by
$\displaystyle {\nabla}D =\frac{\nabla P({\bf u})Q({\bf u})-P({\bf u})\nabla Q({\bf u})}{Q^2({\bf u})}\;.$     (7.17)

If $ \nabla D({\bf u}) = {\bf0}$ , 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 $ n$ -dimensional polynomial vector field, i.e. the roots of a system of $ n$ nonlinear polynomial equations in $ n$ unknowns within a given $ n$ -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:

  1. Find the minimal and maximal distances in the interior domain of point sets.

  2. Find the distances at four corner points of the surface if one point set is a surface.

  3. Find the minimal and maximal distances along the four edges of the surface if one point set is a surface.

  4. Find the distances at end points if one point set is a curve.

  5. Compare the distances to get the absolute minimum and maximum.

next up previous contents index
Next: 7.2.2 Geometric interpretation of Up: 7.2 Problem formulation Previous: 7.2 Problem formulation   Contents   Index
December 2009