【正文】 算法描述：基于正四面體映射和點(diǎn)投影的兩個(gè)凸多面體Minkowski和的求和算法RTMP。輸入：凸多面體P1與P2的用DCEL記錄的映射(正四面體映射和點(diǎn)投影)的表示，分別記為Q1與Q2；輸出：凸多面體P的映射(正四面體映射和點(diǎn)投影)，記為Q，其中Q=Overlay(Q1，Q2)，P=P1197。 P2。RTMP(Q1,Q2,Q)Begin(1) for(int i=0。in。 ++i)(2) Inf(fi)=(0,0)。 /*把Q1中所有的附加信息置零*/(3) for(int j=0。 j m。 ++j) (4) Inf(fj)=(0,0)。 /*把Q2中所有的附加信息置零*/(5) for(int k=1。k=2。 ++k) /*初始化Q1與Q2的頂點(diǎn)數(shù)組*/(6) {for(int i=0。 in。 ++i) (7) { Visitedk[i] =FALSE 。}(8) for(int j=0。 jm。 j++)(9) { Visitedk[j]=FALSE。 }} /*將頂點(diǎn)的訪(fǎng)問(wèn)標(biāo)志標(biāo)記未訪(fǎng)問(wèn)*/(10) MapOverlay (Q1,Q2)。 /*計(jì)算一對(duì)平面劃分的疊置*/(11) for(int i=k。i++) /*k為平面劃分疊置的個(gè)數(shù)*/(12) AdditionalInfor(Q1i,Q2i)。 /*屬性分配,由于只有一個(gè)平面劃分疊置，因此i=0 */(13) 計(jì)算頂點(diǎn)，半邊的輔助信息，判斷是否為真實(shí)圖元(14) Return QEnd在MapOverlay(Q1,Q2)函數(shù)中，計(jì)算交點(diǎn)需要兩個(gè)數(shù)據(jù)結(jié)構(gòu)的支持，前一結(jié)構(gòu)用來(lái)存放事件點(diǎn)的時(shí)間隊(duì)列，以及狀態(tài)結(jié)構(gòu)；后一結(jié)構(gòu)用一棵平衡二分查找樹(shù)實(shí)現(xiàn)，其中自左向右的記錄了與當(dāng)前掃描線(xiàn)相交的所有線(xiàn)段。：計(jì)算兩個(gè)平面劃分的疊置MapOverlay(Q1,Q2)。輸入：兩個(gè)用雙向鏈接表形式存儲(chǔ)的兩個(gè)平面子區(qū)域劃分Q1,Q2；輸出：Q1和Q2的疊置，也存儲(chǔ)為一個(gè)雙向鏈接表Q。MapOverlay(Q1,Q2)Begin(1) Construct a new DCEL Q。 /*生成一個(gè)新的雙向鏈接表Q*/(2) Copy the DECL Q1 and Q2 to DCEL Q。 /*將Q1和Q2對(duì)應(yīng)的兩個(gè)雙向鏈接表復(fù)制到Q中*/(3) Compute the intersections of the edges of DCEL Q1 and Q2。(4) for(int i=0。im。i++) /*m為事件點(diǎn)的個(gè)數(shù)*/(5) { update 。(6) update 。(7) if (the event point is associated the edges of Q1 and Q2) then /*判斷事件點(diǎn)是否同時(shí)涉及Q1,Q2的邊*/(8) {update DCEL Q。 } /*更新數(shù)據(jù)鏈表Q*/(9) 找到緊鄰于該事件點(diǎn)左側(cè)的半邊,將它存儲(chǔ)于Q對(duì)應(yīng)于該點(diǎn)的頂點(diǎn)處.}(10) 通過(guò)對(duì)Q的遍歷,找出Overlay (Q1,Q2)中的所有邊界環(huán)(border ring)(11) Construct a graph G。 (12) for(int i=0。in。i++) /*n為節(jié)點(diǎn)數(shù)目*/(13) {Correspond a boder ring。 }/*對(duì)每個(gè)節(jié)點(diǎn)分別對(duì)應(yīng)一個(gè)邊界環(huán)*/(14) for(int i=0。im。i++) /*m為弧的個(gè)數(shù)*/(15) {對(duì)每條弧都連接了一個(gè)空洞環(huán)與緊鄰于該環(huán)最左端頂點(diǎn)左側(cè)的另一個(gè)環(huán)，找出Q中所有的連通子塊。} (16) for(int j=0。jk。j++)(17) {do 令G為該連通子塊唯一的外邊界環(huán)，由此環(huán)圍成的面記作f。(18) 生成對(duì)應(yīng)于f的一個(gè)面記錄。(19) 將指向Q的某條半邊。(20) 生成一個(gè)列表。}(21) for(int i=0。iw。i++) /*w為Overlay (Q1,Q2)中面得個(gè)數(shù)*/(22) { sign the facet。}(23) Return QEnd：計(jì)算附加信息的疊加，完成屬性分配AdditionalInfor(Q1i,Q2i)。輸入：第i對(duì)平面劃分的疊置；輸出：完成第i對(duì)平面劃分的屬性值分配。AdditionalInfor (Q1i,Q2i)Begin(1) for(j=1。 j=2。 j ++) (2) { {Get(Qi, fm)。 /*取Qi中最左端的平面劃分面*/(3) Get(Qji, g)。 } /*取Qji中最左端的平面劃分面*/(4) V=Inf(g)。 /*g的附加信息為相應(yīng)頂點(diǎn)的坐標(biāo)*/(5) while (!Visitedj[m])(6) { M=Inf(fm)。 /* fm的附加信息為相應(yīng)頂點(diǎn)的坐標(biāo)*/(7) Inf(fm)=M+V。 /*求坐標(biāo)的矢量和*/(8) Visitedj[m]=TRUE。(9) Get(fm, )。 /*取平面劃分面四周的非邊界半邊*/(10) for(k=1。 k=s。 ++k)(11) { Get(,)。 /*取半邊的孿生半邊*/(12) Get(, fm162。)。 /*取半邊的關(guān)聯(lián)面*/(13) if (!Visitedj[m162。]) then goto14。(14) if (eQji) then /*判斷半邊是否取自Qji*/(15) { Get(DCELj(e), g162。)。 /*在Qji中取半邊e的關(guān)聯(lián)面*/(16) V=Inf(g162。)。 /*g162。的附加信息為Pj的相應(yīng)頂點(diǎn)的坐標(biāo)*/(17) g=g162。 } /*將g162。的屬性信息賦給g*/(18) else V=Inf(g)。 }(19) fm=fm162。 } /*將fm162。的屬性信息賦給fm*/(20) return(fm)。} /*返回屬性疊加后頂點(diǎn)坐標(biāo)的值*/End 算法分析下面對(duì)求和算法的時(shí)間復(fù)雜度進(jìn)行分析。首先，輸入凸多面體P1與P2的正四面體映射和點(diǎn)投影后的平面劃分，由映射規(guī)則可知，完成映射所需要的時(shí)間為O(n1+n2)，其中nn2分別為PP2的頂點(diǎn)個(gè)數(shù)。本章采用文獻(xiàn)[27]中的平面掃描疊置算法計(jì)算兩個(gè)平面劃分的疊置，該算法對(duì)于凸平面劃分或凹平面劃分都適用，完成疊置所需時(shí)間為，其中n、k分別為Q中頂點(diǎn)的個(gè)數(shù)與劃分面的個(gè)數(shù)。計(jì)算附加信息的疊加，完成屬性分配過(guò)程，為了計(jì)算Q中每個(gè)平面劃分面的附加信息，對(duì)于任意一個(gè)輸入多面體，都需要依次遍歷Q中所有的平面劃分面，故所需要的時(shí)間為O(k)，其中k為Q中平面劃分面的個(gè)數(shù)。由此可以得出，整個(gè)求和算法的時(shí)間復(fù)雜度為O(n1+n2+nlogn+klogn+k)。由于k為輸出多面體的正四面體映射和點(diǎn)投影后平面劃分面的個(gè)數(shù)，k的大小決定著算法的執(zhí)行速度?；谡拿骟w高斯映射的求和算法，把凸多面體的體元及其關(guān)聯(lián)關(guān)系映射到正四面體表面，得到四個(gè)平面凸劃分；然后依據(jù)文獻(xiàn)[25]中的疊置算法計(jì)算四次平面劃分的疊置。計(jì)算兩個(gè)凸多面體的Minkowski和多面體的算法的時(shí)間復(fù)雜度為。其中是大于1的常數(shù)，為兩個(gè)凸多面體的面數(shù)，n、e分別為Q中頂點(diǎn)的個(gè)數(shù)與邊數(shù)。經(jīng)證明在相同的條件下求平面劃分的疊置得出，求凸多面體映射到二維平面上得出。兩個(gè)平面劃分的疊置是計(jì)算凸多面體Minkowski和的瓶頸，疊置算法的性能決定了求和算法的優(yōu)劣。由上述分析可見(jiàn)，該文利用平面掃描疊置算法，降低了整個(gè)求和算法的時(shí)間復(fù)雜度。由上述分析可見(jiàn)本章通過(guò)采用自定義的正四面體映射和點(diǎn)投影，只需根據(jù)映射規(guī)則，把兩個(gè)凸多面體的體元及其關(guān)聯(lián)關(guān)系直接映射到一個(gè)二維平面，計(jì)算兩個(gè)凸多面體的Minkowski和等價(jià)于計(jì)算一對(duì)平面劃分的疊置。該算法通過(guò)減少計(jì)算平面劃分疊置的次數(shù)，有效的降低了整個(gè)求和算法的時(shí)間復(fù)雜度。 本章小結(jié)在機(jī)器人的路徑規(guī)劃中，Minkowski和算法是計(jì)算無(wú)碰撞路徑的重要工具，因此快速、有效地求和成為尋找安全路徑的關(guān)鍵。在深入研究現(xiàn)有的求和算法后，本章提出了正四面體映射和點(diǎn)投影的概念，并在此基礎(chǔ)上提出了三維空間內(nèi)凸多面體的精確Minkowski和求和算法，理論上完成了計(jì)算凸多面體Minkowski和的過(guò)程；最后對(duì)算法進(jìn)行了分析。結(jié)果表明，與現(xiàn)有的求和算法相比，該算法不僅給出了具體的映射函數(shù)關(guān)系式，而且通過(guò)給出的自定義的映射方式只需要計(jì)算一次平面劃分疊置，減少計(jì)算平面劃分疊置的次數(shù)，加快了Minkowski和的求和速度，從而降低了整個(gè)求和算法的時(shí)間復(fù)雜度。第4章 計(jì)算凹多面體的Minkowski和 引言雖然研究人員已經(jīng)提出了計(jì)算凸多邊形及凸多面體的精確Minkowski和的多種高效求和算法，但由于計(jì)算凹多邊形和凹多面體的Minkowski和較為復(fù)雜，特別是計(jì)算凹多面體的精確Minkowski和的代價(jià)十分昂貴[17]，目前研究人員主要研究滿(mǎn)足某些標(biāo)準(zhǔn)的近似精確的求和計(jì)算。為了進(jìn)一步提高算法的執(zhí)行效率、加快求和速度，在深入分析現(xiàn)有求和算法的基礎(chǔ)上，本章首先采用圖論和集合論的思想，提出一種基于成功回路的凹多面體的剖分算法，然后給出本文計(jì)算凹多面體Minkowski和的求和算法步驟。因?yàn)橛?jì)算凹多面體的精確Minkowski和的求和算法代價(jià)過(guò)高，所以本文也只進(jìn)行近似精確的計(jì)算。 凹多面體Minkowski和求和算法概述1993年，Ghosh為計(jì)算凸多面體和凹多面體的Minkowski和提出了統(tǒng)一的算法，它以?xún)A斜圖表示法為基礎(chǔ)，計(jì)算兩個(gè)多面體的Minkowski和等同于分別計(jì)算兩個(gè)多面體的傾斜圖，然后合并它們的傾斜圖，并從合并的傾斜圖中提取Minkowski和的邊界值。通過(guò)使用立體投影方法，多面體的傾斜圖轉(zhuǎn)換為二維圖形，這樣實(shí)質(zhì)上把問(wèn)題降低到較低維數(shù)的空間中進(jìn)行解決，使得該算法在處理退化情況時(shí)存在著很大的局限性。1996年，、. Ramkumar等提出以定義在多面體運(yùn)動(dòng)軌跡上的卷積計(jì)算為基礎(chǔ)的求和方法。、 Tagansky提出計(jì)算普通多邊形或多面體的Minkowski和的基本框架。簡(jiǎn)單描述為：凸剖分；計(jì)算所有可能的成對(duì)的凸剖分的子多面體的Minkowski和；合并子Minkowski和多面體?；谄史值那蠛退惴ǖ闹攸c(diǎn)和難點(diǎn)工作就是凸剖分和合并子多面體。因此，尋求一種最優(yōu)的剖分算法和最經(jīng)濟(jì)的合并算法，一直是研究人員努力的方向。本文提出的計(jì)算簡(jiǎn)單凹多面體Minkowski和的算法也是基于剖分理論進(jìn)行的，下面首先介紹基于成功回路的凹多面體的凸剖分算法。 凹多面體凸剖分算法凸剖分是計(jì)算幾何研究領(lǐng)域的一類(lèi)基本問(wèn)題，它廣泛用于模式識(shí)別、圖形動(dòng)畫(huà)、計(jì)算機(jī)輔助設(shè)計(jì)等領(lǐng)域。其中平面多邊形的剖分問(wèn)題已經(jīng)得到了很深入的研究，由于空間立體圖形的復(fù)雜性，關(guān)于三維多面體的凸剖分，一直沒(méi)看到非常有效的算法，但是三維凸剖分是研究許多問(wèn)題的前提，因?yàn)橐粋€(gè)凸的圖形較其他圖形，在計(jì)算機(jī)表示、分析及處理方面方便的多。在計(jì)算凹多面體的Minkowski和的算法中，多面體的凸剖分是一個(gè)及其重要的步驟。 凸剖分算法的研究現(xiàn)狀關(guān)于多面體的凸剖分，國(guó)內(nèi)外已經(jīng)有了很多研究。文獻(xiàn)[39]中指出,將一個(gè)多面體凸剖分成個(gè)數(shù)最少的凸多面體是一個(gè)NP難問(wèn)題。因此，人們努力研究更有效的凸剖分方法，而不是去尋求最佳剖分的方法。由于多面體的非凸特征是由凹邊引起的，因此目前各種凸剖分方法基本上是按照Chazelle的“切割分裂”策略進(jìn)行的，即根據(jù)凹邊形成一些切割面對(duì)多面體進(jìn)行分裂操作，以消除各個(gè)凹邊的非凸性質(zhì)[40,41]。這種簡(jiǎn)單、直觀(guān)的方法可能會(huì)生成大量新點(diǎn)，產(chǎn)生很多凸多面體。為了減少剖分出的凸多面體個(gè)數(shù)，并降低凸剖分的復(fù)雜度，Chazelle提出了改進(jìn)的方法，即所有原屬于同一條凹邊但被其它分割面分開(kāi)的凹邊對(duì)應(yīng)的分割面必須共面[40,41]。這樣，每條凹邊的切割面最多會(huì)與r1個(gè)其他凹邊的切割面相交，所以剖分出的凸多面體數(shù)最多為O(r2)，該算法的時(shí)間復(fù)雜度為O(nr3)，n是多面體的面數(shù)，r是凹棱數(shù)。Chazelle還給出了剖分凸多面體個(gè)數(shù)的下限，即存在一類(lèi)多面體，若該多面體的凹邊數(shù)為r，則剖分該多面體生成的凸多面體個(gè)數(shù)總不少于O(r2)。該方法的最壞時(shí)間和空間復(fù)雜度分別為和。經(jīng)過(guò)一些復(fù)雜的預(yù)處理，時(shí)間復(fù)雜度可降至。2003年，Lien和Amato提出對(duì)多面體進(jìn)行近似凸的凸剖分方法，與精確凸剖分相比，這種近似的凸剖分可以減少剖分的多面體數(shù)量，提高剖分的效率[42]。其具體的凸剖分方法依然是根據(jù)“切割分裂”的思路，并采用文獻(xiàn)[43]的方法，該方法能夠很好的表達(dá)模型的重要結(jié)構(gòu)特征，并能生成多面體的細(xì)節(jié)層次表示。為了提高復(fù)雜多面體的凸剖分效率，2008年，李靜等人提出了基于邊/面遮擋關(guān)聯(lián)性的多面體凸剖分方法[44]。該方法的時(shí)間復(fù)雜度、空間復(fù)雜度、剖分后凸多面體個(gè)數(shù)皆近似為，其所新增加頂點(diǎn)數(shù)的復(fù)雜度近似為。其中，n為多面體的點(diǎn)數(shù)，r為多面體凹邊個(gè)數(shù)。但該算法仍然需要增加新的頂點(diǎn)。針對(duì)這一問(wèn)題，本章采用集合論和圖論的思想，提出一種對(duì)任意凹多面體不添加頂點(diǎn)的凸剖分方法，即基于成功回路的凹多面體的剖分算法。該算法可以對(duì)任意凹多面體多面體進(jìn)行剖分，包括含有空洞的凹多面體。 相關(guān)定義與定理為了敘述方便和清楚表達(dá)，首先給出一些相關(guān)的定義和定理。：凸棱(凹棱) 設(shè)m是多面體的一條棱，如果與m相鄰的兩個(gè)面在多面體內(nèi)部所夾的角小于或者等于180度，則稱(chēng)m為凸棱，否則為凹棱。：凸多面體(非凸多面體) 假如多面體的每一條邊都是凸棱，則稱(chēng)多面體為凸多面體，否則稱(chēng)之為凹多面體。：共表面點(diǎn) 對(duì)于多面體的每一個(gè)表面，