點到代數(shù)曲線最短距離的細(xì)分算法

祁佳玳， 壽華好

(浙江工業(yè)大學(xué) 理學(xué)院, 浙江 杭州 310023)

?

點到代數(shù)曲線最短距離的細(xì)分算法

祁佳玳， 壽華好*

(浙江工業(yè)大學(xué) 理學(xué)院, 浙江 杭州 310023)

摘要：距離計算在計算機(jī)輔助幾何設(shè)計與圖形學(xué)領(lǐng)域有著廣泛的應(yīng)用. 為了有效計算點到代數(shù)曲線的最短距離，提出了一種基于區(qū)間算術(shù)和區(qū)域細(xì)分的細(xì)分算法.利用四叉樹數(shù)據(jù)結(jié)構(gòu)對給定區(qū)域進(jìn)行細(xì)分，用區(qū)間算術(shù)計算細(xì)分后所有像素點到給定點的距離區(qū)間，得到最小距離區(qū)間.該方法的優(yōu)勢在于在得到任意精度的點到代數(shù)曲線最短距離的同時，亦得到了該結(jié)果的最大誤差限.為進(jìn)一步提高速度，還對算法進(jìn)行了改進(jìn).

關(guān)鍵詞：代數(shù)曲線；最短距離；區(qū)間算術(shù)；細(xì)分算法

0引言

距離計算有著廣泛的應(yīng)用，如計算機(jī)圖形學(xué)及游戲中的碰撞檢測、CAD/CAM中的干涉檢測、幾何造型中點到曲線距離的查詢等.此外，距離計算還廣泛應(yīng)用于計算機(jī)仿真、觸覺仿真、機(jī)器人路徑規(guī)劃等.關(guān)于距離計算的研究亦從未中斷過.

CHANG 等[1]基于剔除技術(shù)提出了一種有效且穩(wěn)定的方法，計算2條Bézier曲線及2張Bézier曲面之間的最短距離.該方法充分利用控制頂點凸包的最近點對，提出了一種新的節(jié)點分割方法.MA等[2]通過將一系列圓錐球作為包圍盒，提出了有效計算2張管道曲面距離的方法：用圓錐球包圍盒之間的距離近似為2張管道曲面的距離.

陳小雕等[3]首先將得到的一些區(qū)間的單向Hausdorff距離作為Hausdorff距離的下界，然后消除上界比該下界小的子區(qū)間，提出用幾何裁剪法計算2條B-spline曲線的Hausdorff距離，并提出了Hausdorff距離是否發(fā)生在兩曲線端點的判斷條件，該條件把2條曲線間Hausdorff距離的計算轉(zhuǎn)換成點和曲線的最大最小距離，具有較高的穩(wěn)定性.陳小雕等[4]在穩(wěn)定的曲線、曲面分裂技術(shù)和基于常半徑滾動球的幾何裁剪算法的基礎(chǔ)上，提出了計算Bézier曲線曲面間最近距離的混合算法：首先判斷曲線段或曲面片是否包含最近點，此條件可摒棄大部分不包含最近點的曲線段或曲面片；然后判斷最近點是否落在曲線的端點或曲面的邊界曲線上，將曲線/曲面間的距離計算問題轉(zhuǎn)換成點/曲面或曲線/曲線之間的距離問題，大大降低了問題的復(fù)雜度，提高了計算效率. CHEN 等[5]提出了用裁剪圓算法計算點到NURBS曲線的最短距離.以曲線外一定點與該曲線的距離平方作為目標(biāo)函數(shù)，以該定點為裁剪圓圓心，獲得裁剪圓初始半徑，并利用裁剪圓排除裁剪圓外部的曲線段，有效提高了算法的效率和穩(wěn)定性. 陳小雕等[6]根據(jù)一條曲線上的最近點是另一條曲線的等距曲線與該曲線的切點這一幾何特征，基于等距思想提出了計算2條平面代數(shù)曲線間最近距離的方法. 該方法同樣可用于計算代數(shù)曲線和參數(shù)曲線之間的最短距離.

LENNERZ等[7]提出了計算邊界是二次曲線的二次曲面片之間最小距離的方法.將距離計算問題轉(zhuǎn)換為次數(shù)不超過8的單變量多項式的求解問題. KIM[8]根據(jù)2張曲面間最近點法向平行的幾何特性，提出了計算管道曲面與簡單曲面間最小距離的算法. 管道曲面的脊柱曲線和半徑函數(shù)確定了曲面的特征圓，該特征圓上點的法向形成的一個頂點為脊柱曲線上的點，軸與脊柱曲線上點的切線平行的圓錐，得到該管道曲面與簡單曲面間的垂線. 由此建立方程并求解，即可得到最小距離.

余正生等[9]基于隱式曲線曲面的幾何特性，分別利用點到曲線的最短距離矢量與曲線上對應(yīng)點的切向量垂直以及定點到隱式曲面的最短距離矢量與曲面上對應(yīng)點的法向量平行的事實，得到相應(yīng)的方程組. 而對于方程組的求解則應(yīng)用了計算復(fù)雜度較低的離散牛頓法，提高了算法的穩(wěn)定性.

壽華好等[10]基于區(qū)間算術(shù)和細(xì)分算法計算2條代數(shù)曲線間的Hausdorff距離.首先利用四叉樹數(shù)據(jù)結(jié)構(gòu)和區(qū)間算術(shù)對代數(shù)曲線進(jìn)行離散，找到包含這2條代數(shù)曲線的全部像素點的集合，然后利用區(qū)間算術(shù)計算離散化之后的矩形的Hausdorff距離，最后得到距離區(qū)間，取該區(qū)間的中點為2條代數(shù)曲線間Hausdorff距離的近似值，且誤差不超過該區(qū)間長度的一半.

伍麗峰等[11]提出基于幾何特征的快速迭代法、格點法計算點到空間參數(shù)曲線的最小距離，并進(jìn)行了分析比較. 林意等[12]提出把參數(shù)曲線離散成折線，將參數(shù)曲線間Hausdorff距離的計算轉(zhuǎn)換成折線間Hausdorff距離的計算. 廖平等[13]通過將參數(shù)曲線離散成曲線段，提出了點到平面曲線最小距離的分割逼近算法.

本文利用區(qū)間算術(shù)和細(xì)分算法計算點到代數(shù)曲線的最短距離區(qū)間，將該區(qū)間的中點作為點到代數(shù)曲線的最短距離的近似值，同時得到了相應(yīng)的最大誤差限. 與已有的算法相比，本算法在得到距離近似值的同時亦得到了誤差限，而且理論上精度可以無限高，當(dāng)然精度越高，花費的時間也越長.

1點到代數(shù)曲線最短距離的細(xì)分算法

1.1算法原理

1.2算法步驟

Step3利用四叉樹方法，過中心點將該矩形平面區(qū)域分成4個小矩形，再對每個小矩形區(qū)域重復(fù)step1，直到得到的矩形長、寬都小于等于給定的條件ε為止，如果此時還存在排除不掉的矩形區(qū)域，則把它們保存在result1中；

Step4考慮result1中的所有矩形區(qū)域，若曲線過該矩形區(qū)域的2條邊，即認(rèn)為曲線穿過該矩形區(qū)域，可以去掉對最小距離計算沒有作用的矩形區(qū)域，保留曲線穿過的矩形區(qū)域；

1.3計算實例

從例1和例2可以看出，當(dāng)終止條件ε無限小時，所得到的點到代數(shù)曲線的最短距離可以無限接近于精確值，誤差可達(dá)任意小.

2與其他算法的比較

2.1直接計算法

(1)

(2)

2.2利用四叉樹解方程組(本文算法的改進(jìn))

從計算結(jié)果可以看出，改進(jìn)后算法的計算速度有較大的提升.

2.3拉格朗日乘數(shù)法

(3)

2.4離散牛頓法

而代數(shù)曲線是一種特殊的隱式曲線，因此該算法同樣適用于點到代數(shù)曲線最短距離的計算.

2.5基于幾何特征的快速迭代法

代數(shù)曲線在一定條件下可以表示成參數(shù)曲線，因此該算法也可應(yīng)用于求解點到代數(shù)曲線的最短距離.

(4)

通過編程實現(xiàn)，選取ε=0.05，當(dāng)選取參數(shù)u=2.42時，得到的最短距離為1.524 6，運行時間為0.043 000 s；當(dāng)選取參數(shù)u=2.43時，得到的最短距離為1.521 4，運行時間為0.044 000 s；當(dāng)選取參數(shù)u=2.435時，得到的最短距離為1.520 3，運行時間為0.058 000 s；當(dāng)選取參數(shù)u=2.437時，得到的最短距離為1.520 0，運行時間為0.057 000 s；當(dāng)選取參數(shù)u=2.437 7時，得到的最短距離為1.519 9，運行時間為0.052 000 s；當(dāng)選取參數(shù)u=2.438時，得到的最短距離為1.519 9，運行時間為0.053 000 s.當(dāng)選取參數(shù)u=3時，得到的最短距離為3.629 9，運行時間為0.007 000 s.

雖然該算法可以得到比較好的結(jié)果，但對初始點的要求比較苛刻，若初始點選取不當(dāng)，得到的結(jié)果可能會陷入局部極值，此外，誤差也無法得到.

2.6格點法

在點到代數(shù)曲線的最短距離問題中，首先需要對代數(shù)曲線進(jìn)行參數(shù)化，轉(zhuǎn)變?yōu)閰?shù)曲線. 目標(biāo)函數(shù)為

2.7曲線離散成折線法

林意等[12]通過把參數(shù)曲線離散成折線，將曲線間Hausdorff距離的計算轉(zhuǎn)換成折線間Hausdorff距離的計算，進(jìn)一步轉(zhuǎn)換成點到線段之間的Hausdorff距離計算.

通過代數(shù)曲線參數(shù)化及把參數(shù)曲線離散成折線，點到參數(shù)曲線的最短距離轉(zhuǎn)換成點到線段的距離. 過該點向線段作垂線，若垂足在線段內(nèi)，則點到線段的最短距離就是該點到垂足的距離，否則，即為該點到線段兩端點的距離的最小值. 對例1進(jìn)行編程實現(xiàn)，取0為初始點，當(dāng)取得步長為0.5時，得到的最短距離為1.520 5，運行時間為0.012 000s；當(dāng)取得步長為0.25時，得到的最短距離為1.520 3，運行時間為0.029 000s；當(dāng)取得步長為0.1時，得到的最短距離為1.520 1，運行時間為0.052 000s；當(dāng)取得步長為0.05時，得到的最短距離為1.520 0，運行時間為0.091 000s；當(dāng)取得步長為0.02時，得到的最短距離為1.519 9，運行時間為0.174 000s,誤差無法得到.

2.8曲線離散成曲線段法

廖平[13]提出了把參數(shù)曲線離散成曲線段，首先計算定點到每個曲線段端點的距離，記錄其中的最小值所對應(yīng)的點，然后把該點相鄰的2個曲線段等分成4份，再記錄該點到曲線段端點距離最小值所對應(yīng)的點，如果該點相鄰的2個曲線段2個端點間的參數(shù)方向間距小于計算精度，計算結(jié)束；否則繼續(xù)將該點相鄰的2個曲線段等分為4份，重復(fù)上述步驟.

首先把代數(shù)曲線參數(shù)化，對例1進(jìn)行編程實現(xiàn)，取計算精度為0.1，當(dāng)把曲線等分成20個曲線段時，得到的最小距離為1.520 7，運行時間為0.004 000s；當(dāng)把曲線等分成30個曲線段時，得到的最小距離為1.520 7，運行時間為0.014 000s；當(dāng)把曲線等分成50個曲線段時，得到的最小距離為1.520 7，運行時間為0.017 000s；當(dāng)把曲線等分成100個曲線段時，得到的最小距離為1.520 0，運行時間為0.028 684s,誤差無法得到.

以上實例可以看出，本算法可以有效計算點到代數(shù)曲線的最短距離，其優(yōu)勢在于得到最短距離近似值的同時得到了該近似值的最大誤差限. 這對解決實際問題至關(guān)重要.

3結(jié)束語

基于區(qū)間算術(shù)和四叉樹區(qū)域細(xì)分提出了一種計算點到代數(shù)曲線最短距離的細(xì)分算法，該算法不僅可以有效計算點到代數(shù)曲線的最短距離，同時還可得到該結(jié)果的最大誤差限. 另外，根據(jù)終止條件ε的不同，可以得到不同的細(xì)分結(jié)果，且隨著ε趨于無窮小，所得結(jié)果的誤差可以達(dá)到任意小，但計算時間會相對長一些，這也是本算法的不足之處. 為了進(jìn)一步提高算法的計算速度，對算法進(jìn)行了改進(jìn)，從實例中可以看出，改進(jìn)后計算速度有較大提升.

參考文獻(xiàn)(References)：

[1]CHANG Jungwoo, CHIO Yiking, KIM Myungsoo, et al. Computation of the minimum distance between two Bézier curves/surfaces [J]. Computer & Graphics,2011,35(3):677-684.

[2]MA Yanpeng, TU Changhe, WANG Wenping. Distance computation for canal surfaces using cone-sphere bounding volumes [J]. Computer Aided Geometric Design,2012,29(5):255-264.

[3]CHEN Xiaodiao, MA Weiyin, XU Gang . Computing the Hausdorff distance between two B-spline curves[J]. Computer Aided Design,2010,42(12):1197-1206.

[4]陳小雕，王毅剛，徐崗.Bézier曲線曲面間最近距離的幾何裁剪算法[J].計算機(jī)輔助幾何設(shè)計與圖形學(xué)學(xué)報,2009,21(10):1404-1411.

CHEN Xiaodiao, WANG Yigang, XU Gang. Geometric pruning method for computing minimum distance between a Bézier curves and a Bézier surfaces [J]. Journal of Computer-Aided Design & Computer Graphics,2009,21(10):1404-1411.

[5]CHEN Xiaodiao, YONG Junhai, WANG Guozhao, et al. Computing the minimum distance between a point and a NURBS curve [J]. Computer-Aided Design,2008,40(10/11):1051-1054.

[6]陳小雕，雍俊海，汪國昭.平面代數(shù)曲線間最短距離的計算[J].計算機(jī)輔助幾何設(shè)計與圖形學(xué)學(xué)報,2008,20(4):459-463.

CHEN Xiaodiao, YONG Junhai, WANG Guozhao, et al. Computing the minimum distance between two planar algebraic curves [J]. Journal of Computer-Aided Design & Computer Graphics,2008,20(4):459-463.

[7]CHRISTIAN L, ELMAR S. Efficient distance computation for quadratic curves and surfaces [C] // Proceeding of Geometric Modeling and Processing. New York: IEEE Computer Society Press,2002:60-69.

[8]KIM Kujin. Minimum distance between a canal surface and a simple surface [J]. Computer-Aided Design,2003,35(10):871-879.

[9]余正生，樊豐濤，王毅剛.點到隱式曲線曲面的最小距離[J].工程圖學(xué)學(xué)報,2005(5):74-79.

YU Zhengsheng, FAN Fengtao, WANG Yigang. The minimum distance between a point and an implicit curve/surface [J]. Journal of Engineering Graphics,2005(5):74-79.

[10]壽華好，黃永明，閆欣雅，等.兩條代數(shù)曲線間Hausdorff距離的計算[J].浙江工業(yè)大學(xué)學(xué)報,2013,41(5):574-577.

SHOU Huahao, HUANG Yongming, YAN Xinya, et al. Computation of the Hausdorff distance between two algebraic curves [J]. Journal of Zhejiang University of Technology,2013,41(5):574-577.

[11]伍麗峰，陳岳坪，譫炎輝，等.求點到空間參數(shù)曲線最小距離的幾種算法[J].機(jī)械設(shè)計與制造，2011,32(9):15-17.

WU Lifeng, CHEN Yueping, ZHAN Yanhui, et al. Algorithms on calculating minimum distance between point and spatial parametric curves [J]. Machinery Design & Manufacture,2011,32(9):15-17.

[12]林意，薛思騏，郭婷婷.一種參數(shù)曲線間Hausdorff距離的計算方法[J].圖學(xué)學(xué)報，2014，35(5):704-708.

LIN Yi, XUE Siqi, GUO Tingting. A method of calculating the Hausdorff distance between parametric curves [J]. Journal of Graphics,2014,35(5):704-708.

[13]廖平.分割逼近法快速求解點到復(fù)雜平面曲線最小距離[J].計算機(jī)工程與應(yīng)用,2009,45(10):163-164.

LIAO Ping. Fast calculating minimum distance between point and complex curve with subdivision approximating algorithm [J]. Computer Engineering and Application,2009,45(10):163-164.

[14]SHOU Huahao, LIN Hongwei, RALPH M , et al. Modified affine arithmetic is more accurate than centered interval arithmetic or affine arithmetic [J]. Lecture Notes in Computer Science,2003,2768:355-365.

QI Jiadai , SHOU Huahao
(CollegeofScience,ZhejiangUniversityofTechnology,Hangzhou310023,China)
A subdivision algorithm for computing the minimum distance between a point and an algebraic curve. Journal of Zhejiang University(Science Edition), 2016,43(3):286-291

Abstract:The distance computation has wide applications in computer-aided geometric design and graphics. A subdivision algorithm based on the interval arithmetic and quadtree data structure for computing the minimum distance between a point and an algebraic curve is proposed . A quadtree data structure is adopted during the subdivision of the give domain, and the interval arithmetic is used to compute the interval distances between the pixel on the algebraic curve and the given point. Compared with other methods, this method can obtain a close approximate value of the minimum distance between a point and an algebraic curve at any precision, while conducting the error estimation at the same time. An improved algorithm is also proposed to further accelerate the calculation speed.

Key Words:algebraic curves; minimum distance; interval arithmetic; subdivision algorithm

中圖分類號：TP 391.7

文獻(xiàn)標(biāo)志碼：A

文章編號：1008-9497(2016)03-286-06

作者簡介：祁佳玳(1992-)，ORCID:http://orcid.org/0000-0003-4909-854X,女，碩士研究生，主要從事計算機(jī)輔助幾何設(shè)計與圖形學(xué)研究.*通信作者，ORCID:http://orcid.org/0000-0002-8991-337X,E-mail:shh@zjut.edu.cn.

基金項目：國家自然科學(xué)基金資助項目(61572430，61272309，61472366).

收稿日期：2015-11-06.

DOI:10.3785/j.issn.1008-9497.2016.03.006