三維邊界表示法

1、法 5 三維數(shù)據(jù)結(jié)構(gòu)二、三維邊界表示法1、方法原理首先考慮一個(gè)簡(jiǎn)單的四面體應(yīng)如何表示。它是一個(gè)平面多面體，即它的每個(gè)表面均可以看成是一個(gè)平面多邊形。為了做到無(wú)歧義地、有效地表示，需指出它的頂點(diǎn)位置以及由哪些點(diǎn)構(gòu)成邊，哪些邊圍成一個(gè)面等一些幾何與拓?fù)涞男畔?。比較常用的表示一個(gè)平面多面體的方法是采用三張表來(lái)提供這些信息（如圖25-4），這三張表就是：1） 頂點(diǎn)表：用來(lái)表示多面體各頂點(diǎn)的坐標(biāo)；2） 邊表：指出構(gòu)成多面體某邊的兩個(gè)頂點(diǎn)；3） 面表：給出圍成多面體某個(gè)面的各條邊。對(duì)于后兩個(gè)表一般使用指針的方法指出有關(guān)的邊、點(diǎn)存放的位置。vi v v1 2v2v1v1 v41v4 v3v1 v4$3 %圖

2、2-5-4三錐邊界 表示法lx 1_ b k l面表頂點(diǎn)表擴(kuò)充后的邊表為了更快地獲得所需信息，更充分地表達(dá)點(diǎn)、線、面之間的拓?fù)潢P(guān)系，可以把其它一些有關(guān)的內(nèi)容結(jié)合到所使用的表中。圖25-4中的擴(kuò)充后的邊表就是將邊所屬的多邊形信息結(jié)合進(jìn)邊表中以后的形式。這樣利用這種擴(kuò)充后的表，可知某條邊是否為兩個(gè)多邊形的公共邊，如果是，相應(yīng)的兩個(gè)多邊形也立即知道。這是一種用空間換取時(shí)間的方法。是否要這樣做，應(yīng)視具體的應(yīng)用而定，同樣也可根據(jù)需要適當(dāng)?shù)財(cái)U(kuò)充其它兩張表來(lái)提高處理的效率。除了描述它的幾何結(jié)構(gòu)，還要指出該多面體的一些其它特性。例如每個(gè)面的顏色、紋理等等。這些屬性可以用另一個(gè)表獨(dú)立存放。當(dāng)有若干個(gè)多面體時(shí)，還

3、必須有一個(gè)對(duì)象表。每個(gè)多面體在這個(gè)表中列出圍成它的諸面，同樣也可用指針的方式實(shí)現(xiàn)，這時(shí)面表中的內(nèi)容，已不再是只和一個(gè)多面體有關(guān)。2、 特點(diǎn)采用這種分列的表來(lái)表示多面體，可以避免重復(fù)地表示某些點(diǎn)、邊、面，因此一般來(lái)說存貯量比較節(jié)省，對(duì)圖形顯示更有好處。例如，由于使用了邊表，可以立即顯示出該多面體的線條畫，也不會(huì)使同一條邊重復(fù)地畫上兩次?？梢韵胂?，如果表中僅有多邊形表而省卻了邊表，兩個(gè)多邊形的公共邊不僅在表示上要重復(fù)，而且很可能會(huì)畫上兩次。類似地，如果省略了頂點(diǎn)表，那么作為一些邊的公共頂點(diǎn)的坐標(biāo)值就可能反復(fù)地寫出好多次。3、 拓?fù)錂z查對(duì)于比較復(fù)雜的多面體要輸入大量的數(shù)據(jù)。檢查輸入的數(shù)據(jù)是否一致、是

4、否完全，是一項(xiàng)必不可少的工作，這就是通常所說的拓?fù)錂z查。般來(lái)說，在數(shù)據(jù)表中包含的信息越多，輸入時(shí)有錯(cuò)的可能性也越大，但是可用來(lái)檢查是否有錯(cuò)的手段也會(huì)隨之增加。對(duì)上面提及的數(shù)據(jù)結(jié)構(gòu)，至少可以檢查以下諸項(xiàng)：1）頂點(diǎn)表中的每個(gè)頂點(diǎn)至少是兩條邊的端點(diǎn)；2）每條邊至少是一個(gè)多邊形的邊；3）每個(gè)多邊形是封閉的；4）每個(gè)多邊形至少有一條邊是和另一個(gè)多邊形共用的；5）若邊表中包含了指向它所屬多邊形的指針，那么指向該邊的指針必在相應(yīng)的多邊形中出現(xiàn)。這些檢查對(duì)于維護(hù)表示多面體的數(shù)據(jù)庫(kù)的全體一致性是有效的，而復(fù)雜的情況應(yīng)當(dāng)有專門的程序來(lái)檢查。4、應(yīng)用以上討論的只是簡(jiǎn)單的平面多面體的三維邊界表示，但是gis研究的對(duì)象

5、是自然實(shí)體，其三維形狀的復(fù)雜程度難以描述。例如巖石的外表不規(guī)則，組成的平面可有成千上萬(wàn)，如何用三維邊界表示法表示呢？從理論上講，對(duì)任意的三維形體只要它滿足一定的條件，總可找到一個(gè)適合的平面多面體來(lái)近似地表示這個(gè)三維形體，且使誤差保持在一定的范圍之內(nèi)。但是在實(shí)際上，這種逼近受到多方面因素的制約，解決這個(gè)問題的方法也不一而足。通常，這個(gè)問題可以敘述成：要表示某個(gè)三維形體，又僅知道從這個(gè)形體的外表面s0上測(cè)得的一組點(diǎn)p1pn的坐標(biāo)。為了解決這個(gè)問題，首先要為這些點(diǎn)建立起某種關(guān)系。這種關(guān)系被稱為這些點(diǎn)代表的形體結(jié)構(gòu)。可以由一個(gè)圖來(lái)表示，圖的頂點(diǎn)就是這里給定的那組點(diǎn)p1pn, 而圖的邊的給定方式則恰好反映了所設(shè)想的結(jié)構(gòu)。不同的圖，有不同的邊（也就是連接這些頂點(diǎn)的方法不同）, 相應(yīng)地，這個(gè)圖對(duì)應(yīng)的平面多面體也不同，這可由圖25-5來(lái)示意圖 2tt相同的點(diǎn)，不同的形體結(jié)構(gòu)在眾多的結(jié)構(gòu)中，每個(gè)面均是三角形的平面多面體起著很重要的作用（這跟不規(guī)則三角網(wǎng)tin很類似）。即使對(duì)結(jié)構(gòu)加上了這種限制，同一組點(diǎn)仍可得到不同的平面多面體。因此，人們自然會(huì)想到，在這類多面體中