平面簡單閉合曲線離散采樣與重建算法

范麗鵬， 王麗英， 龐明勇

(南京師范大學教育技術系，江蘇 南京 210097)

平面簡單閉合曲線離散采樣與重建算法

范麗鵬， 王麗英， 龐明勇

(南京師范大學教育技術系，江蘇 南京 210097)

提出一種魯棒的平面簡單閉合曲線離散采樣與重建算法。算法分為采樣過程和重建過程兩部分。采樣部分首先對平面閉合曲線均勻取點，然后計算各點到曲線所圍平面區域中軸的最近距離，最后根據所求距離確定采樣間隔，獲取采樣點集；重建部分首先構建采樣點集的Delaunay三角剖分，然后從得到的三角形中選擇邊構建初始化圖形，最后通過修改該圖形獲得重建圖形。實驗表明算法得到的采樣點較少且能反映曲線的局部幾何特性，重建圖形能夠較好地表示原閉合曲線的形狀及走向。

曲線重建；離散采樣；無序點集；平面圖形

在圖形建模與幾何處理領域中，有關三維形體離散采樣與曲面重建的研究已開展得非常深入[1-2]。相對而言，平面曲線采樣與重建的研究工作大多集中于傳統的樣條曲線方法[3-4]，而基于計算幾何方法的研究文獻相對較少；另一方面，在圖形圖像技術的現實應用中，有許多操作涉及對各類曲線進行采樣與重建等計算[5]。因此對基于計算幾何方法的曲線采樣與重建進行研究，具有重要的意義。

目前，對平面曲線進行離散采樣的方法主要有3種：①柵格法[6]，首先將曲線所在的平面區域柵格

化，然后將曲線與柵格線的交點作為離散采樣點。由此得到的采樣點通常數據量較大，且采樣點集不能很好地反映曲線的局部幾何特性；②預測投影法[7]，即從曲線的某點開始，根據曲線在該點處的曲率大小，沿該點的切線方向前進一小段得到預測點，然后將預測點投影到曲線上得到采樣點。由于該方法包括了一個投影過程，所以計算量較大；③ε-采樣法[8]，其處理對象為平面閉合曲線，采樣條件為：設曲線上一點到采樣點的最近距離為 d1，到曲線所圍平面區域中軸的最近距離為 d2。若一采樣點集使曲線上任意一點滿足 d1＜ε× d2，則其為所求點集，ε取值范圍為 0 ＜ε＜ 1。由于該方法設定了參數ε，對于不同的圖形均需要找到合適的ε值，才能滿足采樣條件，因此獲取的采樣點集充滿了不確定性。

平面曲線重建算法主要包括：文獻[9]提出了基于最小二乘法的平滑曲線重建，該方法通過對噪聲采樣點集進行濾噪來實現平滑曲線的重建，其主要關注點是如何過濾采集數據中的噪聲；Amenta等[8]提出了基于β骨架與Voronoi圖的Crust算法，該算法先求取原始點集的Voronoi圖頂點，再對原始點集以及得到的頂點集進行Delaunay三角剖分，最后通過選取三角剖分中三角形的邊來進行曲線重建。該方法對原始點集的密度要求嚴格；Dey等[10]對該算法進行了改進，降低了對原始點集密度的要求。上述算法的重建對象是簡單的閉合光滑曲線，Althaus和Mehlhorn[11]進一步對算法進行了擴展，使之能夠處理開放曲線，Dey和Wenger在文獻[12]中給出一種能夠處理多尖角圖形的算法變種。上述算法均需設定采樣參數，即對于不同的圖形均需找到合適的參數值，才能獲得適合其重建算法的采樣點集。

本文給出一種針對平面簡單閉合曲線的采樣與重建算法。其中采樣過程不需要設定參數，并且所得采樣點集較少且能較好地重建原始曲線。

1 算法梗概

本文算法由采樣與重建構成。采樣過程是由平面簡單閉合曲線(圖1(a))得到表示該曲線的稀疏點集(圖1(b))；重建則由上述采樣過程所得到的采樣點集重建逼近原曲線的重構圖形(圖1(c))。

采樣過程的主要步驟：

(1) 計算曲線所圍平面區域的中軸。中軸上任意一點，與被采樣曲線均存在兩個或兩個以上距離相等的點[13]。

(2) 對曲線均勻取點，并計算各點的局部特征大小。所謂的局部特征大小，是指點到中軸的最近距離[14]，如圖2(a)、(b)所示。

圖1 曲線的采樣與重建

圖2 矩形與圓的中軸、特征大小及采樣點

(3) 獲取采樣點。依據上述所求的局部特征大小，確定采樣間隔，獲取采樣點集，圖2(c)中圓心點即為采樣點。

(4) 添加采樣點。圖2(c)中兩圓相交點為可增加點。最終所得采樣點集只需從可增加點中選擇部分點添加到上述采樣點集中即可。

曲線重建過程的主要步驟：

(1) 逐次連接采樣點集(圖3(a))中距離最近的點，使其連成一個閉合圖形，并且使得該圖形中每個點至少連接兩條邊，如圖3(b)所示。

(2) 求點集的凸包，如圖3(c)所示，并求取圖3(b)的邊界，如圖3(d)中實線所示。其中，虛線為刪除的上述圖形(圖3(b))中的邊，實線為所求邊界；邊界內部的點，即圖3(d)中兩條虛線相交的點，不屬于邊界點。

圖3 曲線重構示意圖

(3) 修改上述邊界中鄰邊個數大于2的點，使得其鄰邊個數為2或0，如圖3(e)所示。圖3(d)中圓內的點即為鄰邊個數大于2的點。

(4) 將鄰邊個數為0的點連接到修改后的邊界中，使其鄰邊個數為2，如圖3(f)所示。圖3(e)中圓內的點即為鄰邊個數為0的點。

2 采樣過程

2.1 計算中軸

本文采用文獻[15]的方法提取平面封閉區域的中軸。該方法提出了一種基于Voronoi圖[16]的中軸提取方法，利用Voronoi圖頂點的連線模擬中軸。由于Voronoi圖的頂點為圖中邊的交點，且邊為曲線上相鄰點連線的垂直平分線，所以Voronoi圖頂點屬于中軸點。進而將平面閉合曲線看作是一些點的集合，當點集足夠密時，其Voronoi圖頂點的連線即可逼近曲線所圍區域的中軸。

2.2 計算局部特征大小

對原始曲線(圖4(a))均勻取點，然后計算各點到曲線所圍平面區域的中軸(圖4(b)中紫線)的最近距離，并將該距離記為該點的局部特征大小。由圖2(c)所示，在曲線上曲率較大的地方，點的局部特征較小，而在曲線較為平滑的地方局部特征較大。因此，根據曲線上所取各點的局部特征大小可獲得較少且能表示曲線局部幾何特性的采樣點集。

2.3 獲取采樣點

2.4 增加采樣點

由于所得采樣點不能較好地重建曲線，因此需要添加采樣點。添加條件：以任意采樣點p為圓心，以該點到其相鄰采樣點的距離為半徑畫圓，若在圓內或圓上存在與p不相鄰的采樣點q，則在點p與該相鄰采樣點之間添加可增加點。為了使得添加的點數量較少，可通過設置一個數值，使得當p與q之間的采樣點與可增加點的個數小于該數值時，不執行操作。若該數值設置過大，則使得添加點過少，而不能重建圖形，若該數值設置過小，則會添加多余的點。因此需要不斷測試尋找到一個合適的數值，測試方法：首先設數值為1，即 q點不存在，然后獲取采樣點集，再對采樣點集進行重建，若重建圖形能夠很好地逼近原曲線，則繼續增加數值，直到所生成的采樣點集不能很好地重建曲線為止，則取前一數值為所求數值。由于文中采樣算法和重建算法是順次執行的，因此對于不同圖形，可由計算機自動地判定合適的取值大小。實驗表明，多數圖形的數值可取6，且所得到的采樣點集更為稀疏且能很好地重建原曲線，圖4(e)中紅色的點即為所增加的點。

圖4 采樣過程

3 重建過程

3.1 構建初始化圖

首先構建采樣點集的Delaunay三角剖分[17]，由于得到的Delaunay三角形集合中存在較多的邊，所以需要從中選取部分邊來連接采樣點集進而重建圖形。依據格式塔[18]的連續性和近似性原理可知，重建圖形為閉合圖形，每個點鄰邊個數均為2，且所有邊長的和最小。在構建采樣點集的初始化圖過程中，涉及到閉合回路的問題，因此在圖5(a)中，展示了非閉合回路的示意圖，圖5(b)中展示了閉合回路的示意圖。

初始狀態時，所有采樣點均沒有相鄰邊，如圖6(a)所示。首先從Delaunay三角形集合(圖6(b))中選擇長度最短的邊，若該邊存在鄰邊個數小于2的端點，則選擇該邊來連接相應的采樣點，否則舍棄；然后再從剩余邊中選擇長度最短的邊進行上述判

斷；最后重復執行上述操作，直到所有采樣點鄰邊個數均不小于2為止。此時，所得圖形中不存在鄰邊個數小于2的點，但是該圖形可能為非閉合圖形，如圖5(a)所示，因此需要再次添加邊，操作步驟為：先從Delaunay三角形集合中選擇長度最短的邊，若該邊連接兩個不連接的閉合回路(圖5(b)中最長的線)，則將該邊添加到上述非閉合圖形，并判斷連接后所得圖形是否為閉合圖形，若不是，則繼續選擇剩余邊中最短的邊，并重復執行上述操作，直到整個圖形為閉合圖形為止，如圖5(b)所示。將所得圖形記為圖形A，如圖6(c)中陰影部分所圍圖形所示。

圖5 非閉合和閉合圖形示意圖

3.2 構建初始化圖的邊界

由于圖形A中存在鄰邊個數大于2的點，因此需要對其進行修改。為了更好地解決這個問題，可以先修改圖形A的邊界，然后再修改其內部的點。通過刪除圖形A外部的Delaunay三角形可以求得圖形A的邊界，圖6(c)中空白區域的三角形即為圖形A外部的三角形。

為了找到圖形A外部的Delaunay三角形，可以先求得圖形A的凸包，即一個最小的多邊形，其所有點集均在該多邊形內部或邊上，并且點集中任意兩點之間的連線均在多邊形內部或邊上[19]，如圖6(d)中實線所示。獲得采樣點集的凸包后，逐一刪除凸包內部包含凸包的邊或新添加的且不為圖形A的邊的三角形，可獲得圖形A的邊界圖形B，如圖6(e) 中陰影部分所圍圖形所示。

3.3 修改邊界上的點

由于圖形B中可能存在鄰邊個數大于2的點，如圖6(e)所示，所以需要對圖形B進行修改，使得圖形B中所有點的鄰邊個數為2或0。

首先找到位于圖形B外部且包含鄰邊個數大于2的點的Delaunay三角形，記為集合T2。對于圖3(c)中的點來說，圖7(a)中包含邊為虛線的三角形即為T2中的三角形。由于存在多個這樣的三角形，且添加三角形的先后順序會影響重建的最終效果，因此可通過對T2中的每個三角形計算被添加后圖形B中所有邊的長度和的變化量，進而確定T2中三角形被添加的先后順序。通常優先添加變化量最小的三角形。添加三角形的過程如圖7(a)～(c)所示。添加三角形后，可能會出現3種情況：①不滿足T2要求的三角形仍然在集合T2中；②滿足T2要求的三角形不在集合T2中；③T2中一些三角形的變化量發生了變化。所以要分別對這3種情況進行分析，并針對相應的情況對T2進行刪除、添加或修改的操作，直到集合T2為空為止。所得圖形記為圖形C，如圖6(f)中陰影部分所圍圖形所示。

3.4 修改邊界內部的點

由于圖形C以及圖形B的內部存在鄰邊個數為0的點，所以需要對其進行修改，使其鄰邊個數為2。

首先在圖形C內部的Delaunay三角形中找到一邊在C上且該點鄰邊個數為0的三角形，記為集合T0，圖7(d)中包含邊為虛線的三角形即為T0中的三角形。由于T0中存在較多的三角形，且刪除T0中三角形的先后順序會影響最終的重建效果，所以需要對T0中的每個三角形計算被刪除后圖形C中所有邊的長度和變化量，并依據變化量的大小確定T0中各三角形被刪除的先后順序。通常優先刪除變化量最小的三角形。刪除三角形過程如圖7(d)～(e)所示。刪除三角形后，會出現2種情況：一種是不符合集合T0要求的三角形仍然存在；另一種是符合集合T0要求的三角形不在。所以要分別對這2種情況進行分析，并針對上述情況對集合T0進行刪除或添加。

當集合T0為空時，即獲得重建圖形，如圖6(g)中陰影部分所圍圖形所示。

圖7 添加和刪除三角形過程

4 實現與結果

本算法在PC機上運用VC6.0和OpenGL實現了采樣過程和曲線重建過程。實驗結果如圖8所示。其中小松鼠和小白兔在增加采樣點時，計算機判定其最適合的數值為6，而海豚的數值為1，它們均展示了由閉合曲線獲得采樣點集，以及由采樣點集重建圖形的過程。可以看出，圖中的采樣點集能較好地反映原曲線的局部幾何特性，在距離較近但不相連接處采樣比較密集，而在其他處采樣比較稀疏。最終所得圖形均能夠較好地表示原曲線的形狀及走向。

圖8 松鼠、兔子、海豚采樣及重建過程

5 結 束 語

本文給出的基于平面簡單閉合曲線的采樣與重建算法，成功地實現了平面簡單閉合曲線的采樣及重建過程。大量實驗表明，該算法能夠獲得更為稀疏且能反映曲線局部幾何特性的采樣點集，并且利用該點集能較好地重建出原曲線。由于本文算法只是針對簡單閉合曲線進行采樣與重建，而對于未閉合以及更為復雜的曲線不具有很好的適用性，因此對于上述類型的曲線以及高維空間曲線的采樣與重建是今后需要考慮的問題。

[1] 厲玉蓉, 張彩明, 董付國. 三角網格上五次齊次代數曲面的重構[J]. 計算機輔助設計與圖形學學報, 2008, 20(9)： 1186-1190.

[2] 龐旭芳, 龐明勇. 點云模型自適應增加采樣點算法[J].小型微型計算機系統, 2010, 11(11)： 2265-2271.

[3] 黃童心, 王文珂, 張 慧, 等. 基于場分布的平面散亂點集B樣條曲線重建算法[J]. 工程圖學學報, 2010, 31(2)： 73-83.

[4] 張 嫻, 張志毅, 田素壘, 等. 基于曲率分析的三次Bezier 曲線采樣方法的研究[J]. 計算機工程與應用, 2013, 49(5)： 160-162.

[5] 駱 沛, 吳壯志, 夏春和, 等. 基于 e1范數最小化的非流形曲線族重構[J]. 計算機學報, 2013, 36(9)： 1917-1928.

[6] 譚昌柏, 周來水, 安魯陵, 等. 逆向工程中基于密集數據點的輪廓線重建技術[J]. 華南理工大學學報, 2005, 33(5)： 32-37.

[7] Akkouche S, Galin E. Adaptive implicit surface polygonization using marching triangles [J]. Computer Graphics Forum, 2001, 20(2)： 67-80.

[8] Amenta N, Bern M, Eppstein D. The crust and the β-skeleton： combinatorial curve reconstruction [J]. Graphical Models and Image Processing, 1998, 60(2)：125-135.

[9] 龐明勇, 盧章平. 局部數據集與噪聲數據曲線的平滑過濾[J]. 礦山測量, 2001, (4)： 24-27.

[10] Dey T K, Mehlhorn K, Ramos E A. Curve reconstruction：connecting dots with good reason [C]//ACM. SOCG. Hong Kong, China, 2000： 229-244.

[11] Althaus E, Mehlhorn K. TSP-based curve reconstruction in polynomial time [C]//ACM/SIAM. SODA. San Francisco, CA, USA, 2000： 686-695.

[12] Dey T K, Wenger R. Fast reconstruction of curves with sharp corners [J]. International Journal of Computational Geometry & Applications, 2002, 12(5)： 353-400.

[13] Blum H. A transformation for extracting new descriptors of shape [J]. Models for the Perception of Speech and Visual Form, 1967, 19(5)： 362-380.

[14] Ruppert J. A new and simple algorithm for quality 2-dimensional mesh generation [C]//ACM/SIAM. SODA. Austin, USA, 1993： 83-92.

[15] Karimipour F, Ghandehari M. Voronoi-based medial axis approximation from samples： issues and solutions [M]. Transactions on Computational Science XX. Berlin Heidelberg： Springer, 2013： 138-157.

[16] Aurenhammer F. Voronoi diagrams： a survey of a fundamental geometric data structure [J]. ACM Computing Surveys, 1991, 23(3)： 345-405.

[17] 何 俊, 戴 浩, 謝永強, 等. 一種改進的快速Delaunay三角剖分算法[J]. 系統仿真學報, 2006, 18(11)： 3055-3057.

[18] Ohrhallinger S, Mudur S P. Interpolating an unorganized 2D point cloud with a single closed shape [J]. Computer-Aided Design, 2011, 43(12)： 1629-1638.

[19] 劉 斌, 王 濤. 一種高效的平面點集凸包遞歸算法[J].自動化學報, 2012, 38(8)： 1375-1379.

Discretely Sampling and Reconstructing Simple Planar Closed Curves

Fan Lipeng, Wang Liying, Pang Mingyong
(Department of Educational Technology, Nanjing Normal University, Nanjing Jiangsu 210097, China)

A robust algorithm is proposed for discretely sampling continuous planar curves and reconstructing the curves from the sampled point sets. The algorithm covers two processes, sampling and reconstruction. In the sampling part, the points are evenly obtained from a given planar closed curve, and then the distances are calculated between each point and the medial-axis of the planar area surrounded by the closed curve. Subsequently, the sampling intervals are decided by the distances and finds the sampling points. In the reconstruction part, a Delaunay triangulation is first built for the sampled points, and then edges are selected from the triangulation to build the initialize graph. Finally, the reconstructed curve is obtained by modifying the graph to a new version. Experiments show that the point sets sampled by our algorithm are locally adapted to the local geometric characteristics of the curves, and the reconstructed curves can approximate the original curves well.

curve reconstruction; discretely sampling; scattered points; 2D graphics

TP 391. 41

A

2095-302X(2015)04-0511-05

2015-01-14；定稿日期：2015-02-25

國家自然科學基金資助項目(41271383，60873175)；江蘇省現代教育技術研究課題資助項目(2014-R-33356)；江蘇省高校自然科學基金資助項目(11KJB520008)；江蘇高校優勢學科建設工程資助項目

范麗鵬(1993–)，女，河南南陽人，碩士研究生。主要研究方向為數字幾何處理。E-mail：funnypower@126.com

龐明勇(1968–)，男，安徽淮南人，教授，博士。主要研究方向為幾何建模與數字幾何處理。E-mail：panion@netease.com