形體的表示及其數(shù)據(jù)結(jié)構(gòu)

1、關(guān)于形體的表示及其數(shù)據(jù)結(jié)構(gòu)第1頁，共81頁，2022年，5月20日，14點37分，星期三第一節(jié) 二維形體的表示 二維圖形的邊界表示 折線法和帶樹法 折線法就是用多段線段形成的折線去逼近曲線 折線表示曲線應(yīng)該解決的關(guān)鍵問題是:如何恰當(dāng)?shù)卮_定曲線上一系列點,使之在某些判定準(zhǔn)則下達(dá)到最優(yōu)。 第2頁，共81頁，2022年，5月20日，14點37分，星期三帶樹法 帶樹是一棵二叉樹,樹的每個結(jié)點對應(yīng)一個矩形帶段,這樣每個結(jié)點可由八個字段組成,前六個字段描述矩形帶段,后二個是指向兩個子結(jié)點的指針, 即矩形帶段的起點是(xb,yb),終點是(xe,ye)。相對從起點到終點的連線,矩形有兩邊與之平行,兩邊與之垂

2、直,平行兩邊與之距離分別為wl和wr。 第3頁，共81頁，2022年，5月20日，14點37分，星期三第4頁，共81頁，2022年，5月20日，14點37分，星期三 設(shè)要表示的曲線是由經(jīng)過適當(dāng)選取已確定的一組離散點P0,P1,Pn序列給出,則生成表示曲線的分辨率為w0的帶樹的算法,可簡略描述如下:1. 找出由起點P0,終點Pn確定的矩形帶段,其中包含P0至Pn的全部點,構(gòu)造此矩形帶段的對應(yīng)結(jié)點并令為根。2. 找出P0至Pn之間距離連線P0Pn為最遠(yuǎn)的點Pk,然后對P0至Pk和Pk至Pn這兩組點分別做與步1中相同的構(gòu)造矩形帶段及對應(yīng)結(jié)點的操作,產(chǎn)生的兩個結(jié)點,分別是根的左右子結(jié)點。3. 反復(fù)執(zhí)行

3、上述操作,直到所產(chǎn)生結(jié)點的w=wl+wr w0。這樣的結(jié)點是葉結(jié)點。 第5頁，共81頁，2022年，5月20日，14點37分，星期三 設(shè)表示曲線有5個點(3,7)(9,12),(15,4),(18,5),(20,7) ,取分辨率w0=1,則上述算法構(gòu)造的帶樹第6頁，共81頁，2022年，5月20日，14點37分，星期三 以不同的分辨率顯示用帶樹表示的曲線 設(shè)給出允許的分辨率為w*,表示曲線的帶樹的分辨率為w0,并設(shè)w0w*,則顯示算法可簡略描述如下: 從根結(jié)點開始,若當(dāng)前正考查結(jié)點的W=wl+wr w*,則顯示該結(jié)點對應(yīng)的矩形帶段;若不然,即W w*則轉(zhuǎn)去分別考查該結(jié)點的左右兩個子結(jié)點,對子結(jié)

4、點做同樣的處理。左右子結(jié)點都被顯示的結(jié)點就認(rèn)為是被顯示了,按此看法,顯示帶樹表示的曲線就是顯示帶樹的結(jié)點。 第7頁，共81頁，2022年，5月20日，14點37分，星期三 帶樹表示的曲線求交 兩個矩形帶段S1和S2的位置關(guān)系有如下三種:(1) 不相交。(2) 良性相交,即S1的與起點至終點連線平行的兩條邊都與S2相交,S2的與起點至終點連線平行的兩條邊也都與S1相交。(3) 可能性相交,這時不是良性相交,但也不是不相交。第8頁，共81頁，2022年，5月20日，14點37分，星期三第9頁，共81頁，2022年，5月20日，14點37分，星期三 設(shè)表示要求交兩曲線的帶樹己構(gòu)造得足夠精確,即在樹葉

5、一層,來自不同帶樹的矩形帶段或是不相交或是良性相交,而沒有可能性相交出現(xiàn)。 兩樹T1和T2表示的兩條曲線是否相交的算法,可以簡略敘述如下: 若T1和T2對應(yīng)的矩形帶段互不相交,那么它們代表的曲線不相交; 若T1和T2對應(yīng)的矩形帶段良性相交,那么它們代表的曲線相交; 若T1和T2對應(yīng)的矩形帶段可能性相交,且T1的面積大于或等T2的面積,那么分別執(zhí)行T2與T1的左右兩個兒子結(jié)點的相交性檢查。 第10頁，共81頁，2022年，5月20日，14點37分，星期三 若T1的面積小于T2的面積,則把它們位置對換一下再如上進(jìn)行兩個檢查。若兩個檢查的結(jié)果都是不相交,則認(rèn)為所表示曲線不相交;若兩個檢查中有一個是良

6、性相交,則認(rèn)為所表示曲線相交;若不是上述兩情形,即出現(xiàn)可能性相交,則對可能性相交的兩個矩形帶段中面積較大者,取其對應(yīng)結(jié)點的兩個子結(jié)點,如此進(jìn)行可直到樹葉那一層。 實踐表明用帶樹方法表示曲線對提高計算效率是有幫助的。另外兩個帶樹對并、交等運算是封閉的,與用象素陣列來表示圖形的方法比較空間需求也算是節(jié)省的。 第11頁，共81頁，2022年，5月20日，14點37分，星期三平面圖形的四叉樹表示方法 假定一個平面圖形是黑白的二值圖形,即組成圖形象素陣列的僅有黑色象素值1,白色象素值0,設(shè)表現(xiàn)圖形的象素陣列由2n2n個象素組成。 表示該圖形的四叉樹結(jié)構(gòu)可以如下形成:圖形顯然包括2n2n的正方形中，這個正

7、方形是四叉樹的根結(jié)點。 若圖形整個地占據(jù)這個正方形,則圖形就用該正方形表示,否則將該正方形均分為四個小正方形，每個小正方形邊長為原正方形邊長的一半.它們是根結(jié)點的四個子結(jié)點,可編號為0,1,2,3。第12頁，共81頁，2022年，5月20日，14點37分，星期三 再考查每個小正方形,若整個被圖形占據(jù),則標(biāo)記相應(yīng)結(jié)點為1,可稱為黑結(jié)點。若整個與圖形不相交,則標(biāo)記相應(yīng)結(jié)點為0，可稱為白結(jié)點。 若不是上述兩情形，即與圖形部分相交，則稱相應(yīng)結(jié)點是灰結(jié)點并將其一分為四。當(dāng)再分生成小正方形邊長達(dá)到一個象素單位時，再分終止，此時一般應(yīng)將仍是灰結(jié)點的改為黑結(jié)點，如此形成了平面圖形的四叉樹表示 第13頁，共81

8、頁，2022年，5月20日，14點37分，星期三第14頁，共81頁，2022年，5月20日，14點37分，星期三 四叉樹的存儲結(jié)構(gòu)，即規(guī)則方式、線性方式和一對四方式，相應(yīng)的四叉樹也就稱為規(guī)則四叉樹、線性四叉樹和一對四式四叉樹。 規(guī)則四叉樹是用五個字段的記錄來表示樹中的每個結(jié)點，其中一個用來描述結(jié)點的特性，即是灰、黑、白三類結(jié)點中的哪一種。其余四個用于存放指向四個子結(jié)點的指針。 線性四叉樹以某一預(yù)先確定的次序遍歷四叉樹形成一個線性表結(jié)構(gòu) 。 RAabcdBCDefgh。其中R表示根，字母右上角加表示是灰結(jié)點。 第15頁，共81頁，2022年，5月20日，14點37分，星期三 一對四式四叉樹的存儲

9、結(jié)構(gòu) 每個結(jié)點有五個字段，其中四個字段用來描述該結(jié)點的四個子結(jié)點的狀態(tài)，另一個結(jié)點存放指向子結(jié)點記錄存放處的指針。四個子結(jié)點對應(yīng)的記錄是依次連續(xù)存放的。 第16頁，共81頁，2022年，5月20日，14點37分，星期三 為節(jié)省存貯空間,有兩個途徑可以采取。一個是增加計算量；另一個途徑是在記錄中再增加一個字節(jié),一分為四,每個子結(jié)點對應(yīng)2位,表示它的子結(jié)點在指針指向區(qū)域中的偏移。 第17頁，共81頁，2022年，5月20日，14點37分，星期三第二節(jié) 三維幾何模型 幾何元素 形體的模型主要指的就是包含圖形信息所形成的模型。 形體本身的構(gòu)造有一定的層次性，低層部分組合構(gòu)成上一層部分，而上一層部分組合

10、又可以構(gòu)成更高一層的部分，依此類推可形成多層結(jié)構(gòu)。其中，每一層中的部分，我們把它有稱為幾何元素。 第18頁，共81頁，2022年，5月20日，14點37分，星期三點 它是0維幾何元素，有端點、交點、切點、孤立點等形式。 曲線、曲面的應(yīng)用中會涉及到三種類型的點：型值點 相應(yīng)曲線、曲面必然經(jīng)過的點?？刂泣c 相應(yīng)曲線、曲面不一定經(jīng)過的點，僅用于確定位置和形狀。插值點 在型值點之間插入的一系列點，用于提高曲線曲面的輸出精度。 第19頁，共81頁，2022年，5月20日，14點37分，星期三 不同的空間中點的表示方式 一維空間中用一元組t表示； 二維空間中用二元組x,y或x(t),y(t)表示； 三維空

11、間中用三元組x,y,z或x(t),y(t),z(t)表示； 點是幾何造型中的最基本的元素，曲線、曲面和其它形體都可以用有序的點集描述。 用計算機存儲、管理、輸出形體的實質(zhì)就是對點集及其連接關(guān)系的處理。 第20頁，共81頁，2022年，5月20日，14點37分，星期三邊 邊是一維幾何元素，是兩個鄰面（正則形體）或多個鄰面（非正則形體）的交界。邊分直線邊和曲線邊。直線邊由起點和終點兩端點確定；曲線邊由一系列型值點或控制點表示，也可以用顯示、隱式方程描述。環(huán) 環(huán)是有序有向邊（直線段或曲線段）組成的面的封閉邊界。環(huán)中的邊不能相交，相鄰兩條邊共享一個端點。環(huán)有內(nèi)外之分，確定面的最大外邊界的環(huán)稱之為外環(huán)，

12、通常其邊按逆時針方向排序。而把確定面中內(nèi)孔或凸臺邊界的環(huán)稱之為內(nèi)環(huán)，其邊相應(yīng)外環(huán)排序方向相反，通常按順時針方向排序。第21頁，共81頁，2022年，5月20日，14點37分，星期三面 面是二維元素，是形體上一個有限、非零的區(qū)域，它由一個外環(huán)和若干個內(nèi)環(huán)所界定。面有方向性，一般用其外法向量作為該面的正向。若一個面的外法向量向外，此面為正；否則，為反向面。體 體是三維幾何元素，由封閉表面圍成的空間，它是歐氏空間R3中非空、有界的封閉子集，其邊界是有限面的并集。在實際應(yīng)用中，要求形體是正則形體，即形體上任意一點的足夠小的鄰域在拓?fù)渖蠎?yīng)是一個等價的封閉圓。不滿足上述要求的形體稱為非正則形體。存在懸面、

13、懸邊的形體是非正則形體。 第22頁，共81頁，2022年，5月20日，14點37分，星期三體素 體素是可以用有限個尺寸參數(shù)定位和定型的體，常有下面三種定義形式。一組單元實體 長方體、圓柱體、圓錐體、球體。掃描體 由參數(shù)定義的一條（一組）截面輪廓線沿一條（一組）空間參數(shù)曲線作掃描運動而產(chǎn)生的形體。用代數(shù)半空間定義的形體，在此半空間中點集可定義(x,y,z)|f(x,y,z) 0此處的f應(yīng)是不可約的多項式。形體的層次結(jié)構(gòu) 點邊環(huán)面外殼形體。 第23頁，共81頁，2022年，5月20日，14點37分，星期三 在幾何造型中最基本的幾何元素是點（V）、邊(E)、面(F),這三種元素一共有九種連接關(guān)系 第

14、24頁，共81頁，2022年，5月20日，14點37分，星期三線框、表面及實體表示 常用的多面體表示法是三表表示法，即采用三個表:頂點表,用來存放多面體各頂點的坐標(biāo);邊表,指出哪兩個頂點之間有多面體的邊；面表，指出哪些邊圍成了多面體的表面。 任意多面體容易得到它的三表表示,但任意三張表卻不一定表示了一個真實的多面體。這里必須滿足的條件至少有以下幾項:頂點表中的每個頂點至少是三邊的端點;邊表中的每條邊是兩個多邊形面的公共邊；每個多邊形面是封閉的等等。 第25頁，共81頁，2022年，5月20日，14點37分，星期三第26頁，共81頁，2022年，5月20日，14點37分，星期三xyz100110

15、010000101111011001122334415667788515263748110592116103127114981256783214頂點表面表邊表第27頁，共81頁，2022年，5月20日，14點37分，星期三 空間正二十面體V20, 的三表表示。 引人一個正數(shù)0,它滿足二次方程2-1=0,因此=1/2(1+ )1.618034。 XYZ第28頁，共81頁，2022年，5月20日，14點37分，星期三編號xyz編號xyz110123-101213-001-12431-10-1 014-0-13201-2110330-1221-0340-1-第29頁，共81頁，2022年，5月20日

16、，14點37分，星期三邊編號邊編號111，131621，32212，141722，33321，231822，34422，241923，31531，332023，32632，342124，33711，212224，34811，222331，11邊編號邊編號912，232431，121012，242532，131113，212632，141213，222733，111314，232833，121414，242934，131521，313034，14第30頁，共81頁，2022年，5月20日，14點37分，星期三面編號面編號17，23，151125，6，2928，17，271230，6，26311，

17、16，251311，1，7429，28，12148，1，1259，19，24159，2，13628，21，101614，2，10726，20，131719，3，15814，22，301816，3，20927，5，231917，4，211024，5，282022，4，18第31頁，共81頁，2022年，5月20日，14點37分，星期三第32頁，共81頁，2022年，5月20日，14點37分，星期三三維實體表示方法 從用戶角度來看，形體以特征表示和構(gòu)造的實體幾何表示比較適宜；從計算機對形體的存儲管理和操作運算角度看，以邊界表示最為實用。 1 構(gòu)造的實體幾何法 構(gòu)造的實體幾何(CSG:Constru

18、ctive Solid Geometry)法是指任意復(fù)雜的形體都可以用簡單形體(體素)的組合來表示。 形體的CSG表示可看成是一棵有序的二叉樹，稱為CSG樹。其終端結(jié)點或是體素，如長方體、圓錐等；或是剛體運動的變換參數(shù)，如平移參數(shù)Tx等；非終端結(jié)點或是正則的集合運算，一般有交、并、差運算；第33頁，共81頁，2022年，5月20日，14點37分，星期三或是剛體的幾何變換，如平移、旋轉(zhuǎn)等。 采用BNF范式可定義CSG樹若下： :=| CSG樹是無二義性的，但不是唯一的，其定義域取決于所用體素以及所允許的幾何變換和正則集合運算算子。 CSG表示的優(yōu)點： 數(shù)據(jù)結(jié)構(gòu)比較簡單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管

19、理比較容易；第34頁，共81頁，2022年，5月20日，14點37分，星期三每個CSG表示都和一個實際的有效形體所對應(yīng)；CSG表示可方便地轉(zhuǎn)換成Brep表示，從而可支持廣泛的應(yīng)用； 比較容易修改CSG表示形體的形狀。CSG表示的缺點：產(chǎn)生和修改形體的操作種類有限，基于集合運算對形體的局部操作不易實現(xiàn)； 由于形體的邊界幾何元素(點、邊、面)是隱含地表示在CSG中，故顯示與繪制CSG表示的形體需要較長的時間。第35頁，共81頁，2022年，5月20日，14點37分，星期三并第36頁，共81頁，2022年，5月20日，14點37分，星期三2 特征表示 特征表示是從應(yīng)用層來定義形體，因而可以較好地表達(dá)

20、設(shè)計者的意圖，為制造和檢驗產(chǎn)品和形體提供技術(shù)依據(jù)和管理信息。從功能上看可分為形狀、精度、材料和技術(shù)特征。 形狀特征：體素、孔、槽、鍵等 精度特征：形位公差、表面粗糙度等； 材料特征：材料硬度、熱處理方法等； 技術(shù)特征：形體的性能參數(shù)和特征等。 形狀特征單元是一個有形的幾何實體，是一組可加工表面的集合。如采用長、寬、高三尺寸表示的長方體；采用底面半徑及高度表示的圓柱體均是可選用的形狀特征單元。 第37頁，共81頁，2022年，5月20日，14點37分，星期三形狀特征單元的BNF范式可定義如下： ：=|;：=長方體|圓柱體|球體|圓錐體|棱錐體|棱柱體|棱臺體|圓環(huán)體|楔形體|圓角體|；：=并|交

21、|差|放；：=外圓角|內(nèi)圓角|倒角。 第38頁，共81頁，2022年，5月20日，14點37分，星期三第39頁，共81頁，2022年，5月20日，14點37分，星期三3 邊界表示 邊界表示詳細(xì)記錄了構(gòu)成形體的所有幾何元素的幾何信息及其相互連接關(guān)系拓?fù)潢P(guān)系，便于直接存取構(gòu)成形體的各個面、面的邊界以及各個頂點的定義參數(shù)，有利于以面、邊、點為基礎(chǔ)的各種幾何運算和操作。 形體的邊界表示就是用面、環(huán)、邊、點來定義形體的位置和形狀。例如，一個長方體由六個面圍成，對應(yīng)有六個環(huán)，每個環(huán)由四條邊界定義，每條邊又由兩個端點定義。而圓柱體則由上頂面、下底面和圓柱面所圍成，對應(yīng)有上頂面圓環(huán)、下底面圓環(huán)。 第40頁，共

22、81頁，2022年，5月20日，14點37分，星期三Brep表示的優(yōu)點是： 表示形體的點、邊、面等幾何元素是顯式表示的，使得繪制Brep表示形體的速度較快，而且比較容易確定幾何元素間的連接關(guān)系； 對形體的Brep表示可有多種操作和運算。Brep表示的缺點是： 數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲空間，維護(hù)內(nèi)部數(shù)據(jù)結(jié)構(gòu)的程序比較復(fù)雜； 修改形體的操作比較難以實現(xiàn)； Brep表示并不一定對應(yīng)一個有效形體，即需要有專門的程序來保證Brep表示形體的有效性、正則性等。 第41頁，共81頁，2022年，5月20日，14點37分，星期三八叉樹 假設(shè)要表示的形體V可以放在一個充分大的正立方體C內(nèi),C的邊長為2n,形

23、體V C ,它的八又樹表示可以遞歸定義為: 八叉樹每個結(jié)點與C的一個子立方體對應(yīng)，樹根就和C本身對應(yīng)。如果V=C,那么V八叉樹僅有樹根。如果VC,則將C均分為八個子立方體,每個子立方體對應(yīng)根結(jié)點的一個子結(jié)點。只要某個子立方體不是完全空白或完全被V所占據(jù),它就要被八等分,從而它對應(yīng)的結(jié)點也有了八個子結(jié)點。這樣的遞歸判斷及可能分割一直進(jìn)行,直到結(jié)點對應(yīng)的立方體或完全空白,或完全被占據(jù),或其大小已是預(yù)先規(guī)定的體素大小.第42頁，共81頁，2022年，5月20日，14點37分，星期三 這時對它與V之交作一定的“舍入”,使體素或認(rèn)為是空白,或認(rèn)為是被V占據(jù)的。這里所謂的體素,就是指被分割后得到的小立方體

24、。 通常稱對應(yīng)立方體被形體V完全占據(jù)的結(jié)點為黑結(jié)點,完全不占據(jù)的為白結(jié)點,部分被占據(jù)的為灰結(jié)點。 存貯結(jié)構(gòu), 有常規(guī)的、線性的、一對八式的八叉樹等等。第43頁，共81頁，2022年，5月20日，14點37分，星期三 八叉樹方法的主要優(yōu)點在于,可以非常方便地實現(xiàn)形體的集合運算 。 八叉樹表示的三維形體的幾何變換 比例變換 旋轉(zhuǎn)變換 相對通過原點的一條任意方向的直線做旋轉(zhuǎn)任意角度的旋轉(zhuǎn)變換。 構(gòu)成原形體的直立的正立方體經(jīng)繞原點任意軸線旋轉(zhuǎn)任意角度后, 一般都成為斜置的。為了使變換后形體的八叉樹仍對應(yīng)一系列直立的正立方體,必須對被斜置立方體部分占據(jù)體素做出選擇,即或認(rèn)為是占據(jù),為黑結(jié)點,或認(rèn)為不占據(jù)

25、,為白結(jié)點,這就必然帶來一定的誤差。而且執(zhí)行多次變換后,誤差積累會大到產(chǎn)生嚴(yán)重的錯誤。 第44頁，共81頁，2022年，5月20日，14點37分，星期三 第一項措施是保持一個原始的八叉樹做為參考的源樹。設(shè)指定了一次變換R1,接著又要做變換R2,可以計算出復(fù)合變換R=R1R2,然后對原始的八叉樹做一次變換。這樣來避免誤差的積累。 第二項措施是為了盡量減少舍入誤差,可以規(guī)定一個當(dāng)前正要重建的八叉樹,如果它的最底層葉結(jié)點對應(yīng)的體素是部分地為顯示對象所占據(jù)，那么當(dāng)且僅當(dāng)這個體素的中心位于某個黑變換后立方體內(nèi)時,這個體素才被規(guī)定為黑,否則就規(guī)定為白。這樣規(guī)定使得一般不會產(chǎn)生原來不存在的孔洞，而不這樣規(guī)定

26、,例如簡單地規(guī)定部分被占據(jù)的體素都為白,則可能在做450左右旋轉(zhuǎn)時原來黑立方體變換為部分占據(jù)若干體素而被指定為白,在變換后形體中間出現(xiàn)斷裂。 第45頁，共81頁，2022年，5月20日，14點37分，星期三第46頁，共81頁，2022年，5月20日，14點37分，星期三第47頁，共81頁，2022年，5月20日，14點37分，星期三 設(shè)己采取了上述兩項措施,已知形體變換前的八叉樹表示T1,己計算出 要做的復(fù)合變換R,要確定變換后形體的八叉樹表示T2,可以寫出如下的算法框架：1. 遍歷形體原來的八叉樹T1,對遇到的每個黑結(jié)點,做下述步2。2. 對遇到黑結(jié)點對應(yīng)的正立方體做相應(yīng)變換,得它新的一般來

27、說是斜置的新位置。若這位置已超出定義八叉樹的充分大正立方體C之外,報告出錯;否則執(zhí)行下述的步3。3. 從要計算求出的目標(biāo)樹T2的根開始,檢查2中確定的處于新位置立方體與T2中結(jié)點對應(yīng)的直立的正立方體是否相交,分以下三種情況進(jìn)行處理: 第48頁，共81頁，2022年，5月20日，14點37分，星期三(1) 不相交,說明正考查直立正立方體未被占據(jù),可保持為白結(jié)點,不做處理。(2) 直立的正立方體整個被占據(jù),即它在變換后斜置立方體內(nèi),置對應(yīng)結(jié)點為黑結(jié)點。(3) 在上述兩條均不成立時,生成當(dāng)前結(jié)點的八個子結(jié)點,對八個子結(jié)點對應(yīng)的八個直立子立方體,依次再遞歸執(zhí)行步3。如果最終這八個結(jié)點被標(biāo)上同樣特性,比

28、方為黑結(jié)點,則應(yīng)再刪掉這八個子結(jié)點而把它們的共同父結(jié)點置為黑。 算法中,主要工作是檢查某個直立的正立方體與一個斜置的正立方體是否相交,。對所有黑結(jié)點對應(yīng)正立方體處理相同,使得操作可以并行進(jìn)行。第49頁，共81頁，2022年，5月20日，14點37分，星期三線性八叉樹 在對立方體做八等分時,按一致的方式, 對分出的子立方體進(jìn)行編號。若再分共進(jìn)行n層，則每個結(jié)點可以用n位的八進(jìn)制數(shù)的數(shù)串來表示,數(shù)串從左至右,第一位對應(yīng)第一次劃分，第二位對應(yīng)第二位劃分，依此類推。據(jù)此整個八叉樹就可以根據(jù)對其做深度第一遍歷而依次列出的黑結(jié)點的編號序列來表示 。 前圖所示三維形體,其線性八叉樹表示是: 0 x,10,1

29、2,13,14,2x,4x,6x,7x 第50頁，共81頁，2022年，5月20日，14點37分，星期三求并運算 C1UC2 兩棵線性八叉樹:C1=122,123,301,302,303,305,307C2=12x,300,302,304,306 將C2的各結(jié)點依次插入到C1的適當(dāng)位置,使插入后編號漸增這一性質(zhì)保持不變。當(dāng)C2中結(jié)點可以包含C1中若干結(jié)點時,則取而代之。另外,如果插入后可以進(jìn)行結(jié)點壓縮,也應(yīng)該立即進(jìn)行:C1UC2=12x,300,301,302,303,304,305,306,307 =12x,30 x 第51頁，共81頁，2022年，5月20日，14點37分，星期三八叉樹表示

30、形體的顯示 當(dāng)觀察位置是x10,y10時,最可能被遮擋看不見的是編號2的子立方體,全部依次排出可以是26034715 第52頁，共81頁，2022年，5月20日，14點37分，星期三 zl0,y10 優(yōu)先級26034715。前圖表示形體的線性八叉樹0 x,10,12,13,14,2x,4x,6x,7x 按結(jié)點應(yīng)顯示次序排出的序列就是:2x,6x,Ox,4x,7x,12,10,13,14 z1 y1 x1 優(yōu)先級000735612400037125604005174306200153074260000260347150000004216537第53頁，共81頁，2022年，5月20日，14點37

31、分，星期三第三節(jié) 分形 分形的概念 三分康托(Cantor)集 設(shè)E0是閉區(qū)間0,1,即E0是滿足0 x1的實數(shù)x組成的點集;E1是E0去掉中間1/3之后的點集,即E1是兩個閉區(qū)間0，1/3和1/3，2/3;E2是分別去掉E1中兩個區(qū)間的中間1/3之后的點集,即E2已經(jīng)是四個閉區(qū)間。此過程要繼續(xù)進(jìn)行,Ek是2k個長度為1/3k的閉區(qū)間組成的點集。三分康托集F是屬于所有的Ek的點組成的集,即 。 F可以看成是集序列Ek當(dāng)k趨于無窮時的極限。只能畫出k取定時的某個Ek。當(dāng)k充分大時,Ek是對F的很好的近似的表現(xiàn) 第54頁，共81頁，2022年，5月20日，14點37分，星期三第55頁，共81頁，2

32、022年，5月20日，14點37分，星期三 三分康托集是區(qū)間0,1中的可以展成以3為底的幕級數(shù)的下面形式的數(shù)組成的:a13-1+a23-2+a33-3 其中ai的取值限制為0或2,不取1。為看清這一事實,注意從E0得到E1時,去掉的是ai=1的數(shù),從E1得E2時,去掉的是a2=1的數(shù),并以此類推。 三分康托集具有的一些值得注意的特征,這些特征對許多其它的分形也是大體上適合的。(1) F是自相似的。E1的兩個區(qū)間0，1/3，1/3，2/3的每一個,其內(nèi)部F的部分與F整體相似,相似比為1/3。第56頁，共81頁，2022年，5月20日，14點37分，星期三(2) F具有“精細(xì)結(jié)構(gòu)”，即它包含有任意

33、小比例的細(xì)節(jié)。 (3) F的實際定義是簡單的和明確的。 (4) 傳統(tǒng)的幾何學(xué)很難描述F的性質(zhì),因為F不是滿足某些簡單條件的點的軌跡,也不是任何簡單的方程的解的集合。(5) F的局部幾何性質(zhì)也很難描述,在它的每點附近都有大量被各種不同間隔分開的其它點。 (6) 按傳統(tǒng)幾何學(xué)中的長度概念,F的長度為零。就是說,盡管從不可數(shù)集合這點上說F是一個相當(dāng)大的集,但它卻沒有長度,或者說長度不能對F的形狀或大小提供有意義的描述。第57頁，共81頁，2022年，5月20日，14點37分，星期三von Koch曲線 第58頁，共81頁，2022年，5月20日，14點37分，星期三 稱集合F是分形,即認(rèn)為它具有下面

34、典型的性質(zhì):(1)F具有精細(xì)的結(jié)構(gòu)，即有任意小比例的細(xì)節(jié)。 (2) F是如此的不規(guī)則以至它的整體和局部都不能用傳統(tǒng)的幾何語言來描述。(3) F具有某種自相似的形式,可能是近似的或是統(tǒng)計的。(4) 一般地,F的分形維數(shù)大于它的拓?fù)渚S數(shù)。 (5) 在大多數(shù)令人感興趣的情形下,F以非常簡單的方法定義,可能由迭代產(chǎn)生。 第59頁，共81頁，2022年，5月20日，14點37分，星期三 考慮一個簡單的幾何圖形,取一個邊長為1的正方形,若每邊擴大2倍,則正方形面積放大4倍,其數(shù)學(xué)表達(dá)式為22=4,這是2維圖形。對3維圖形,如考慮邊長為1的立方體,令每邊長放大2倍,則立方體體積擴大8倍,其數(shù)學(xué)表達(dá)式為23=

35、8。 類似地,對一個Df維的幾何對象,若每邊長擴大L倍,則這個幾何對象相應(yīng)地放大K倍,歸納前述結(jié)果,Df,L,K三者間的關(guān)系式應(yīng)為:LDf=K 解出Df,有:Df=lnK/lnL 這里Df不必是整數(shù)。這就是Hausdorff引人的維數(shù)概念,可以稱為Hausdorff維數(shù)。 第60頁，共81頁，2022年，5月20日，14點37分，星期三 假定有一個單位正方形,把它每邊三等分得九個小的正方形,九個小正方形面積總和是原單位正方形面積,即9(1/3)2=1?，F(xiàn)在我們把Df維的幾何對象等分為N個小的幾何圖形,則每個小圖形每維縮小為原來的r倍,而N個小圖形的總和應(yīng)有NrDf=1。 這時解出 ,有: 容易

36、看出式(1)和(2)本質(zhì)上是相同的,即這樣引入的也是Hausdorff維數(shù) 第61頁，共81頁，2022年，5月20日，14點37分，星期三 von Koch曲線,每次分為4個小圖形,每個小圖形縮小1/3倍,故其Hausdorff維數(shù) 為： 分形一般算法 規(guī)則分形的生成算法。對算法的輸入是事先給定的一個整數(shù)k、源形E0及生成規(guī)則,算法操作步驟如下: 第62頁，共81頁，2022年，5月20日，14點37分，星期三1.初始化i0,j1,隊Q,A0Eo;用在第i層表示正處在生成Ei的階段。對m 2,設(shè)生成規(guī)則指明了Ei由m個Ei+1組成,則在第i層共應(yīng)生成mi個部分圖形。用A0記一個部分圖形,j是

37、己生成部分圖形的數(shù)目。第i層部分圖形要在第i+1層再分,故生成后要送到一個先進(jìn)先出的隊Q中等待;2.一次生成依據(jù)生成規(guī)則,由一個部分圖形A0,計算它的m個分解部分A1,A2, Am;3.圖形繪制對Al,A2, ,Am做圖形繪制;4.存貯隊Q (A1,A2,Am)生成各部分圖形依次加到隊尾;第63頁，共81頁，2022年，5月20日，14點37分，星期三5.準(zhǔn)備下次A0隊Q;從隊取出一個部分圖形;6.第i層是否結(jié)束jj+1,若jmi,則j1;ii+1; 7.結(jié)束判斷若ik,則算法結(jié)束;否則返回步 2. von Koch曲線 其源形E0可以是一條線段, 記其端點坐標(biāo)為P0,P1。在算法步1,應(yīng)令A(yù)

38、0=E0=(Po,Pl ),在算法步2,需要依據(jù)Po,Pl ,計算圖中P2,P3,P4三點的坐標(biāo)。 這樣m=4,分別得到四個部分圖形是A1=(P0,P2),A2=(P2,P3),A3=(P3,P4),A4=(P4,P1)。在算法步3,可畫出四條線段P0P2,P2 P3, P3 P4, P4P1,擦去前次畫線時可能畫出的P2P4部分。第64頁，共81頁，2022年，5月20日，14點37分，星期三Von Koch算法 利用自相似變換來繪制分形 設(shè)D是歐氏空間Rn的閉子集,映射S:D D稱為是D上的壓縮，如果對所有D上的點x,y,存在一個數(shù)c,0ck則算法結(jié)束,否則返步2。第73頁，共81頁，2022年，5月20日，14點37分，星期三 上面的變換能產(chǎn)生很緊松樹樹枝的圖象。 第74頁，共81頁，2022年，5月20日，14點37分，星期三Julia和Mandelbrot集 設(shè)有復(fù)數(shù)域上如下形式的二次函數(shù):f(z)=z2+c其中c是復(fù)數(shù)值常數(shù),做迭代操作:zn+1= zn2+c,n=0,1,2, 研究的問題是:1.給定z0,當(dāng)參數(shù)c在什么范圍內(nèi)取值能保證|zn|有界2.當(dāng)c給定,如何選取z0,使|zn|有界? 第75頁，共81頁，2022年，5月20日，14點37分，星期三 上述迭代,當(dāng)c=0時,可以有以下三種情況:1. 序列中的數(shù)按模來說越來越小,且趨于零。這時說零是