點集圖形重建的算法研究.pdf

1、點集圖形在許多課題中都有涉及，例如，特殊空間的點、數(shù)字照片中的像素、銀河中的星球和空間數(shù)據(jù)等。并且，點集圖形集重建是圖形重建領域的一個非常重要的內(nèi)容。
　　假設平面中有一系列離散的點，這些點僅憑我們的視覺系統(tǒng)是無法感知其所要表達的具體形狀的。本文研究的主要內(nèi)容就是如何由這些離散的點重建出一個我們能夠識別的具體圖形。為了重建出一個具體的圖形，要從這個圖形的凸包開始，一步步將這個圖形的凸包進行凹化，這樣就能夠使更多的點回到邊界上，從而

2、能夠更加接近點集所要表達的真實的圖形。當一個點集是一列不含邊界的離散點的時候，需要建立這個點集的一個凸包邊界。本文利用的是Delaunay三角剖分的方法。顯然，一個點集的凸包邊界，就是這個點集經(jīng)過Delaunay三角剖分之后形成的三角網(wǎng)的一個子集。所以，只要確定介值并刪去多余的邊即可得到這個點集的凸包。除此之外，本文還設計了一個有適當半徑的圓，通過這個圓與點集中的兩點形成的弦來確定這個點集的凸包。當輸入的點集帶有邊界時，就需要對這個點集

3、的邊界進行檢測。本文主要用到的算法是合并算法，分離算法和獨立算法。
　　當一個點集的凸包被構建完成后，就要對這個點集的凸包進行凹化處理。在進行凹化處理的時候，需要刪去已知的邊并利用這條邊的兩端點和點集內(nèi)一點建立兩條新的邊。這就需要在每一步都選取適當?shù)倪吅瓦m當?shù)狞c。在選擇時，本文將已有的就近選擇標準、最長邊選擇標準、等角選擇標準結合起來，得到一個新的選擇標準。最后文章給出這個算法的停止條件，如果滿足條件，則算法停止，如果不滿足，算法