基于單調鏈的簡單多邊形距離算法
2007-01-01 00:00:00周之平吳介一張颯兵張少博
計算機應用研究 2007年1期
摘要：簡單多邊形的距離問題是計算機圖形學中的一個研究難點，為了能快速地獲得距離信息，提出一種基于單調鏈的簡單多邊形距離算法。算法先對多邊形邊界進行關于坐標軸的單調鏈分割，然后根據可見性原則確定候選鏈對，再結合層次樹理論和分支限界策略計算鏈對距離以求解多邊形的最近距離。試驗結果表明，該算法性能優于其他同類算法。
關鍵詞：簡單多邊形； 單調鏈； 層次樹； AABB包圍盒； 可見性
中圖法分類號：TP301．6文獻標識碼：A
文章編號：1001－3695(2007)01－0136－04
距離算法是計算機圖形學中的一個研究難點。Chin提出了一種計算多邊形距離的線性算法[1]，該算法通過凸頂點搜索可視鏈來確定凸n邊形P和簡單m邊形Q的最近距離。Nancy提出一種多處理器并行距離算法[2]，其復雜度為O(n log n)，實現起來比較復雜。對于可以用若干凸對象的并集表示的非凸對象，David 等人提出一種基于包圍盒層次樹的距離算法[3]，當兩個物體相隔很近時，需要通過大量的包圍盒預測試和邊對距離計算才能求解最近分離距離。考慮到多邊形凸包之間的位置關系，文獻[4]提出一種用差別鏈配對的多邊形距離算法，這種算法需要對大量的邊對進行距離計算，算法運行效率比較低。為了便于實現和提高算法的效率，本文提出了一種基于單調鏈的多邊形距離算法。
1簡單多邊形分離距離問題描述
本文假定多邊形P，Q的走向為逆時針方向，P，Q分離但Box(P)∩Box(Q)≠Φ。
2基于單調鏈的簡單多邊形距離算法
若將多邊形邊界分割為關于坐標軸單調的鏈的集合，則可以通過搜索互為可見的邊界來確定候選鏈對，再通過求解這些單調鏈對的距離來獲得多邊形P，Q的最近距離。
2．1對象的單調鏈分割
（1)判定多邊形的走向；
（2)將P(Q)分割為左右兩分支；
（3)對于右分支，從P(Q)的最低點出發，沿多邊形走向，逐條邊判定其端點Y的增減性，將增減性相同的組合為一條單調鏈，水平邊單獨作為一條鏈。
算法復雜度為O(n)。
2．2采用可見性原則進行單調鏈配對
因為最近距離點一定在邊界上，所以我們可以設定關于鏈的搜索范圍以確定測試鏈對，通過計算單調鏈的距離來獲得d(P，Q)。
2．3簡單多邊形距離算法實現（MC算法）
根據第2.2節處理過程可知，所有與Ci關聯的鏈CQi都位于Ci的可見區域內，這說明P，Q互為可見的邊界一定包含在這些鏈對中，所以這些鏈對的距離最小值就是d(P，Q)。為了提高算法的效率，將結合包圍盒、層次樹結構和分支限界算法對單調鏈對進行進一步篩選，以減少邊對距離計算量。為此，我們引入了包圍盒最小有向距離概念。
2．3．2MC算法步驟
（1）按第2.1節的規則選定分割方向，對多邊形P，Q進行單調鏈分割。
（2）按第2.2.3節的過程進行單調鏈配對，并將所有單調鏈對存入鏈表List中。
（3）對List中所有鏈對求距離上界U和下界L，按L遞增次序對List進行重新排序。求Umin=min{Ui}，刪除List中L>Umin的元素。
（4）選取List中L最小的元素List(i*)，用層次樹方法求單調鏈距離dmin（具體過程參見文獻[3]）。
（5）若Umin＞dmin，令Umin=dmin，刪除List(i*)及List中下界大于Umin的元素。
（6）重復過程（4）和過程（5），直至List為空為止，所得到的Umin就是多邊形P，Q的最近距離。
3復雜度分析與性能比較
3．1預處理復雜度分析
3．2性能比較
筆者對MC算法用Visual C++ 6.0程序進行實現，該算法在P4 1.7GHz CPU，256MB內存下的Windows 2000系統環境中運行，對一對平面鋸齒狀多邊形P，Q距離計算1 000次，就平均運行時間而論，與文獻[3，4]算法進行比較，如圖6~圖7所示。為表述方便，稱文獻[3]算法為LUB算法，文獻[4]算法為GSS算法。
從圖6試驗數據可知，當P，Q的邊距離很近，CHull(P)∩CHull(Q)≠Φ 時，MC算法性能比LUB算法提高了14%~23%，與GSS算法相比，提高了41%~64%。
從圖7試驗數據可知，當P，Q的邊距離很近，CHull(P)CHull(Q)時，MC算法性能比LUB算法提高了13%~25%，與GSS算法相比，提高了33%~60%。
MC算法效率的提高主要歸功于兩個原因：①設定搜索區域，采用可見性原則進行鏈的篩選，減少了大量的無關邊對測試；②采用了基于層次樹結構的分支限界策略。由于研究對象是星形多邊形，GSS從凸包構建角度來搜索關聯鏈，必須對一對差別鏈上的所有邊對測試，這大大增加了邊對測試量，從而影響了算法的效率。LUB算法利用包圍體距離來逐步篩選層次樹分支，當P，Q距離很近時，包圍體的重疊程度很高，存在大量距離很近的邊對，必須經過大量的包圍體測試來篩選無關邊，因為沒有考慮邊之間的遮擋關系，所以與MC算法相比，LUB算法需要進行更多的邊對距離計算。
4結論
本文提出了一種基于單調鏈的多邊形分離距離算法(MC算法)。MC算法首先對多邊形進行單調鏈分割，然后根據鏈的搜索范圍初步確定關聯鏈對，再利用可見性篩選原則和分支限界策略減少鏈對測試，逐步計算單調鏈的距離以求取多邊形的最近距離。試驗結果表明， MC算法可行、有效，其性能優于同類算法。雖然預處理算法的最壞復雜度為O(nM+mN)，但由于其運算過程相對簡單，所以其花費的代價是可接受的。今后，我們將對一般多邊形的穿透深度和三維多面體模型的距離計算進行深入研究。
參考文獻：
［1］Chin F， Wang C A. Optimal Algorithms for the Intersection and the Minimum Distance Problems between Planar Polygons[J]. IEEE Transactions on Computers， 1983，C32(12)：12031207.
［2］Nancy M A. Determining the Separation of Simple Polygons[J]. Journal of Computational GeometryApplications， 1994，4(4)：457474.
［3］David E J， Elaine C. Minimum Distance Queries for Polygonal and Parametric Models[R]. Technical Report UUCS97003， University of Utah，1997.
［4］Yang Chun Cheng， Zhang Qing Pu. A Closest Distance Computation Method for Simple Polygons Considering Geometry Shape Similarity[J]. ACTA Geodaetica et Cartographica Sinica， 2000，32(4)： 311318.
作者簡介：
周之平(1976)，男，江西樂安人，博士研究生，主要研究方向為虛擬裝配、計算機圖形學；
吳介一 (1941)，男，江蘇南京人，教授，博導，主要研究方向為計算機網絡、先進制造技術；
張颯兵(1964)， 女，江蘇南京人，高級工程師，主要研究方向為集成制造環境；
張少博(1964)， 男，陜西西安人，博士研究生，主要研究方向為計算機網絡。
注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
