【正文】 分平面疊置，并且都沒有給出具體的映射函數(shù)關(guān)系式。該問題用滲透深度來描述，兩個(gè)多面體P和Q的滲透深度是指使得兩個(gè)多面體不相交，其中一個(gè)多面體必須移動(dòng)的最小距離[17]。假設(shè)多面體P為工作空間中的障礙物，多面體R為移動(dòng)機(jī)器人，那么通過計(jì)算位姿空間障礙物來確定一條無碰撞的路徑，這個(gè)問題就轉(zhuǎn)變?yōu)橛?jì)算多面體P與R的Minkowski和，其中R與R關(guān)于坐標(biāo)原點(diǎn)對(duì)稱。路徑規(guī)劃是機(jī)器人學(xué)算法中的一個(gè)重要問題，其本質(zhì)是在眾多障礙物之間為機(jī)器人尋找一條最優(yōu)或近似最優(yōu)的無碰撞路徑，該問題經(jīng)常用位姿空間方法來描述。因此研究凹多面體的精確Minkowski和求和算法是一項(xiàng)具有挑戰(zhàn)性及重要意義的課題?；谕蛊史值腗inkowski和算法，是計(jì)算凹多邊形或凹多面體的Minkowski和的常用算法?；谡拿骟w中心投影的Minkowski和算法，首先按照高斯映射規(guī)則，將凸多面體映射到單位球面上，再取單位球面的外切正四面體，通過自定義的正四面體中心投影得到凸多面體在正四面體上的投影。基于傾斜圖的Minkowski和求和算法，根據(jù)高斯映射的規(guī)則，把多面體的體元(包括多面體的頂點(diǎn)、棱、面)映射到單位球表面，并采用立體投影方法把每個(gè)多面體的傾斜圖轉(zhuǎn)化為平面圖形，然后計(jì)算平面圖形的疊置，從疊置的結(jié)果中抽取Minkowski和的邊界值?；谡拿骟w中心投影算法，2008年，郭希娟和謝蕾又給出了進(jìn)一步優(yōu)化—基于正四面體高斯映射RTGM(Regular Tetrahedron Gaussian Map)的算法[26]。遵循文獻(xiàn)[13]提出的方法，2007年，(Cubical Gaussian Map)計(jì)算三維空間內(nèi)凸多面體的精確Minkowski和算法[24]，該算法也是基于CGAL實(shí)現(xiàn)的。2000年，[19]中給出了計(jì)算普通多邊形的Minkowski和算法，該算法是基于CGAL(Computational Geometry Algorithm Library)[20]實(shí)現(xiàn)的。通過使用立體投影(Stereographic Projection)方法，多面體的傾斜圖轉(zhuǎn)換為二維圖形，這樣就把問題降低到較低維數(shù)的空間中進(jìn)行解決。 國外研究現(xiàn)狀1987年，(OutputSensitive)算法，該算法定義了二維平面上的一個(gè)操作，稱作卷積(Convolution)[11]。可見，研究兩個(gè)幾何對(duì)象的Minkowski和求和算法，對(duì)于解決機(jī)器人的路徑規(guī)劃問題有著十分重要的現(xiàn)實(shí)價(jià)值。Minkowski和是計(jì)算無碰撞路徑的一個(gè)重要工具，可以定義為，在歐幾里得空間中，假設(shè)P和Q為兩個(gè)封閉的幾何對(duì)象，那么P和Q的Minkowski和為幾何對(duì)象M，其中p和q分別是P和Q上的點(diǎn)，p+q是p和q的位置矢量和[7]。對(duì)于軌跡已知的情況下的規(guī)劃可以將其轉(zhuǎn)化為若干靜態(tài)問題解決；但對(duì)于運(yùn)動(dòng)軌跡未知的情況，機(jī)器人需要在運(yùn)動(dòng)中不斷地檢測(cè)與障礙物之間的碰撞情況。為了更好地解決機(jī)器人的路徑規(guī)劃問題，人們往往用多面體模型來模擬工作空間中的機(jī)器人與障礙物，其中多面體又可以分為凸多面體和凹多面體。機(jī)器人學(xué)有著極其廣泛的研究和應(yīng)用領(lǐng)域，這些領(lǐng)域體現(xiàn)出廣泛的學(xué)科交叉，涉及眾多的課題，如機(jī)器人控制、智能、傳感、機(jī)器人裝配以及機(jī)器語言等，在工業(yè)、農(nóng)業(yè)、空間和海洋以及國防等領(lǐng)域得到越來越普遍的應(yīng)用。Minkowski和算法作為計(jì)算幾何研究領(lǐng)域中的一個(gè)分支，在理論和應(yīng)用上都有著重要的意義。 Enhanced Marching Cubes。 Regular Tetrahedron Map。再次，給出了計(jì)算凹多面體的Minkowski和算法的總體思想。首先，在對(duì)國內(nèi)外研究現(xiàn)狀進(jìn)行綜合分析的基礎(chǔ)上，進(jìn)一步研究了計(jì)算兩個(gè)凸多面體Minkowski和的求和算法。工學(xué)碩士學(xué)位論文三維空間內(nèi)凹多面體的Minkowski和的算法研究摘 要計(jì)算幾何是計(jì)算機(jī)理論科學(xué)的一個(gè)重要分支，該學(xué)科已經(jīng)有了巨大的發(fā)展，產(chǎn)生了一系列的理論成果。本文脫離以往算法中基于傳統(tǒng)的高斯映射的算法，以減少計(jì)算平面劃分疊置的次數(shù)、提高算法的執(zhí)行效率為目標(biāo)，提出了正四面體映射和點(diǎn)投影的概念，通過計(jì)算凸多面體的正四面體映射和點(diǎn)投影，把三維空間的問題轉(zhuǎn)換到二維平面進(jìn)行解決。采用成功回路的算法對(duì)凹多面體進(jìn)行剖分，得到若干子凸多面體；利用正四面體映射和點(diǎn)投影的算法計(jì)算所有可能成對(duì)的子凸多面體的Minkowski和；通過已改進(jìn)的Enhanced Marching Cubes算法合并子凸多面體的Minkowski和多面體的邊界。 Point Projection。 Minkowski Sum目錄摘 要 IAbstract II第1章 緒論 1 課題研究意義 1 Minkowski和算法的研究現(xiàn)狀 2 國外研究現(xiàn)狀 3 國內(nèi)研究現(xiàn)狀 4 Minkowski和算法的應(yīng)用 6 機(jī)器人路徑規(guī)劃 6 碰撞檢測(cè) 6 本文研究內(nèi)容 7 本文組織結(jié)構(gòu) 8第2章 理論基礎(chǔ) 9 相關(guān)的幾何定義 9 歐幾里得空間 9 點(diǎn) 9 直線與線段 9 多面體 10 平面圖及平面劃分 10 凸集與凸包 10 基礎(chǔ)知識(shí)及內(nèi)容 10 Minkowski和的定義 10 Minkowski和的性質(zhì) 11 平面劃分的疊置 12 邊界表示法 13 移動(dòng)立方體算法 13 算法與數(shù)據(jù)結(jié)構(gòu) 13 算法 14 數(shù)據(jù)結(jié)構(gòu) 15 本章小結(jié) 18第3章 計(jì)算凸多面體的精確Minkowski和 19 引言 19 現(xiàn)有的Minkowski和求和算法 19 相關(guān)定義 21 正四面體映射 21 正四面體映射的定義 21 空間坐標(biāo)轉(zhuǎn)換關(guān)系 22 數(shù)據(jù)結(jié)構(gòu)及相關(guān)信息 24 點(diǎn)投影 25 點(diǎn)投影的定義 25 空間坐標(biāo)轉(zhuǎn)換關(guān)系 26 數(shù)據(jù)結(jié)構(gòu)及相關(guān)信息 28 基于正四面體映射和點(diǎn)投影的Minkowski和求和算法 28 算法思想 29 算法描述 30 算法分析 33 本章小結(jié) 34第4章 計(jì)算凹多面體的Minkowski和 35 引言 35 凹多面體Minkowski和求和算法概述 35 凹多面體凸剖分算法 36 凸剖分算法的研究現(xiàn)狀 36 相關(guān)定義與定理 37 基于成功回路的凹多面體的剖分算法 39 算法分析 43 合并子Minkowski和多面體 43 相關(guān)定義 43 合并子Minkowski和多面體算法概述 44 改進(jìn)的合并算法 45 算法分析 47 計(jì)算簡單凹多面體的Minkowski和算法總體思想 47 本章小結(jié) 48第5章 實(shí)驗(yàn)與分析 49 實(shí)驗(yàn)環(huán)境設(shè)置 49 LEDA簡介 49 精確實(shí)數(shù)計(jì)算 50 Minkowski和求和算法的實(shí)驗(yàn)驗(yàn)證 51 凸多面體Minkowski和求和算法實(shí)現(xiàn)及分析 52 簡單凹多面體Minkowski和求和算法實(shí)現(xiàn)及分析 56 本章小結(jié) 61結(jié) 論 63參考文獻(xiàn) 65第1章 緒論 課題研究意義“計(jì)算幾何”這個(gè)術(shù)語最初是由Minsky和Papert作為模式識(shí)別的代用詞被提出來，：“對(duì)幾何外形信息的計(jì)算機(jī)表示、分析和綜合”。它廣泛應(yīng)用于機(jī)器人學(xué)、計(jì)算機(jī)圖形學(xué)、固體建模、計(jì)算機(jī)動(dòng)畫和CAD/CAM等領(lǐng)域[2]。機(jī)器人學(xué)的最終目標(biāo)之一，就是設(shè)計(jì)出一個(gè)獨(dú)立自主的機(jī)器人，它能夠接受高級(jí)任務(wù)并且在沒有人的干涉下自主執(zhí)行并完成任務(wù)[4]。這樣，檢測(cè)機(jī)器人與障礙物之間的碰撞情況就轉(zhuǎn)換為檢測(cè)多個(gè)幾何體之間的碰撞情況[6]。在靜態(tài)環(huán)境下，機(jī)器人僅僅能夠做平移或翻轉(zhuǎn)運(yùn)動(dòng)，通常障礙物為靜態(tài)的剛性物體，并且機(jī)器人與障礙物的幾何形狀和位置是已知的。也就是說若，則有。 Minkowski和算法的研究現(xiàn)狀1983年，(Configuration Space Obstacle)，并應(yīng)用到機(jī)器人的運(yùn)動(dòng)規(guī)劃中[9]。1996年，提出了以定義在多面體運(yùn)動(dòng)軌跡上的卷積計(jì)算為基礎(chǔ)的方法來計(jì)算三維空間內(nèi)多面體的Minkowski和[12]。1997年，：首先，對(duì)每個(gè)多邊形(或多面體)進(jìn)行凸剖分，得到若干個(gè)子凸多邊形(或多面體)；然后，計(jì)算取自不同多邊形(或多面體)的所有可能成對(duì)的子凸剖分的Minkowski和；最后，合并第二步中所有子Minkowski和多邊形(多面體)[15]。2001年，基于Ghosh在文獻(xiàn)[13]中提出的傾斜圖表示法，最終提出了在線性時(shí)間內(nèi)計(jì)算三維空間凸多面體Minkowski和的新方法，但是該方法只對(duì)非常簡單的凸多面體適用[21]。 國內(nèi)研究現(xiàn)狀國內(nèi)對(duì)Minkowski和算法的研究起步較晚。通過對(duì)國內(nèi)外研究現(xiàn)狀的分析，可以得出計(jì)算多邊形或者多面體的Minkowski和算法主要有六種，即基于凸包的求和算法、基于凸剖分的求和算法、基于傾斜圖的求和算法、基于立方體高斯映射的求和算法、基于正四面體中心投影的求和算法以及基于正四面體高斯映射的算法。采用立體投影方法不僅會(huì)使算法在處理退化情況時(shí)存在著很大的局限性，而且會(huì)增加算法的實(shí)現(xiàn)難度，很難得到精確的計(jì)算結(jié)果。求兩個(gè)凸多面體的Minkowski和等同于求四對(duì)平面劃分的疊置。對(duì)于二維空間內(nèi)的凹多邊形而言，常用的方法就是把凹多邊形剖分為若干個(gè)凸多邊形，通過計(jì)算凸多邊形Minkowski子和的并來得到凹多邊形的Minkowski和。 Minkowski和算法的應(yīng)用Minkowski和算法在許多領(lǐng)域中有著廣泛的應(yīng)用，如機(jī)器人學(xué)、碰撞檢測(cè)、模擬仿真、計(jì)算機(jī)圖形學(xué)等等，下面重點(diǎn)介紹該算法在機(jī)器人路徑規(guī)劃和碰撞檢測(cè)中的應(yīng)用。所謂的位姿空間，也稱C空間，是機(jī)器人的參數(shù)空間；機(jī)器人的工作空間是機(jī)器人在其中實(shí)際運(yùn)動(dòng)的那個(gè)空間，也就是真實(shí)的世界。 碰撞檢測(cè)碰撞檢測(cè)是檢測(cè)兩個(gè)物體在空間中是否重疊或它們的邊界線是否至少共享一個(gè)點(diǎn)[17]。通過計(jì)算原心到Minkowski和()表面上的最小距離來得到。因此，本文提出了正四面體映射和點(diǎn)投影的概念，把三維空間的問題轉(zhuǎn)換到二維空間進(jìn)行解決，且只需要計(jì)算一對(duì)平面劃分的疊置，更高效的計(jì)算凸多面體的精確Minkowski和。 本文組織結(jié)構(gòu)論文分為5章，其余部分組織如下。首先，介紹現(xiàn)有的求和算法，分析它的主要思想；然后，以提高算法的執(zhí)行效率為目標(biāo)，提出正四面體映射和點(diǎn)投影的概念，給出正四面體映射和點(diǎn)投影的映射規(guī)則，并由此提出基于該映射的凸多面體的精確Minkowski和求和算法。第5章是實(shí)驗(yàn)與分析，對(duì)所研究的內(nèi)容及算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證并給出實(shí)驗(yàn)結(jié)果。除了點(diǎn)之外，還將考慮包含兩個(gè)給定點(diǎn)的直線、直線上兩定點(diǎn)確定的直線段、三個(gè)給定點(diǎn)確定的平面等。點(diǎn)也可以解釋為有個(gè)分量的向量，此向量的起點(diǎn)為坐標(biāo)原點(diǎn)，終點(diǎn)為點(diǎn)[28]。線段是直線的一部分，并以兩個(gè)端點(diǎn)為界限。 平面圖及平面劃分假設(shè)圖G=(V，E)，其中V為頂點(diǎn)集，E為邊集，如果圖G能夠沒有交叉地嵌入平面，那么稱圖G為平面圖。這就是說，如果S中任意兩點(diǎn)所連線段全部位于S之中，那么S是凸的。 基礎(chǔ)知識(shí)及內(nèi)容下面將給出Minkowski和的定義、性質(zhì)及相關(guān)的幾何操作。圖21 P和Q的Minkowski和Fig. 21 The Minkowski Sum of P and Q另外，P和Q的Minkowski和也可以表示為幾何對(duì)象M，其中p和q分別為屬于幾何對(duì)象P和Q的點(diǎn)，為位置矢量與的矢量和。(1)與實(shí)數(shù)運(yùn)算相似，求兩個(gè)幾何對(duì)象的Minkowski和滿足交換規(guī)則和分配規(guī)則，即式子S1197。S2)(S1197。若S1與S2均為凸多邊形，則計(jì)算的時(shí)間復(fù)雜度上界為O(n+m)。若S1與S2均為凸多面體，則計(jì)算所需要的時(shí)間為O(n2m2)。如果在Overlay(D1,D2)中存在一張面f，在D1和D2中分別存在面和，那么面f是的一個(gè)極大連通子集[27]。邊界就是物體內(nèi)部點(diǎn)與外部點(diǎn)的分界面。拓?fù)湫畔⑹侵肝矬w上所有的頂點(diǎn)、棱邊、面間的連接情況[35]。該算法對(duì)體數(shù)據(jù)中的體素逐個(gè)進(jìn)行處理，每個(gè)被處理的體素，以三角面片表示其內(nèi)部的等值面。由于本文的研究內(nèi)容與幾何算法的設(shè)計(jì)與分析相關(guān)，因此就必須介紹一下關(guān)于算法和數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)。描述一個(gè)算法可以采用文字?jǐn)⑹?，也可以采用傳統(tǒng)流程圖、NS圖或PAD圖等等。(3)可行性 算法中描述的操作都必須足夠基本，即都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。為了說明復(fù)雜度的概念，先介紹問題規(guī)模的概念。算法的空間復(fù)雜度是指解決問題的算在執(zhí)行時(shí)所占用的存儲(chǔ)空間，記作S(n)[28]。一般情況下，都是取一個(gè)簡單形式的函數(shù)作為階數(shù)的規(guī)范，如。因此應(yīng)該盡可能選用多項(xiàng)式階O(nk)的算法，而不希望用指數(shù)階的算法。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，簡言之是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合[37]。也就是說，對(duì)于任一個(gè)子區(qū)域，與之相對(duì)應(yīng)的雙向鏈接邊表為其中的每個(gè)頂點(diǎn)，每條半邊和每張面都設(shè)置了一個(gè)記錄，即頂點(diǎn)記錄、半邊記錄和面記錄，在這些記錄中，分別存有幾何信息、拓?fù)湫畔⒑透郊有畔ⅰ４送?，還有一個(gè)名為IncidentEdge(v)的指針，指向以頂點(diǎn)為起點(diǎn)的某一條半邊。在對(duì)應(yīng)于半邊的半邊記錄中，設(shè)有一個(gè)名為Origin(e)的指針，指向該半邊的起點(diǎn)；另有一個(gè)名為Twin(e)的指針，指向其孿生半邊；還有一個(gè)名為IncidentFace(e)的指針，指向位于半邊左邊的面，即半邊參與圍成的那張面。這樣，沿著IncidentFace(e)的邊界，以的終點(diǎn)為起點(diǎn)的半邊只有Next(e)一條，而以的起點(diǎn)為終點(diǎn)的半邊也只有Prev(e)一條。由此可以得出結(jié)論：每個(gè)平面劃分所需存儲(chǔ)空間的規(guī)模，與該平面劃分本身的復(fù)雜度呈線性關(guān)系。在某些具體的應(yīng)用中，頂點(diǎn)v本身可能不含任何屬性信息，此時(shí)，就可以將它們各自的坐標(biāo)，直接存儲(chǔ)在相關(guān)聯(lián)的半邊的Oringe( )域中，而不必專門為頂點(diǎn)記錄定義一種數(shù)據(jù)類型。幾何學(xué)是整個(gè)Minkowski和算法設(shè)計(jì)的基礎(chǔ)，本章首先介紹了與研究內(nèi)容相關(guān)的基本