祁佳玳， 壽華好

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

?

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

祁佳玳， 壽華好*

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

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

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

0引言

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

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

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

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

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

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

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

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

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

1.1算法原理

1.2算法步驟

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

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

1.3計(jì)算實(shí)例

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

2與其他算法的比較

2.1直接計(jì)算法

(1)

(2)

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

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

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

(3)

2.4離散牛頓法

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

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

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

(4)

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

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

2.6格點(diǎn)法

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

2.7曲線離散成折線法

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

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

2.8曲線離散成曲線段法

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

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

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

3結(jié)束語

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

參考文獻(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ì)算機(jī)輔助幾何設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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]陳小雕，雍俊海，汪國(guó)昭.平面代數(shù)曲線間最短距離的計(jì)算[J].計(jì)算機(jī)輔助幾何設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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]余正生，樊豐濤，王毅剛.點(diǎn)到隱式曲線曲面的最小距離[J].工程圖學(xué)學(xué)報(bào),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ì)算[J].浙江工業(yè)大學(xué)學(xué)報(bào),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]伍麗峰，陳岳坪，譫炎輝，等.求點(diǎn)到空間參數(shù)曲線最小距離的幾種算法[J].機(jī)械設(shè)計(jì)與制造，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ì)算方法[J].圖學(xué)學(xué)報(bào)，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]廖平.分割逼近法快速求解點(diǎn)到復(fù)雜平面曲線最小距離[J].計(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

中圖分類號(hào)：TP 391.7

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

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

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

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

收稿日期：2015-11-06.

DOI:10.3785/j.issn.1008-9497.2016.03.006