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