【正文】 若，則有。這個看似簡單的問題在計算幾何學(xué)中卻成為具有挑戰(zhàn)性的問題，并且成為機(jī)器人研究領(lǐng)域中的一個研究熱點問題。在靜態(tài)環(huán)境下，機(jī)器人僅僅能夠做平移或翻轉(zhuǎn)運動，通常障礙物為靜態(tài)的剛性物體，并且機(jī)器人與障礙物的幾何形狀和位置是已知的。動態(tài)環(huán)境即時變環(huán)境，含有運動軌跡已知或未知的障礙物。這樣，檢測機(jī)器人與障礙物之間的碰撞情況就轉(zhuǎn)換為檢測多個幾何體之間的碰撞情況[6]。因此，能否對運動路徑進(jìn)行快速而準(zhǔn)確地規(guī)劃成為衡量機(jī)器人智能高低的一個重要標(biāo)準(zhǔn)。機(jī)器人學(xué)的最終目標(biāo)之一，就是設(shè)計出一個獨立自主的機(jī)器人，它能夠接受高級任務(wù)并且在沒有人的干涉下自主執(zhí)行并完成任務(wù)[4]。機(jī)器人學(xué)(Robotics)是與機(jī)器人設(shè)計、制造和應(yīng)用等相關(guān)的學(xué)科，主要研究機(jī)器人的控制與被處理物體之間的相互關(guān)系[3]。它廣泛應(yīng)用于機(jī)器人學(xué)、計算機(jī)圖形學(xué)、固體建模、計算機(jī)動畫和CAD/CAM等領(lǐng)域[2]。該領(lǐng)域中的問題所帶來的挑戰(zhàn)性，也使得一大批科研人員為之嘔心瀝血、辛勤耕耘，從而使這一嶄新的研究領(lǐng)域在比較短的時間內(nèi)取得了輝煌的成果，對許多問題已經(jīng)有了一系列比較成熟的計算幾何算法。 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 碰撞檢測 6 本文研究內(nèi)容 7 本文組織結(jié)構(gòu) 8第2章 理論基礎(chǔ) 9 相關(guān)的幾何定義 9 歐幾里得空間 9 點 9 直線與線段 9 多面體 10 平面圖及平面劃分 10 凸集與凸包 10 基礎(chǔ)知識及內(nèi)容 10 Minkowski和的定義 10 Minkowski和的性質(zhì) 11 平面劃分的疊置 12 邊界表示法 13 移動立方體算法 13 算法與數(shù)據(jù)結(jié)構(gòu) 13 算法 14 數(shù)據(jù)結(jié)構(gòu) 15 本章小結(jié) 18第3章 計算凸多面體的精確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 點投影 25 點投影的定義 25 空間坐標(biāo)轉(zhuǎn)換關(guān)系 26 數(shù)據(jù)結(jié)構(gòu)及相關(guān)信息 28 基于正四面體映射和點投影的Minkowski和求和算法 28 算法思想 29 算法描述 30 算法分析 33 本章小結(jié) 34第4章 計算凹多面體的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 計算簡單凹多面體的Minkowski和算法總體思想 47 本章小結(jié) 48第5章 實驗與分析 49 實驗環(huán)境設(shè)置 49 LEDA簡介 49 精確實數(shù)計算 50 Minkowski和求和算法的實驗驗證 51 凸多面體Minkowski和求和算法實現(xiàn)及分析 52 簡單凹多面體Minkowski和求和算法實現(xiàn)及分析 56 本章小結(jié) 61結(jié) 論 63參考文獻(xiàn) 65第1章 緒論 課題研究意義“計算幾何”這個術(shù)語最初是由Minsky和Papert作為模式識別的代用詞被提出來，：“對幾何外形信息的計算機(jī)表示、分析和綜合”。 Successful Loop。 Point Projection。關(guān)鍵詞 計算幾何；正四面體映射；點投影；凹多面體；成功回路；Enhanced Marching Cubes；Minkowski和AbstractComputational Geometry is an important embranchment of puter theoretical science. The subject has already made a tremendous development and produced a series of theoretical results. Minkowski sum algorithm has the great significance in theory and application as an embranchment of Computational Geometry. It plays an important role in robotics, dynamic simulation, puter graphics, and so on, especially in the field of robotics, it is an important tool for puting collisionfree path. Therefore, how to calculate the path of obstacle avoidance quickly and accurately has been an important research subject of the home and foreign scholars.Firstly, this paper researches the existed approach of Minkowski sum of two convex polyhedral. In order to reduce the amount of puting overlay of two planar subdivisions and improve the efficiency of the algorithm, this paper separates from the previous algorithm based on the traditional Gaussian Map and proposes the method of Regular Tetrahedron Map and Point Projection to resolve this problem. Through this method, it can reduce the problem in 3D to 2D. Secondly, convex deposition is an important step of puting Minkowski sum of two nonconvex polyhedral. So, for effectively puting the Minkowski sum of nonconvex polyhedral, the papers uses the idea of set theory and graph theory and propose a new algorithm to depose nonconvex polyhedron that based on Successful Loop after studying the convex deposition algorithms. At the same time, the plexity of the algorithm is analyzed.Thirdly, the paper gives the overall idea of puting the Minkowski sum of nonconvex polyhedral. It uses Successful Loop to depose nonconvex polyhedral into convex pieces, then putes their pair wise Minkowski sum that based on Regular Tetrahedron Map and Point Projection, last, uses the reformative approach of the Enhanced Marching Cubes to unite the boundary of polyhedral Minkowski sum of the sub polyhedral. Finally, we validate the above algorithm and give the results. We also do some parison and analysis with the existing algorithm.Keywords Computational Geometry。采用成功回路的算法對凹多面體進(jìn)行剖分，得到若干子凸多面體；利用正四面體映射和點投影的算法計算所有可能成對的子凸多面體的Minkowski和；通過已改進(jìn)的Enhanced Marching Cubes算法合并子凸多面體的Minkowski和多面體的邊界。為了有效地計算凹多面體的Minkowski和，在研究了國內(nèi)外許多凸剖分算法后，本文采用集合論和圖論的思想，提出了基于成功回路的凹多面體的剖分算法，同時對剖分算法的時間復(fù)雜度進(jìn)行了分析。本文脫離以往算法中基于傳統(tǒng)的高斯映射的算法，以減少計算平面劃分疊置的次數(shù)、提高算法的執(zhí)行效率為目標(biāo)，提出了正四面體映射和點投影的概念，通過計算凸多面體的正四面體映射和點投影，把三維空間的問題轉(zhuǎn)換到二維平面進(jìn)行解決。因此，如何快速而準(zhǔn)確地計算避障路徑，一直是國內(nèi)外學(xué)者研究的重要課題。工學(xué)碩士學(xué)位論文三維空間內(nèi)凹多面體的Minkowski和的算法研究摘 要計算幾何是計算機(jī)理論科學(xué)的一個重要分支，該學(xué)科已經(jīng)有了巨大的發(fā)展，產(chǎn)生了一系列的理論成果。Minkowski和算法作為計算幾何研究領(lǐng)域中的一個分支，在理論和應(yīng)用上都有著重要的意義，其研究成果已在機(jī)器人學(xué)、動態(tài)仿真、計算機(jī)圖形學(xué)等許多領(lǐng)域中得到了廣泛的應(yīng)用，尤其在機(jī)器人學(xué)領(lǐng)域，它是計算無碰撞路徑的一個重要工具。首先，在對國內(nèi)外研究現(xiàn)狀進(jìn)行綜合分析的基礎(chǔ)上，進(jìn)一步研究了計算兩個凸多面體Minkowski和的求和算法。其次，凸剖分是計算凹多面體的Minkowski和的一個重要步驟。再次，給出了計算凹多面體的Minkowski和算法的總體思想。最后，通過實驗驗證了上述的研究內(nèi)容，給出了實驗結(jié)果，并將結(jié)果與現(xiàn)有的算法進(jìn)行了對比分析。 Regular Tetrahedron Map。 NonConvex Polyhedron。 Enhanced Marching Cubes。到了20世紀(jì)70年代末，Shamos(沙莫斯)和Hoey(霍伊)利用計算機(jī)有效地計算出平面點集的Voronoi圖，并發(fā)表了一篇著名的論文，從此一門新的學(xué)科——計算幾何從算法設(shè)計與分析中孕育而生[1]。Minkowski和算法作為計算幾何研究領(lǐng)域中的一個分支，在理論和應(yīng)用上都有著重要的意義。尤其在機(jī)器人學(xué)領(lǐng)域，Minkowski和算法起到了重要的作用，主要應(yīng)用在機(jī)器人的運動規(guī)劃中。機(jī)器人學(xué)有著極其廣泛的研究和應(yīng)用領(lǐng)域，這些領(lǐng)域體現(xiàn)出廣泛的學(xué)科交叉，涉及眾多的課題，如機(jī)器人控制、智能、傳感、機(jī)器人裝配以及機(jī)器語言等，在工業(yè)、農(nóng)業(yè)、空間和海洋以及國防等領(lǐng)域得到越來越普遍的應(yīng)用。路徑規(guī)劃問題是指在有障礙物的工作環(huán)境中尋找一條恰當(dāng)?shù)膹慕o定初始位姿到終止位姿的運動路徑，使機(jī)器人在運動過程中能安全、無碰撞地繞過所有障礙物[5]。為了更好地解決機(jī)器人的路徑規(guī)劃問題，人們往往用多面體模型來模擬工作空間中的機(jī)器人與障礙物，其中多面體又可以分為凸多面體和凹多面體。根據(jù)工作環(huán)境，機(jī)器人的路徑規(guī)劃可以分為動態(tài)路徑規(guī)劃和靜態(tài)路徑規(guī)劃。對于軌跡已知的情況下的規(guī)劃可以將其轉(zhuǎn)化為若干靜態(tài)問題解決；但對于運動軌跡未知的情況，機(jī)器人需要在運動中不斷地檢測與障礙物之間的碰撞情況。在這種條件下，機(jī)器人可根據(jù)先驗環(huán)境模型找出從起始點到目標(biāo)點的可行或最優(yōu)路徑，并沿著這條路徑順利地完成任務(wù)。Minkowski和是計算無碰撞路徑的一個重要工具，可以定義為，在歐幾里得空間中，假設(shè)P和Q為兩個封閉的幾何對象，那么P和Q的Minkowski和為幾何對象M，其中p和q分別是P和Q上的點，p+q是p和q的位置矢量和[7]。假設(shè)多面體P為工作空間中的任意一個障礙物，多面體R為沿平面做平移運動的機(jī)器人，則P所對應(yīng)的R障礙物為，其中R與R關(guān)于坐標(biāo)原點對稱。可見，研究兩個幾何對象的Minkowski和求和算法，對于解決機(jī)器人的路徑規(guī)劃問題有著十分重要的現(xiàn)實價值。目前研究人員已經(jīng)提出了計算三維空間內(nèi)兩個多面體的Minkowski和的多種不同方法，主要目標(biāo)都是計算Minkowski和的邊界值，并提供一些方法來表示它[10]。 國外研究現(xiàn)狀1987年，(OutputSensitive)算法，該算法定義了二維平面上的一個操作，稱作卷積(Convolution)[11]。1993年，它以傾斜圖(Slope Diagram)表示法為基礎(chǔ)[13]。通過使用立體投影(Stereographic Projection)方法，多面體的傾斜圖轉(zhuǎn)換為二維圖形，這樣就把問題降低到較低維數(shù)的空間中進(jìn)行解決。基于上面的剖分框架，2002年，并提出了多種不同的剖分方法[16]。2000年，[19]中給出了計算普通多邊形的Minkowski和算法，該算法是基于CGAL(Computational Geometry Algorithm Library)[20]實現(xiàn)的。2002年，E. ，提供了為建造平面集合的精確、有效的Minkow