Open AccessArticle

The Accurate Method for Computing the Minimum Distance between a Point and an Elliptical Torus

Xiaowu Li

^1,*,†

Zhinan Wu

^2,†,

Linke Hou

^3,*,†,

Lin Wang

^1,† and

Chunguang Yue

^1,*,†

College of Information Engineering, Guizhou Minzu University, Guiyang 550025, China

School of Mathematics and Computer Science, Yichun University, Yichun 336000, China

Center for Economic Research, Shandong University, Jinan 250100, China

Authors to whom correspondence should be addressed.

^†

These authors contributed equally to this work.

Computers 2016, 5(1), 4; https://doi.org/10.3390/computers5010004

Submission received: 20 December 2015 / Revised: 14 February 2016 / Accepted: 16 February 2016 / Published: 24 February 2016

Download

Browse Figures

Versions Notes

Abstract

We present an accurate method to compute the minimum distance between a point and an elliptical torus, which is called the orthogonal projection problem. The basic idea is to transform a geometric problem into finding the unique real solution of a quartic equation, which is fit for orthogonal projection of a point onto the elliptical torus. Firstly, we discuss the corresponding orthogonal projection of a point onto the elliptical torus for test points at six different spatial positions. Secondly, we discuss the same problem for test points on three special positions, e.g., points on the z-axis, the long axis and the minor axis, respectively.

Keywords:

point projection; elliptical torus; major planar circle; minor planar ellipse; the long axis; the minor axis; intersection

1. Introduction

In this paper, we discuss how to compute the minimum distance between a point and a spatial parametric surface and to return the nearest point on the surface, as well as its corresponding parameter, which is also called the point projection problem (the point inversion problem) of a spatial parametric surface. This problem is very interesting due to its importance in geometric modeling, computer graphics and computer vision [1]. Both projection and inversion are essential for interactively selecting surfaces [1,2], for the surface fitting problem [1,2] and for the reconstructing surfaces problem [3,4,5]. It is also a key issue in the ICP (iterative closest point) algorithm for the shape and rendering of solid models with boundary representation [6] and projecting of a space curve onto a surface for curve surface design [7]. Many algorithms have been developed by using various techniques, including turning the problem into solving the root problem of polynomial equations, geometric methods, subdivision methods and the circular clipping algorithm. For more details, see [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30] and the references therein. The elliptical torus in the geodetic science, machinery and machine, biochemistry and biophysics, colloids and interfaces, antennas and propagation and other subjects has certain applications [31,32,33,34,35,36].

In the various methods mentioned above, all of the iterative processes can produce one iterative solution. Different from the above methods, we consider the special situation in which the test point generates countless corresponding solutions for the orthogonal projection problem. We then present an accurate method for computing the minimum distance between a point and an elliptical torus, which is called the orthogonal projection problem. The basic idea is to transform a geometric problem into finding the unique real solution of a quartic equation, which is fit for the orthogonal projection of a point onto the elliptical torus. Firstly, we will discuss the corresponding orthogonal projection of a point onto the elliptical torus for test points at six different spatial positions. Secondly, we will discuss the same problem for test points at three special positions, e.g., points at the z-axis, the long axis and the minor axis, respectively.

2. The Accurate Method for Computing the Minimum Distance between a Point and an Elliptical Torus

The parametric equation of an elliptical torus Γ can be defined as:

\{\begin{matrix} x (u, v) = (R + m cos (v)) cos (u) \\ y (u, v) = (R + m cos (v)) sin (u), 0 \leq v \leq 2 π, 0 \leq u \leq 2 π \\ z (u, v) = n sin (v) \end{matrix}

(1)

where

R > m > n > 0

. The corresponding implicit function equation of Equation (1) is:

\frac{{(\sqrt{x^{2} + y^{2}} - R)}^{2}}{m^{2}} + \frac{z^{2}}{n^{2}} = 1

(2)

where

R > m > n > 0

. We assume that the test point is

(x_{0}, y_{0}, z_{0})

. Orthogonally projecting the test point

(x_{0}, y_{0}, z_{0})

onto the x-y plane, the corresponding projecting point on the x-y plane is

(x_{0}, y_{0}, 0)

. It is not difficult to know that the corresponding orthogonal projection point for the minimum distance between point

(x_{0}, y_{0}, 0)

and the major planar circle:

\{\begin{matrix} x^{2} + y^{2} = R^{2} \\ z = 0 \end{matrix}

(3)

(x_{1}, y_{1}, 0) = (\frac{x_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}}, \frac{y_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}}, 0)

, which is set as the datum point. The plane determined by the z-axis and the line that passes through the point

(0, 0, 0)

and the test point

(x_{0}, y_{0}, z_{0})

is:

x_{0} y - y_{0} x = 0

(4)

It is not difficult to find that the plane Equation (4) is perpendicular to the horizontal tangent vector, which is determined by datum point

(x_{1}, y_{1}, 0)

at the major planar circle Equation (3). Therefore, computing the minimum distance between the test point

(x_{0}, y_{0}, z_{0})

and the elliptical torus Γ is equivalent to computing the minimum distance between the test point

(x_{0}, y_{0}, z_{0})

and the planar ellipse:

\begin{matrix} \{\begin{matrix} \frac{{(\sqrt{x^{2} + y^{2}} - R)}^{2}}{m^{2}} + \frac{z^{2}}{n^{2}} = 1 \\ x_{0} y - y_{0} x = 0 \end{matrix} \end{matrix}

(5)

The corresponding parametric equation of the planar ellipse Equation (5) is:

\{\begin{matrix} x = \frac{x_{0} (R + m cos (u))}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y = \frac{y_{0} (R + m cos (u))}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z = n sin (u) \end{matrix}

(6)

Therefore, the problem of finding the minimum distance between the test point

(x_{0}, y_{0}, z_{0})

and the elliptical torus Γ is naturally transformed into finding the minimum distance between the test point

(x_{0}, y_{0}, z_{0})

and the planar ellipse Equation (6). The tangent vector at the planar ellipse Equation (6) is:

V_{1} = (\frac{- x_{0} m sin (u)}{\sqrt{x_{0}^{2} + y_{0}^{2}}}, \frac{- y_{0} m sin (u)}{\sqrt{x_{0}^{2} + y_{0}^{2}}}, n cos (u))

(7)

The vector determined by test point

(x_{0}, y_{0}, z_{0})

and one point on the ellipse is:

V_{2} = (x_{0} - \frac{x_{0} (R + m cos (u))}{\sqrt{x_{0}^{2} + y_{0}^{2}}}, y_{0} - \frac{y_{0} (R + m cos (u))}{\sqrt{x_{0}^{2} + y_{0}^{2}}}, z_{0} - n sin (u))

(8)

The inner product of the two vectors

V_{1}, V_{2}

is:

〈 V_{1}, V_{2} 〉 = (m^{2} - n^{2}) cos (u) sin (u) + cos (u) n z_{0} - sin (u) m (\sqrt{x_{0}^{2} + y_{0}^{2}} - R) = 0

(9)

The left side of the Equation (9) can be transformed into the form:

sin (u) (m (\sqrt{x_{0}^{2} + y_{0}^{2}} - R) - (m^{2} - n^{2}) cos (u)) = cos (u) n z_{0}

(10)

Let

c o s (u) = t

; Equation (10) can be expressed as the form:

\pm \sqrt{1 - t^{2}} (m (\sqrt{x_{0}^{2} + y_{0}^{2}} - R) - (m^{2} - n^{2}) t) = t n z_{0}

(11)

Squaring both sides of the Equation (11) and simplifying, we get:

a_{0} t^{4} + a_{1} t^{3} + a_{2} t^{2} + a_{3} t + a_{4} = 0

(12)

where

a_{0} = {(m^{2} - n^{2})}^{2}, a_{1} = - 2 m (m^{2} - n^{2}) (\sqrt{x_{0}^{2} + y_{0}^{2}} - R), a_{2} = m^{2} ({(\sqrt{x_{0}^{2} + y_{0}^{2}} - R)}^{2} - (m^{2} - 2 n^{2})) - n^{2} (n^{2} - z_{0}^{2}),

a_{3} = 2 m (m^{2} - n^{2}) (\sqrt{x_{0}^{2} + y_{0}^{2}} - R), a_{4} = - m^{2} {(\sqrt{x_{0}^{2} + y_{0}^{2}} - R)}^{2}

. The simplified Equation (12) is:

t^{4} + a t^{3} + b t^{2} + c t + d = 0

(13)

where

a = \frac{a_{1}}{a_{0}}, b = \frac{a_{2}}{a_{0}}, c = \frac{a_{3}}{a_{0}}, d = \frac{a_{4}}{a_{0}} .

Let

Y = t + \frac{a}{4}

, then the Equation (13) can further be simplified as:

Y^{4} + p Y^{2} + q Y + r = 0

(14)

where

p = b - \frac{3 a^{2}}{8}, q = c - \frac{a b}{2} + \frac{a^{3}}{8}, r = d - \frac{a c}{4} + \frac{a^{2} b}{16} - \frac{3 a^{4}}{256} .

Lemma 1.

Equation (14) can be factored into:

Y^{4} + p Y^{2} + q Y + r = (Y^{2} + λ Y + β) (Y^{2} - λ Y + γ) = 0

(15)

where

λ, β, γ

are three parameters to be determined by

p, q, r

Proof.

We assume that the left-hand side of Equation (15) has four roots

Y_{1}, Y_{2}, Y_{3}, Y_{4}

, and then, we have

Y^{4} + p Y^{2} + q Y + r = (Y - Y_{1}) (Y - Y_{2}) (Y - Y_{3}) (Y - Y_{4})

. Because the multiplication of an arbitrary two of four factors

(Y - Y_{1}), (Y - Y_{2}), (Y - Y_{3}), (Y - Y_{4})

must generate a quadratic trinomial in which the coefficient of the first term is one, we will obtain the right side of the equation in Equation (15). ☐

Theorem 1.

The two real roots of the Equation (15) are:

Y_{1} = \frac{- λ + \sqrt{λ^{2} - 4 β}}{2}, Y_{2} = \frac{- λ - \sqrt{λ^{2} - 4 β}}{2}

Proof.

From Lemma 1, Formula (15) can be expressed in the following way,

Y^{4} + p Y^{2} + q Y + r = (Y^{2} + λ Y + β) (Y^{2} - λ Y + γ) = Y^{4} + (β + γ - λ^{2}) Y^{2} + (λ γ - λ β) Y + β γ = 0

(16)

Comparing coefficients in both sides of Formula (16), we get:

\{\begin{matrix} β + γ = λ^{2} + p \\ β - γ = - \frac{q}{λ} \\ β γ = r \end{matrix}

(17)

Combining Equation (16) with Equation (17), it is not difficult to find that:

\{\begin{matrix} β = \frac{1}{2} (λ^{2} + p - \frac{q}{λ}) \\ γ = \frac{1}{2} (λ^{2} + p + \frac{q}{λ}) \end{matrix}

(18)

Substituting Formula (18) into the third formula of Equation (17) and simplifying it, we get:

λ^{6} + 2 p λ^{4} + (p^{2} - 4 r) λ^{2} - q^{2} = 0

(19)

We know that the following cubic equation for x:

x^{3} + A x^{2} + B x + C = 0

(20)

has only one real root:

x_{1} = \frac{1}{6} x_{0} + \frac{(2 A^{2} - 6 B)}{3 x_{0}} - \frac{A}{3}

(21)

and a pair of complex roots:

\{\begin{matrix} x_{2} = - \frac{1}{12} x_{0} + \frac{(3 B - A^{2})}{3 x_{0}} - \frac{A}{3} + \frac{\sqrt{3}}{2} I (\frac{1}{6} x_{0} + \frac{(6 B - 2 A^{2})}{3 x_{0}}) \\ x_{3} = - \frac{1}{12} x_{0} + \frac{(3 B - A^{2})}{3 x_{0}} - \frac{A}{3} - \frac{\sqrt{3}}{2} I (\frac{1}{6} x_{0} + \frac{(6 B - 2 A^{2})}{3 x_{0}}) \end{matrix}

where

x_{0} = {(36 A B - 108 C - 8 A^{3} + 12 \sqrt{12 A^{3} C - 3 A^{2} B^{2} - 54 A B C + 12 B^{3} + 81 C^{2}})}^{\frac{1}{3}}

. It is easy to know that a pair of complex roots

x_{2}

and

x_{3}

are not satisfied for Formula (19), because there is no imaginary root fit for the orthogonal projection point, so we have to abandon them. Based on Equation (20), the real root of Equation (19) is:

λ = λ_{1} = \sqrt{\frac{1}{6} λ_{0} + \frac{(2 A^{2} - 6 B)}{3 λ_{0}} - \frac{A}{3}}

and:

λ = λ_{2} = - \sqrt{\frac{1}{6} λ_{0} + \frac{(2 A^{2} - 6 B)}{3 λ_{0}} - \frac{A}{3}}

where

λ_{0} = {(36 A B - 108 C - 8 A^{3} + 12 \sqrt{12 A^{3} C - 3 A^{2} B^{2} - 54 A B C + 12 B^{3} + 81 C^{2}})}^{\frac{1}{3}}

and

A = 2 p,

B = p^{2} - 4 r, C = - q^{2} .

Substituting these results into the right-hand side of Formula (15), we get the four roots

Y_{1}, Y_{2}, Y_{3}, Y_{4}

, namely, two real roots:

Y_{1} = \frac{- λ + \sqrt{λ^{2} - 4 β}}{2}, Y_{2} = \frac{- λ - \sqrt{λ^{2} - 4 β}}{2}

and a pair of complex roots

Y_{3} = \frac{- λ + \sqrt{λ^{2} - 4 γ}}{2}, Y_{4} = \frac{- λ - \sqrt{λ^{2} - 4 γ}}{2}

☐

According to the result of Theorem 1 and the corresponding four roots of Formula (13), there are two real roots,

t_{1} = t_{11} = \frac{- λ + \sqrt{λ^{2} - 4 β}}{2} - \frac{a}{4}

(22)

t_{1} = t_{12} = \frac{- λ - \sqrt{λ^{2} - 4 β}}{2} - \frac{a}{4}

(23)

and a pair of complex roots:

\{\begin{matrix} t_{2} = t_{21} = \frac{- λ + \sqrt{λ^{2} - 4 γ}}{2} - \frac{a}{4} \\ t_{2} = t_{22} = \frac{- λ - \sqrt{λ^{2} - 4 γ}}{2} - \frac{a}{4} \end{matrix}

(24)

respectively. We discard a pair of complex roots

t_{21}, t_{22}

because Equation (19) has two real roots

λ = λ_{1} = \sqrt{\frac{1}{6} λ_{0} + \frac{(2 A^{2} - 6 B)}{3 λ_{0}} - \frac{A}{3}}

and

λ = λ_{2} = - \sqrt{\frac{1}{6} λ_{0} + \frac{(2 A^{2} - 6 B)}{3 λ_{0}} - \frac{A}{3}}

. Therefore, there are four real root solutions for

t_{1}

, but only two of them are satisfied with the conditions by the point projection problem. By verification, if

\sqrt{x_{0}^{2} + y_{0}^{2}} > R

, then the solution for Equation (13) is:

t_{1} = t_{11} = \frac{- λ_{1} + \sqrt{λ_{1}^{2} - 4 β}}{2} - \frac{a}{4}

(25)

\sqrt{x_{0}^{2} + y_{0}^{2}} < R

, then the solution for Equation (13) is:

t_{1} = t_{12} = \frac{- λ_{2} - \sqrt{λ_{2}^{2} - 4 β}}{2} - \frac{a}{4}

(26)

\sqrt{x_{0}^{2} + y_{0}^{2}} = R

, then the solution for Equation (13) is

t_{1} = 0

Furthermore, we have six cases with different test points (see Figure 1):

(1): If $\sqrt{x_{0}^{2} + y_{0}^{2}} > R, z_{0} > 0$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is:

$\{\begin{matrix} x_{2} = \frac{x_{0} (R + m t_{11})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} (R + m t_{11})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = n \sqrt{1 - t_{11}^{2}} \end{matrix}$
(2): If $\sqrt{x_{0}^{2} + y_{0}^{2}} > R, z_{0} < 0$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is:

$\{\begin{matrix} x_{2} = \frac{x_{0} (R + m t_{11})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} (R + m t_{11})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = - n \sqrt{1 - t_{11}^{2}} \end{matrix}$
(3): If $\sqrt{x_{0}^{2} + y_{0}^{2}} < R, z_{0} > 0$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is:

$\{\begin{matrix} x_{2} = \frac{x_{0} (R + m t_{12})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} (R + m t_{12})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = n \sqrt{1 - t_{12}^{2}} \end{matrix}$
(4): If $\sqrt{x_{0}^{2} + y_{0}^{2}} < R, z_{0} < 0$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is:

$\{\begin{matrix} x_{2} = \frac{x_{0} (R + m t_{12})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} (R + m t_{12})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = - n \sqrt{1 - t_{12}^{2}} \end{matrix}$
(5): If $\sqrt{x_{0}^{2} + y_{0}^{2}} = R, z_{0} > 0$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is:

$\{\begin{matrix} x_{2} = \frac{x_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = n \end{matrix}$
(6): If $\sqrt{x_{0}^{2} + y_{0}^{2}} = R, z_{0} < 0$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is:

$\{\begin{matrix} x_{2} = \frac{x_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = - n \end{matrix}$

Remark 1. Because of the errors due to the floating-point numbers in the computer’s arithmetic operation, in the program implementation, we must consider the case in which the roots

t_{1} = t_{11}, t_{1} = t_{12}

are complex roots. The specific approach is as follows:

because

λ_{0} = {(36 A B - 108 C - 8 A^{3} + 12 \sqrt{12 A^{3} C - 3 A^{2} B^{2} - 54 A B C + 12 B^{3} + 81 C^{2}})}^{\frac{1}{3}}

12 A^{3} C - 3 A^{2} B^{2} - 54 A B C + 12 B^{3} + 81 C^{2} < 0

, then

λ_{0} = {(36 A B - 108 C - 8 A^{3} + 12 \sqrt{- (12 A^{3} C - 3 A^{2} B^{2} - 54 A B C + 12 B^{3} + 81 C^{2})} i)}^{\frac{1}{3}} = {(λ_{0 r} + λ_{0 i} i)}^{\frac{1}{3}}

, where

λ_{0 r}, λ_{0 i}

denotes the real part and the imaginary part of complex number

λ_{0}

, respectively. Let

r = \sqrt{λ_{0 r}^{2} + λ_{0 i}^{2}}

θ_{1} = acos (\frac{λ_{0 r}}{r})

R = r^{\frac{1}{3}}

(1): If $λ_{0 i} \geq 0$ , then $λ_{0} = R cos (θ_{1} / 3) + R sin (θ_{1} / 3) i$
(2): If $λ_{0 i} \leq 0$ , then $λ_{0} = R cos (θ_{1} / 3) - R sin (θ_{1} / 3) i$ .

Let

{(λ^{2} - 4 β)}^{\frac{1}{2}} = {(s_{r} + s_{i} i)}^{\frac{1}{2}}

, where

s_{r}, s_{i}

represent the real part and imaginary part of complex number

λ^{2} - 4 β

, respectively. Therefore:

(1): If $s_{i} \geq 0$ , then ${(λ^{2} - 4 β)}^{\frac{1}{2}} = {(s_{r}^{2} + s_{i}^{2})}^{\frac{1}{4}} cos (θ_{2} / 2) + {(s_{r}^{2} + s_{i}^{2})}^{\frac{1}{4}} sin (θ_{2} / 2) i$
(2): If $s_{i} \leq 0$ , then ${(λ^{2} - 4 β)}^{\frac{1}{2}} = {(s_{r}^{2} + s_{i}^{2})}^{\frac{1}{4}} cos (θ_{2} / 2) - {(s_{r}^{2} + s_{i}^{2})}^{\frac{1}{4}} sin (θ_{2} / 2) i$ , where $θ_{2} = acos (\frac{s_{r}}{{(s_{r}^{2} + s_{i}^{2})}^{\frac{1}{2}}})$ . In the process of computing the real roots, we delete the imaginary part of the roots $t_{1} = t_{11} = \frac{- λ_{1} + \sqrt{λ_{1}^{2} - 4 β}}{2} - \frac{a}{4}$ and $t_{1} = t_{12} = \frac{- λ_{2} - \sqrt{λ_{2}^{2} - 4 β}}{2} - \frac{a}{4}$ .

Now, we begin to deal with the first special case in which the test point is on the z-axis, namely test point is

(0, 0, z_{0})

. We compute the corresponding orthogonal projection point

(x_{2}, y_{2}, z_{2})

on the specific planar ellipse

\{\begin{matrix} x = R + m cos (u), \\ y = 0, \\ z = n sin (u) . \end{matrix}

Because

x_{0} = y_{0} = 0

, this special case is satisfied with

\sqrt{x_{0}^{2} + y_{0}^{2}} < R

, then the corresponding parameter value is

t_{1} = t_{12} = \frac{- λ_{2} - \sqrt{λ_{2}^{2} - 4 β}}{2} - \frac{a}{4}

. Based on this parameter value, we present the corresponding orthogonal projection point

(x_{2}, y_{2}, z_{2})

in the following with different test points on the z-axis of the elliptical torus (see Figure 2).

(1): If $z_{0} > 0$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is $\{\begin{matrix} x_{2} = R + m t_{12}, \\ y_{2} = 0, \\ z_{2} = n \sqrt{1 - t_{12}^{2}} . \end{matrix}$
(2): If $z_{0} < 0$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is $\{\begin{matrix} x_{2} = R + m t_{12}, \\ y_{2} = 0, \\ z_{2} = - n \sqrt{1 - t_{12}^{2}} . \end{matrix}$
(3): If $z_{0} = 0$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is $\{\begin{matrix} x_{2} = R - m, \\ y_{2} = 0, \\ z_{2} = 0 . \end{matrix}$

According to these three cases, if

z_{0} > 0, z_{0} < 0

z_{0} = 0

, the corresponding orthogonal projection point set

(x_{2}, y_{2}, z_{2})

of test point

(0, 0, z_{0})

is:

\{\begin{matrix} x^{2} + y^{2} = {(R + m t_{12})}^{2} \\ z = n \sqrt{1 - t_{12}^{2}} \end{matrix}

(27)

\{\begin{matrix} x^{2} + y^{2} = {(R + m t_{12})}^{2} \\ z = - n \sqrt{1 - t_{12}^{2}} \end{matrix}

(28)

and:

\{\begin{matrix} x^{2} + y^{2} = {(R - m)}^{2} \\ z = 0 \end{matrix}

(29)

respectively.

We turn to discuss the second special case in which test point

(x_{0}, y_{0}, z_{0})

is on the long axis, and its parametric equation is

\{\begin{matrix} x = \frac{x_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} + \frac{x_{0} m}{\sqrt{x_{0}^{2} + y_{0}^{2}}} s \\ y = \frac{y_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} + \frac{y_{0} m}{\sqrt{x_{0}^{2} + y_{0}^{2}}} s, - 1 \leq s \leq 1 \\ z = 0 \end{matrix}

(30)

We then compute the corresponding orthogonal projection point

(x_{2}, y_{2}, z_{2})

in the following five cases with different test points on the planar ellipse (see Figure 3).

(1): If $- 1 \leq s \leq - \frac{m^{2} - n^{2}}{m^{2}}$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is expressed as:

$\{\begin{matrix} x_{2} = \frac{x_{0} (R - m)}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} (R - m)}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = 0 \end{matrix}$

(31)
(2): If $- \frac{m^{2} - n^{2}}{m^{2}} < s < 0$ , then the corresponding parameter value is $t_{1} = t_{12} = \frac{- λ_{2} - \sqrt{λ_{2}^{2} - 4 β}}{2} - \frac{a}{4}$ , so the corresponding orthogonal projection points $(x_{2}, y_{2}, z_{2})$ are expressed as:

$\{\begin{matrix} x_{2} = \frac{x_{0} (R + m t_{12})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} (R + m t_{12})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = n \sqrt{1 - t_{12}^{2}} \end{matrix}$

(32)

and:

$\{\begin{matrix} x_{2} = \frac{x_{0} (R + m t_{12})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} (R + m t_{12})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = - n \sqrt{1 - t_{12}^{2}} \end{matrix}$

(33)
(3): If $s = 0$ , then the corresponding orthogonal projection points $(x_{2}, y_{2}, z_{2})$ are expressed as:

$\{\begin{matrix} x_{2} = \frac{x_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = n \end{matrix}$

(34)

and:

$\{\begin{matrix} x_{2} = \frac{x_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = - n \end{matrix}$

(35)
(4): If $0 < s < \frac{m^{2} - n^{2}}{m^{2}}$ , then the corresponding parameter value is $t_{1} = t_{11} = \frac{- λ_{1} + \sqrt{λ_{1}^{2} - 4 β}}{2} - \frac{a}{4}$ . Therefore, the corresponding orthogonal projection points $(x_{2}, y_{2}, z_{2})$ are expressed as:

$\{\begin{matrix} x_{2} = \frac{x_{0} (R + m t_{11})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} (R + m t_{11})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = n \sqrt{1 - t_{11}^{2}} \end{matrix}$

(36)

and:

$\{\begin{matrix} x_{2} = \frac{x_{0} (R + m t_{11})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} (R + m t_{11})}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = - n \sqrt{1 - t_{11}^{2}} \end{matrix}$

(37)
(5): If $\frac{m^{2} - n^{2}}{m^{2}} \leq s \leq 1$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is expressed as:

$\{\begin{matrix} x_{2} = \frac{x_{0} (R + m)}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} (R + m)}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = 0 \end{matrix}$

(38)

Remark 2. When the test point

(x_{0}, y_{0}, z_{0})

and parameter s are determined, the left-hand side

(x, y, z)

of Equation (30) is also uniquely determined. In the five cases above, the new test point

(x_{0}, y_{0}, z_{0})

in Equations (31)–(38) is equal to

(x, y, z)

in the left side of Equation (30), rather than the original test point

(x_{0}, y_{0}, z_{0})

. We remind the readers to pay attention to our explanation here with respect to different test points in Equations (30)–(38).

We start to analyze the third special case in which the test point

(x_{0}, y_{0}, z_{0})

is on the minor axis and its parametric equation is:

\{\begin{matrix} x = \frac{x_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y = \frac{y_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}}, - \infty < s < \infty \\ z = n s \end{matrix}

(39)

We compute the corresponding orthogonal projection point

(x_{2}, y_{2}, z_{2})

on the planar ellipse:

(1): If $s > 0$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is:

$\{\begin{matrix} x_{2} = \frac{x_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = n \end{matrix}$

(40)
(2): If $s < 0$ , then the corresponding orthogonal projection point $(x_{2}, y_{2}, z_{2})$ is expressed as:

$\{\begin{matrix} x_{2} = \frac{x_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = - n \end{matrix}$

(41)
(3): If $s = 0$ , then the corresponding orthogonal projection points $(x_{2}, y_{2}, z_{2})$ are expressed as:

$\{\begin{matrix} x_{2} = \frac{x_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = n \end{matrix}$

(42)

and:

$\{\begin{matrix} x_{2} = \frac{x_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ y_{2} = \frac{y_{0} R}{\sqrt{x_{0}^{2} + y_{0}^{2}}} \\ z_{2} = - n \end{matrix}$

(43)

Remark 3. When the test point

(x_{0}, y_{0}, z_{0})

and parameter s are determined, the left-hand side

(x, y, z)

of Equation (39) is also uniquely determined. In the three cases above, the new test point

(x_{0}, y_{0}, z_{0})

in Equations (40)–(43) is equal to

(x, y, z)

in the left side of Equation (39), rather than the original test point

(x_{0}, y_{0}, z_{0})

. We remind the readers to pay attention to our explanation here with respect to different test points in Equations (39)–(43).

3. Conclusions

This paper investigates the problem related to a point projection onto the elliptical torus surface. We present the accurate method for the orthogonal projection problem about how to compute the minimum distance between a point and the elliptical torus for all kinds of positions. A topic for future research is to develop a method to compute the minimum distance between a point and a general completely central symmetrical surface.

Acknowledgments

We would like to take the opportunity to thank the reviewers for their thoughtful and meaningful comments. This work is supported by the National Natural Science Foundation of China (Grant No. 61263034), the Scientific and Technology Foundation Funded Project of Guizhou Province (Grant No. [2014]2093), the National Bureau of Statistics Foundation Funded Project (Grant No. 2014LY011), the Key Laboratory of Pattern Recognition and Intelligent System of Construction Project of Guizhou Province (Grant No. [2009]4002) and the Information Processing and Pattern Recognition for Graduate Education Innovation Base of Guizhou Province. Linke Hou is supported by the Visiting Scholar Program of the Chinese Scholarship Council (Grant No. 201406225058).

Author Contributions

The contributions of all of the authors are the same. All of them have worked together to develop the present manuscript.

Conflicts of Interest

The authors declare no conflict of interest.

References

Ma, Y.L.; Hewitt, W.T. Point inversion and projection for NURBS curve and surface: Control polygon approach. Comput. Aided Geom. Des. 2003, 20, 79–99. [Google Scholar] [CrossRef]
Yang, H.P.; Wang, W.P.; Sun, J.G. Control point adjustment for B-spline curve approximation. Comput. Aided Des. 2004, 36, 639–652. [Google Scholar] [CrossRef] [Green Version]
Johnson, D.E.; Cohen, E. A Framework for efficient minimum distance computations. In Proceedings of the IEEE Intemational Conference on Robotics & Automation, Leuven, Belgium, 20–20 May 1998.
Piegl, L.; Tiller, W. Parametrization for surface fitting in reverse engineering. Comput. Aided Des. 2001, 33, 593–603. [Google Scholar] [CrossRef]
Pegna, J.; Wolter, F.E. Surface curve design by orthogonal projection of space curves onto free-form surfaces. J. Mech. Des. ASME Trans. 1996, 118, 45–52. [Google Scholar] [CrossRef]
Hu, S.M.; Wallner, J. A second order algorithm for orthogonal projection onto curves and surfaces. Comput. Aided Geom. Des. 2005, 22, 251–260. [Google Scholar] [CrossRef]
Besl, P.J.; McKay, N.D. A method for registration of 3-D shapes. IEEE Trans. Pattern Anal. Mach. Intell. 1992, 14, 239–256. [Google Scholar] [CrossRef]
Mortenson, M.E. Geometric Modeling; Wiley: New York, NY, USA, 1985. [Google Scholar]
Zhou, J.M.; Sherbrooke, E.C.; Patrikalakis, N. Computation of stationary points of distance functions. Eng. Comput. 1993, 9, 231–246. [Google Scholar] [CrossRef]
Johnson, D.E.; Cohen, E. Distance extrema for spline models using tangent cones. In Proceedings of the 2005 Conference on Graphics Interface, Waterloo, ON, Canada, 9–11 May 2005.
Hartmann, E. On the curvature of curves and surfaces defined by normalforms. Comput. Aided Geom. Des. 1999, 16, 355–376. [Google Scholar] [CrossRef]
Limaien, A.; Trochu, F. Geometric algorithms for the intersection of curves and surfaces. Comput. Graph. 1995, 19, 391–403. [Google Scholar] [CrossRef]
Polak, E.; Royset, J.O. Algorithms with adaptive smoothing for finite minimax problems. J. Optim. Theory Appl. 2003, 119, 459–484. [Google Scholar] [CrossRef]
Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P. Numerical Recipes in C: The Art of Scientific Computing, 2nd ed.; Cambridge University Press: New York, NY, USA, 1992. [Google Scholar]
Elber, G.; Kim, M.S. Geometric Constraint solver using multivariate rational spline functions. In Proceedings of the Sixth ACM Symposiumon Solid Modeling and Applications, Ann Arbor, MI, USA, 6–8 June 2001; pp. 1–10.
Patrikalakis, N.; Maekawa, T. Shape Interrogation for Computer Aided Design and Manufacturing; Springer: Berlin, Germany, 2001. [Google Scholar]
Selimovic, I. Improved algorithms for the projection of points on NURBS curves and surfaces. Comput. Aided Geom. Des. 2006, 23, 439–445. [Google Scholar] [CrossRef]
Cohen, E.; Lyche, T.; Riesebfeld, R. Discrete B-splines and subdivision techniques in computer-aided geometric design and computer graphics. Comput. Graph. Image Process. 1980, 14, 87–111. [Google Scholar] [CrossRef]
Piegl, L.; Tiller, W. The NURBS Book; Springer: New York, NY, USA, 1995. [Google Scholar]
Liu, X.-M.; Yang, L.; Yong, J.-H.; Guf, H.-J.; Sun, J.-G. A torus patch approximation approach for point projection on surfaces. Comput. Aided Geom. Des. 2009, 26, 593–598. [Google Scholar] [CrossRef]
Li, X.; Xin, Q.; Wu, Z.; Zhang, M.; Zhang, Q. A geometric strategy for computing intersections of two spatial parametric curves. Vis. Comput. 2013, 29, 1151–1158. [Google Scholar] [CrossRef]
Kim, K.-J. Minimum distance between a canal surface and a simple surface. Comput. Aided Des. 2003, 35, 871–879. [Google Scholar] [CrossRef]
Li, X.; Jiang, H.; Chen, S.; Wang, X. An efficient surface-surface intersection algorithm based on geometry characteristics. Comput. Graph. 2004, 28, 527–537. [Google Scholar] [CrossRef]
Chen, S.-D.; Ma, W.; Xu, G.; Paul, G.-C. Computing the Hausdorff distance between two B-spline curves. Comput. Aided Des. 2010, 42, 1197–1206. [Google Scholar] [CrossRef]
Chen, X.-D.; Xu, G.; Yong, J.-H.; Wang, G.; Paul, G.-C. Computing the minimum distance between a point and a clamped B-spline surface. Graph. Models 2009, 71, 107–112. [Google Scholar] [CrossRef] [Green Version]
Chen, X.-D.; Yong, J.-H.; Wang, G.; Paul, G.-C.; Xu, G. Computing the minimum distance between a point and a NURBS curve. Comput. Aided Des. 2008, 40, 1051–1054. [Google Scholar] [CrossRef] [Green Version]
Chen, X.-D.; Chen, L.; Wang, Y.; Xu, G.; Yong, J.-H.; Paul, J.-C. Computing the minimum distance between two Bézier curves. J. Comput. Appl. Math. 2009, 229, 294–301. [Google Scholar] [CrossRef] [Green Version]
Chen, X.D.; Yong, J.H.; Wang, G.Z.; Paul, J.C.; Xu, G. Computing the minimum distance between a point and a NURBS curve. Comput. Aided Des. 2008, 40, 1051–1054. [Google Scholar] [CrossRef] [Green Version]
Oh, Y.-T.; Kim, Y.-J.; Lee, J.; Kim, Y.-S.; Elber, G. Efficient point-projection to freeform curves and surfaces. Comput. Aided Geom. Des. 2012, 29, 242–254. [Google Scholar] [CrossRef]
Sundar, B.R.; Chunduru, A.; Tiwari, R.; Gupta, A.; Muthuganapathy, R. Footpoint distance as a measure of distance computation between curves and surfaces. Comput. Graph. 2014, 38, 300–309. [Google Scholar] [CrossRef]
Borkowski, K.M. Accurate algorithms to transform geocentric to geodetic coordinates. J. Geod. 1989, 63, 50–56. [Google Scholar] [CrossRef]
Bil, T. Geometry of a mechanism with a higher pair in the form of two elliptical tori. Mech. Mach. Theory 2010, 45, 185–192. [Google Scholar] [CrossRef]
Bil, T. Kinematic analysis of a universal spatial mechanism containing a higher pair based on tori. Mech. Mach. Theory 2011, 46, 412–424. [Google Scholar] [CrossRef]
Haneskog, L.; Andersson, L.; Brekkan, E.; Englund, A.-K.; Kameyarna, K.; Llljas, L.; Greljer, E.; Flschbarg, J.; Lundahl, P. Monomeric human red cell glucose transporter (Glutl) in non-ionic detergent solution and a semi-elliptical toms model for detergent binding to membrane proteins. Biochim. Biophys. Acta 1996, 1282, 39–47. [Google Scholar] [CrossRef]
Dantchev, D.; Valchev, G. Surface integration approach: A new technique for evaluating geometry dependent forces between objects of various geometry and a plate. J. Colloid Interface Sci. 2012, 372, 148–163. [Google Scholar] [CrossRef] [PubMed]
Werner, D.H.; Jones, D.M.; Werner, P.L. The Electromagnetic Fields of Elliptical Torus Knots. IEEE Trans. Antennas Propag. 2001, 49, 980–991. [Google Scholar] [CrossRef]

Figure 1. Graph of orthogonal projection with test points given by six cases.

Figure 2. Graph of orthogonal projection with test points given by three cases.

Figure 3. Graph of orthogonal projection with test points given by five cases.

© 2016 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons by Attribution (CC-BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Li, X.; Wu, Z.; Hou, L.; Wang, L.; Yue, C. The Accurate Method for Computing the Minimum Distance between a Point and an Elliptical Torus. Computers 2016, 5, 4. https://doi.org/10.3390/computers5010004

AMA Style

Li X, Wu Z, Hou L, Wang L, Yue C. The Accurate Method for Computing the Minimum Distance between a Point and an Elliptical Torus. Computers. 2016; 5(1):4. https://doi.org/10.3390/computers5010004

Chicago/Turabian Style

Li, Xiaowu, Zhinan Wu, Linke Hou, Lin Wang, and Chunguang Yue. 2016. "The Accurate Method for Computing the Minimum Distance between a Point and an Elliptical Torus" Computers 5, no. 1: 4. https://doi.org/10.3390/computers5010004

APA Style

Li, X., Wu, Z., Hou, L., Wang, L., & Yue, C. (2016). The Accurate Method for Computing the Minimum Distance between a Point and an Elliptical Torus. Computers, 5(1), 4. https://doi.org/10.3390/computers5010004

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

The Accurate Method for Computing the Minimum Distance between a Point and an Elliptical Torus

Abstract

1. Introduction

2. The Accurate Method for Computing the Minimum Distance between a Point and an Elliptical Torus

3. Conclusions

Acknowledgments

Author Contributions

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI