技術領域

本發(fā)明涉及數值計算領域，具體地說是一種為計算機提供點到隱式曲線距離的數值計算方法。

背景技術

點到隱式曲線的距離計算方法在模式識別、幾何建模、計算機視覺、醫(yī)學影像處理等領域具有重要應用價值，也是數值分析、計算機科學、逆向工程等學科的重要研究基礎。由于點到隱式曲線的距離的解析式一般很難得到甚至不可能得到，所以距離的計算通常是數值計算。

設所求距離是點p₀到隱式曲線f(x，y)＝0的距離，點到隱式曲線距離的數值計算通常有局部法和全局法之分。局部法含有一個迭代過程，如牛頓迭代法，它先以迭代方式求出隱式曲線上與p₀達到最小距離的點(稱為足點)，也就是先求解下列關于p的方程的根p^*：

(p-p0)×▿f(p)=0f(p)=0]]>

其中，表示梯度算子，×為矢量叉乘。于是所求距離就是||p^*-p₀||。迭代法收斂速度較快，但經常受奇點和初值選擇的影響，存在不收斂、陷入局部極值點等缺點，且對f(x，y)的光滑性要求較高。全局法則根據隱式函數f(x，y)的某種全局特性對足點進行二維搜索，如文獻“Geometric?constraint?solver?using?multivariate?rational?spline?functions”(Elber，G.and?Kim，M.-S.，In：Proceedings?of?the?Sixth?ACM?Symposium?on?Solid?Modeling?and?Applications，ACM，2001：pp.1-10)和文獻“Computation?of?the?solutions?of?nonlinear?polynomial?systems”(Sherbrooke，E.C.and?Patrikalakis，N.M.，Computer?Aided?Geometric?Design，v10，1993：pp.379-405)所述方法，根據基函數的凸包性質，采用Bézier裁剪方法不斷排除非足點區(qū)域，得到候選足點，最后在這些候選足點中選取與p₀距離最小的點。全局法能保證魯棒計算，但計算量較大，對隱式函數有特殊要求(如凸性)。

此外，還有作為全局方法和局部方法之折中的方法，基本框架仍為迭代法，但每步迭代根據徑向導數搜索下一個足點的估計位置，參見文獻“Robust?Computation?of?Foot?Points?on?Implicitly?Defined?Curves”(Aigner，M.and?Jüttler，B.，In：Mathematical?Methods?for?Curves?and?Surfaces：2004，Nashboro?Press，2005：pp.1-10)。