點到代數曲線最短距離的細分算法

祁佳玳， 壽華好

(浙江工業大學 理學院, 浙江 杭州 310023)

?

點到代數曲線最短距離的細分算法

祁佳玳， 壽華好*

(浙江工業大學 理學院, 浙江 杭州 310023)

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

關鍵詞：代數曲線；最短距離；區間算術；細分算法

0引言

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

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

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

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

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

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

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

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

1點到代數曲線最短距離的細分算法

1.1算法原理

1.2算法步驟

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

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

1.3計算實例

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

2與其他算法的比較

2.1直接計算法

(1)

(2)

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

從計算結果可以看出，改進后算法的計算速度有較大的提升.

2.3拉格朗日乘數法

(3)

2.4離散牛頓法

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

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

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

(4)

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

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

2.6格點法

在點到代數曲線的最短距離問題中，首先需要對代數曲線進行參數化，轉變為參數曲線. 目標函數為

2.7曲線離散成折線法

林意等[12]通過把參數曲線離散成折線，將曲線間Hausdorff距離的計算轉換成折線間Hausdorff距離的計算，進一步轉換成點到線段之間的Hausdorff距離計算.

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

2.8曲線離散成曲線段法

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

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

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

3結束語

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

參考文獻(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].計算機輔助幾何設計與圖形學學報,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]陳小雕，雍俊海，汪國昭.平面代數曲線間最短距離的計算[J].計算機輔助幾何設計與圖形學學報,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].工程圖學學報,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]壽華好，黃永明，閆欣雅，等.兩條代數曲線間Hausdorff距離的計算[J].浙江工業大學學報,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]伍麗峰，陳岳坪，譫炎輝，等.求點到空間參數曲線最小距離的幾種算法[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]林意，薛思騏，郭婷婷.一種參數曲線間Hausdorff距離的計算方法[J].圖學學報，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]廖平.分割逼近法快速求解點到復雜平面曲線最小距離[J].計算機工程與應用,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

文獻標志碼：A

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

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

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

收稿日期：2015-11-06.

DOI:10.3785/j.issn.1008-9497.2016.03.006