【文章內(nèi)容簡(jiǎn)介】 )與實(shí)數(shù)運(yùn)算相似，求兩個(gè)幾何對(duì)象的Minkowski和滿足交換規(guī)則和分配規(guī)則，即式子S1197。S2=S2197。S1與S1197。(S2S3)=(S1197。S2)(S1197。S3)成立。(2)設(shè)幾何對(duì)象S1與S2為兩個(gè)凸多邊形，分別含有n和m條邊，則Minkowski和是由不超過(guò)n+m條邊構(gòu)成的凸多邊形。(3)設(shè)S1與S2為兩個(gè)多邊形，分別含有n和m個(gè)頂點(diǎn)，S1與S2的Minkowski和的時(shí)間復(fù)雜度上界分為下列幾種情況。若S1與S2均為凸多邊形，則計(jì)算的時(shí)間復(fù)雜度上界為O(n+m)。若S1與S2中一個(gè)為凸多邊形，另外一個(gè)為非凸多邊形，則計(jì)算的時(shí)間復(fù)雜度上界為O(nm)。若S1與S2均為非凸多邊形，則計(jì)算的時(shí)間復(fù)雜度上界為O(n2m2)。(4)設(shè)S1與S2為兩個(gè)多面體，分別含有n和m個(gè)頂點(diǎn)，S1與S2的Minkowski和所需要的時(shí)間分為下列幾種情況。若S1與S2均為凸多面體，則計(jì)算所需要的時(shí)間為O(n2m2)。若S1與S2均為非凸多面體，則計(jì)算所需要的時(shí)間為O(n3m3)。 平面劃分的疊置求平面劃分的疊置是將兩個(gè)或者多個(gè)平面劃分圖層進(jìn)行疊加，并產(chǎn)生一個(gè)新平面劃分圖層的操作，其結(jié)果是將原來(lái)平面劃分中的圖元分割成新圖元，新圖元綜合了原來(lái)兩個(gè)圖層或者多個(gè)圖層的屬性[33]。給定兩個(gè)平面劃分D1和D2，它們的疊置是一個(gè)新的平面劃分，記作Overlay(D1,D2)。如果在Overlay(D1,D2)中存在一張面f，在D1和D2中分別存在面和，那么面f是的一個(gè)極大連通子集[27]。簡(jiǎn)單的說(shuō)是由來(lái)自D1和D2的邊共同在平面上導(dǎo)出一個(gè)子區(qū)域劃分，如圖23所示，黃色點(diǎn)為新的交點(diǎn)。圖23 平面劃分的疊置Fig. 23 Overlay of planar subdivisions一般的疊置問(wèn)題，首先給出分別對(duì)應(yīng)于D1和D2的兩個(gè)雙向鏈接邊表，然后計(jì)算出對(duì)應(yīng)于Overlay(D1,D2)的雙向鏈接邊表，同時(shí)要求對(duì)Overlay(D1,D2)中的每張平面劃分面加上標(biāo)注，以指明在D1和D2中它分別屬于哪張平面劃分面，這樣能夠直接訪問(wèn)存儲(chǔ)在這些面記錄中的附加信息。 邊界表示法物體可以通過(guò)描述它的邊界來(lái)表示，稱為邊界表示法[34]。邊界就是物體內(nèi)部點(diǎn)與外部點(diǎn)的分界面。定義了物體的邊界，該物體也就被唯一的定義了。邊界表示法的一個(gè)很重要的特點(diǎn)是描述了物體的信息，包括幾何信息與拓?fù)湫畔蓚€(gè)方面。物體的幾何信息是指頂點(diǎn)、邊、面的位置、大小、形狀等幾何數(shù)據(jù)。拓?fù)湫畔⑹侵肝矬w上所有的頂點(diǎn)、棱邊、面間的連接情況[35]。 移動(dòng)立方體算法移動(dòng)立方體MC(Marching Cubes)算法是基于規(guī)則體數(shù)據(jù)抽取等值面的經(jīng)典算法[36]。傳統(tǒng)的MC算法的基本思想是逐個(gè)處理數(shù)據(jù)場(chǎng)中的立方體(體單元)，分類出與等值面相交的立方體，采用插值計(jì)算出等值面與立方體的交點(diǎn)。根據(jù)立方體每一頂點(diǎn)與等值面的相對(duì)位置，將等值面與立方體的交點(diǎn)按一定方式連接生成等值面，作為等值面在該立方體內(nèi)的一個(gè)逼近。該算法對(duì)體數(shù)據(jù)中的體素逐個(gè)進(jìn)行處理，每個(gè)被處理的體素，以三角面片表示其內(nèi)部的等值面。 算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)專門研究從解決非數(shù)值計(jì)算的現(xiàn)實(shí)問(wèn)題中抽象出來(lái)的數(shù)據(jù)在計(jì)算機(jī)中如何表示、快速存取和處理的方法。計(jì)算幾何與計(jì)算機(jī)科學(xué)中的算法設(shè)計(jì)與分析、數(shù)據(jù)結(jié)構(gòu)等學(xué)科的關(guān)系非常密切，它常常要用到這些學(xué)科的知識(shí)。設(shè)計(jì)求解幾何問(wèn)題的算法首先應(yīng)該具備兩個(gè)條件，一是分析并理解問(wèn)題的幾何特征，二是掌握計(jì)算幾何中的幾何結(jié)構(gòu)、特殊的算法設(shè)計(jì)方法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。由于本文的研究?jī)?nèi)容與幾何算法的設(shè)計(jì)與分析相關(guān)，因此就必須介紹一下關(guān)于算法和數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)。 算法算法是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列，是求解一個(gè)問(wèn)題類的無(wú)二義性的有窮過(guò)程[28]。這里的求解過(guò)程是指求解問(wèn)題執(zhí)行的一步一步動(dòng)作的集合，每一步動(dòng)作只需要有限的存儲(chǔ)單元和有限的操作時(shí)間。簡(jiǎn)單的說(shuō)，算法就是解決特定問(wèn)題的方法。描述一個(gè)算法可以采用文字?jǐn)⑹觯部梢圆捎脗鹘y(tǒng)流程圖、NS圖或PAD圖等等。一個(gè)算法具有下列重要特性。(1)有窮性 算法只執(zhí)行有限步，并且每步應(yīng)該在有限的時(shí)間內(nèi)完成。(2)確定性 算法中的每一條指令必須有確切的含義，無(wú)二義性。(3)可行性 算法中描述的操作都必須足夠基本，即都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。(4)輸入 算法具有零個(gè)或多個(gè)輸入。(5)輸出 算法具有一個(gè)或多個(gè)輸出，沒(méi)有輸出的算法沒(méi)有任何意義。算法的復(fù)雜度是衡量算法效率的方法，其中包括算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度。為了說(shuō)明復(fù)雜度的概念，先介紹問(wèn)題規(guī)模的概念。隨著處理問(wèn)題的數(shù)據(jù)增大，處理會(huì)越來(lái)越困難復(fù)雜，把描述數(shù)據(jù)增大程度的量叫做問(wèn)題規(guī)模[37]。規(guī)模越大，消耗的時(shí)間越多。利用某算法處理一個(gè)問(wèn)題規(guī)模為n的輸入所需要的時(shí)間，稱為該算法的時(shí)間復(fù)雜度，它是規(guī)模n的函數(shù)，記為T(n)。算法的空間復(fù)雜度是指解決問(wèn)題的算在執(zhí)行時(shí)所占用的存儲(chǔ)空間，記作S(n)[28]。下面主要討論算法的時(shí)間復(fù)雜度。由于一般不需要知道精確的時(shí)間耗費(fèi)，只要知道時(shí)間耗費(fèi)的增長(zhǎng)率大體在什么范圍內(nèi)即可，因此引入算法復(fù)雜度階的概念。如果對(duì)某一個(gè)正常數(shù)c，一個(gè)算法能在時(shí)間2內(nèi)處理規(guī)模是n的輸入，則稱此算法的時(shí)間復(fù)雜度是O(n2)，讀作“n2階”。一般情況下，都是取一個(gè)簡(jiǎn)單形式的函數(shù)作為階數(shù)的規(guī)范，如。一個(gè)算法的時(shí)間復(fù)雜度，如果是O(2n)，則稱算法需要指數(shù)時(shí)間；如果是O(nk)(k為有理數(shù))，則稱此算法為多項(xiàng)式時(shí)間算法。當(dāng)n很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法存在很大的差別。以多項(xiàng)式時(shí)間為限界的算法稱為有效算法。因此應(yīng)該盡可能選用多項(xiàng)式階O(nk)的算法，而不希望用指數(shù)階的算法。算法的時(shí)間復(fù)雜度可分為最壞情況的時(shí)間復(fù)雜性和平均情況的時(shí)間復(fù)雜性[30]。對(duì)于給定規(guī)模為n的各種輸入，某算法執(zhí)行每條指令所需要的時(shí)間之和的最大值，稱為該算法的最壞情況的時(shí)間復(fù)雜性；對(duì)于給定規(guī)模為n的各種輸入，執(zhí)行每條指令所需要的時(shí)間之和的平均值，稱為平均情況的時(shí)間復(fù)雜性(或期望復(fù)雜性或平均特性)。由于規(guī)模為n的輸入出現(xiàn)的概率不同，所以有時(shí)要考慮加權(quán)平均特性。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，簡(jiǎn)言之是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合[37]。由于算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系非常緊密，因此在進(jìn)行算法設(shè)計(jì)時(shí)首先要確定相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。本文除了用到通用的數(shù)據(jù)結(jié)構(gòu)鄰接表、隊(duì)列以外，還用到一種特殊的結(jié)構(gòu)：雙向鏈接邊表DCEL(Doubly Connected Edge List)[27]。雙向鏈接邊表適于表示嵌入到平面的平面劃分，它是一種簡(jiǎn)單而有效的數(shù)據(jù)結(jié)構(gòu)，并且是一種基于邊的表示方法，同時(shí)包含頂點(diǎn)和面(平面劃分面)的信息。也就是說(shuō)，對(duì)于任一個(gè)子區(qū)域，與之相對(duì)應(yīng)的雙向鏈接邊表為其中的每個(gè)頂點(diǎn)，每條半邊和每張面都設(shè)置了一個(gè)記錄，即頂點(diǎn)記錄、半邊記錄和面記錄，在這些記錄中，分別存有幾何信息、拓?fù)湫畔⒑透郊有畔?。在雙向鏈接邊表數(shù)據(jù)結(jié)構(gòu)中，規(guī)定每條無(wú)向邊都由兩條具有相對(duì)方向的半邊(Half Edge)表示，這兩條半邊互稱為孿生半邊，并且都與它左側(cè)的面相關(guān)聯(lián)；對(duì)于任何一條半邊，都有唯一的一條后繼半邊，以及唯一的一條前驅(qū)半邊；每條有向半邊都有起點(diǎn)和終點(diǎn)。下面給出DCEL結(jié)構(gòu)的各組成部分，如圖24所示。一般情況下，在對(duì)應(yīng)頂點(diǎn)的頂點(diǎn)記錄中，設(shè)有一個(gè)名為Coordinates(v)的域，用來(lái)存放頂點(diǎn)的坐標(biāo)。此外，還有一個(gè)名為IncidentEdge(v)的指針，指向以頂點(diǎn)為起點(diǎn)的某一條半邊。在對(duì)應(yīng)于面的面記錄中，設(shè)有一名為OuterComponent(f )的指針，指向該面的外邊界(Outer Boundary)上的任意一條半邊。若是無(wú)界面(Unbouned Face)，則此指針為Null。此外，還有一個(gè)名為InnerComponent(f )的列表，其中設(shè)有多個(gè)指針，分別對(duì)應(yīng)于該面的各個(gè)空洞；每個(gè)指針?biāo)傅模瞧鋵?duì)應(yīng)空洞的邊界上的某一條半邊。在對(duì)應(yīng)于半邊的半邊記錄中，設(shè)有一個(gè)名為Origin(e)的指針，指向該半邊的起點(diǎn)；另有一個(gè)名為Twin(e)的指針，指向其孿生半邊；還有一個(gè)名為IncidentFace(e)的指針，指向位于半邊左邊的面，即半邊參與圍成的那張面。半邊的終點(diǎn)無(wú)需存儲(chǔ)，因?yàn)樗扔贠rigin(Twin(e))。半邊起點(diǎn)的選取，要使得從半邊的起點(diǎn)走向終點(diǎn)的過(guò)程中，IncidentFace(e)位于的左側(cè)。此外，半邊記錄中還設(shè)有兩個(gè)指針Next(e)和Prev(e)，分別指向沿著IncidentFace(e)邊界的半邊的后繼半邊與前驅(qū)半邊。這樣，沿著IncidentFace(e)的邊界，以的終點(diǎn)為起點(diǎn)的半邊只有Next(e)一條，而以的起點(diǎn)為終點(diǎn)的半邊也只有Prev(e)一條。Origin(e)Next(e)IncidentFace(e)Twine(e)ePrev(e)圖24 DCEL結(jié)構(gòu)的各組成部分Fig. 24 Component of DCEL structure每個(gè)頂點(diǎn)和每條邊所對(duì)應(yīng)的信息量，都是常數(shù)規(guī)模的。面記錄占用的空間可能會(huì)更多一些，因?yàn)槊鎓中含有多少個(gè)空洞，列表InnerComponent(f )中就需要有多少項(xiàng)。然而，只要將所有的InnerComponent(f )列表合起來(lái)統(tǒng)計(jì)，就會(huì)發(fā)現(xiàn)其中指向任何一條半邊的指針都不會(huì)超過(guò)一個(gè)。由此可以得出結(jié)論：每個(gè)平面劃分所需存儲(chǔ)空間的規(guī)模，與該平面劃分本身的復(fù)雜度呈線性關(guān)系。e1,a下面給出了一個(gè)簡(jiǎn)單的平面劃分區(qū)域的子區(qū)域所對(duì)應(yīng)的雙向鏈接邊表，如圖25所示。表2表22和表23分別給出相應(yīng)的頂點(diǎn)記錄、面記錄、半邊記錄。e1,be4,ae4,be3,be3,af1e2,ae2,bv4v3v2v1f2圖25 簡(jiǎn)單的平面劃分Fig. 25 Simple planar subdivision表21 頂點(diǎn)記錄Table 21 Records of verticesVertexCoordinatesIncidentEdgev1(0,4)e1,av2(2,4)e4,bv3(2,2)e2,av4(1,2)e2,b表22 面記錄Table 22 Records of facetsFaceOuterComponentInnerComponentsf1Nulle1,af2e4,aNull表23 半邊記錄Table 23 Records of half edgesHalfedgeOriginTwinIncidentFaceNextPreve1,av1e1,bf1e4,be3,ae1,bv2e1,af2e3,be4,ae2,av3e2,bf1e2,be4,be2,bv4e2,af1e3,ae2,ae3,av3e3,bf1e1,ae2,be3,bv1e3,af2e4,ae1,be4,av3e4,bf2e1,be3,be4,bv2e4,af1e2,ae1,a上面介紹的雙向鏈接邊表，只是一種通用版本。在某些具體的應(yīng)用中，頂點(diǎn)v本身可能不含任何屬性信息，此時(shí)，就可以將它們各自的坐標(biāo)，直接存儲(chǔ)在相關(guān)聯(lián)的半邊的Oringe( )域中，而不必專門為頂點(diǎn)記錄定義一種數(shù)據(jù)類型。除此之外，在很多實(shí)際應(yīng)用中，子區(qū)域劃分中的面并不具有任何含義，此時(shí)可以完全舍棄掉面記錄，以及各半邊對(duì)應(yīng)的IncidentFace( )域。在雙向鏈接表的某些實(shí)現(xiàn)中，可能要求平面劃分的頂點(diǎn)和邊所對(duì)應(yīng)的圖是連通的，既然連通圖對(duì)應(yīng)的子區(qū)域劃分絕對(duì)不會(huì)出現(xiàn)空洞，因此列表InnerComponent( )也就不必存在了。 本章小結(jié)本章主要對(duì)Minkowski和算法涉及的基本知識(shí)進(jìn)行了簡(jiǎn)要的介紹。幾何學(xué)是整個(gè)Minkowski和算法設(shè)計(jì)的基礎(chǔ)，本章首先介紹了與研究?jī)?nèi)容相關(guān)的基本幾何對(duì)象的定義。其次，描述了Minkowski和的概念及性質(zhì)，并介紹了相關(guān)的幾何操作，如平面劃分的疊置、移動(dòng)立方體算法等。最后，介紹了有關(guān)算法的基本知識(shí)，重點(diǎn)介紹了雙向鏈接邊表。通過(guò)對(duì)算法所涉及的基本知識(shí)的介紹，為后續(xù)研究奠定了基礎(chǔ)。第3章 計(jì)算凸多面體的精確Minkowski和 引言在歐幾里得三維空間中，求兩個(gè)凸多面體的Minkowski和是一項(xiàng)重要的幾何操作，它等同于兩個(gè)凸多面體中所有點(diǎn)的矢量和的集合[38]。為了提高算法的執(zhí)行效率、加快求和速度，在深入分析現(xiàn)有算法的基礎(chǔ)上，本章脫離以往算法中基于傳統(tǒng)的高斯映射的算法，提出一種全新的計(jì)算凸多面體精確Minkowski和的算法。該算法以文獻(xiàn)[27]中的子區(qū)域劃分的疊置算法為基礎(chǔ)，通過(guò)給出一種自定義的映射方式，即正四面體映射和點(diǎn)投影，把三維空間的問(wèn)題轉(zhuǎn)換到二維空間進(jìn)行解決，求兩個(gè)凸多面體的Minkowski和就等同于計(jì)算一對(duì)平面劃分的疊置。除此之外，還根據(jù)求和的需要及特征完成了屬性分配過(guò)程。 現(xiàn)有的Minkowski和求和算法為了求兩個(gè)凸多面體的Minkowski和，研究人員已經(jīng)提出了多種有效的方法。下面主要介紹基于立方體高斯映射的凸多面體Minkowski和求和算法，并對(duì)其進(jìn)行分析。基于高斯映射的定義，[24]中提出了CGM的概念。它可以描述為：在歐幾里得三維空間內(nèi)，凸多面體的CGM是一個(gè)從多面體體元到立方體表面的集值函數(shù)。首先，為凸多面體P的每個(gè)點(diǎn)p分配一條指向P的支撐平面的法線向量，則P的每個(gè)小面均對(duì)應(yīng)著一條法向量，使所有法向量的起始點(diǎn)都處在立方體的中心，這樣多面體的一個(gè)小面就能夠映射為立方體某個(gè)面上的一個(gè)點(diǎn)；然后，按照同樣的映射規(guī)則，多面體的一條邊至多映射為三條連接的線段，它們分別位于三個(gè)鄰接的立方體表面上；多面體的一個(gè)頂點(diǎn)映射為一個(gè)凸多邊形，此多邊形至多位于五個(gè)鄰接的立方體表面上。在這里，立方體的邊平行于坐標(biāo)軸，并且長(zhǎng)度為2。與基于傾斜圖的求