點(diǎn)集圖形重建的算法研究.pdf

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

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

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