三維空間內(nèi)凹多面體的Minkowski和的算法研究

1、學(xué)位論文三維空間內(nèi)凹多面體的minkowski和的算法研究2009年11月工學(xué)碩士學(xué)位論文三維空間內(nèi)凹多面體的minkowski和的算法研究碩士研究生：導(dǎo)師：申請(qǐng)學(xué)位級(jí)別：工學(xué)碩士學(xué) 科、專 業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)所 在 單 位：信息科學(xué)與工程學(xué)院授予學(xué)位單位：classified index: tp301.6u.d.c.: 654dissertation for the master degree in engineeringresearch on computing minkowski sum of non-convex polyhedral in thress demensioncandid

2、ate:supervisor:academic degree applied for:master of engineeringspeciality:computer application technologyuniversity:yanshan university碩士學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：此處所提交的碩士學(xué)位論文三維空間內(nèi)凹多面體的minkowski和的算法研究，是本人在導(dǎo)師指導(dǎo)下，在攻讀碩士學(xué)位期間獨(dú)立進(jìn)行研究工作所取得的成果。據(jù)本人所知，論文中除已注明部分外不包含他人已發(fā)表或撰寫過的研究成果。對(duì)本文的研究工作做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式注明。本聲明的法律結(jié)

3、果將完全由本人承擔(dān)。 作者簽字 日期： 年 月 日碩士學(xué)位論文使用授權(quán)書三維空間內(nèi)凹多面體的minkowski和的算法研究系本人在攻讀碩士學(xué)位期間在導(dǎo)師指導(dǎo)下完成的碩士學(xué)位論文。本論文的研究成果歸所有，本人如需發(fā)表將署名為第一完成單位及相關(guān)人員。本人完全了解關(guān)于保存、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向有關(guān)部門送交論文的復(fù)印件和電子版本，允許論文被查閱和借閱。本人授權(quán)，可以采用影印、縮印或其他復(fù)制手段保存論文，可以公布論文的全部或部分內(nèi)容。 保密，在 年解密后適用本授權(quán)書。本學(xué)位論文屬于不保密。（請(qǐng)?jiān)谝陨舷鄳?yīng)方框內(nèi)打“” ）作者簽名： 日期： 年 月 日導(dǎo)師簽名： 日期： 年 月 日摘要摘 要

4、計(jì)算幾何是計(jì)算機(jī)理論科學(xué)的一個(gè)重要分支，該學(xué)科已經(jīng)有了巨大的發(fā)展，產(chǎn)生了一系列的理論成果。minkowski和算法作為計(jì)算幾何研究領(lǐng)域中的一個(gè)分支，在理論和應(yīng)用上都有著重要的意義，其研究成果已在機(jī)器人學(xué)、動(dòng)態(tài)仿真、計(jì)算機(jī)圖形學(xué)等許多領(lǐng)域中得到了廣泛的應(yīng)用，尤其在機(jī)器人學(xué)領(lǐng)域，它是計(jì)算無碰撞路徑的一個(gè)重要工具。因此，如何快速而準(zhǔn)確地計(jì)算避障路徑，一直是國內(nèi)外學(xué)者研究的重要課題。首先，在對(duì)國內(nèi)外研究現(xiàn)狀進(jìn)行綜合分析的基礎(chǔ)上，進(jìn)一步研究了計(jì)算兩個(gè)凸多面體minkowski和的求和算法。本文脫離以往算法中基于傳統(tǒng)的高斯映射的算法，以減少計(jì)算平面劃分疊置的次數(shù)、提高算法的執(zhí)行效率為目標(biāo)，提出了正四面體映

5、射和點(diǎn)投影的概念，通過計(jì)算凸多面體的正四面體映射和點(diǎn)投影，把三維空間的問題轉(zhuǎn)換到二維平面進(jìn)行解決。其次，凸剖分是計(jì)算凹多面體的minkowski和的一個(gè)重要步驟。為了有效地計(jì)算凹多面體的minkowski和，在研究了國內(nèi)外許多凸剖分算法后，本文采用集合論和圖論的思想，提出了基于成功回路的凹多面體的剖分算法，同時(shí)對(duì)剖分算法的時(shí)間復(fù)雜度進(jìn)行了分析。再次，給出了計(jì)算凹多面體的minkowski和算法的總體思想。采用成功回路的算法對(duì)凹多面體進(jìn)行剖分，得到若干子凸多面體；利用正四面體映射和點(diǎn)投影的算法計(jì)算所有可能成對(duì)的子凸多面體的minkowski和；通過已改進(jìn)的enhanced marching cu

6、bes算法合并子凸多面體的minkowski和多面體的邊界。最后，通過實(shí)驗(yàn)驗(yàn)證了上述的研究內(nèi)容，給出了實(shí)驗(yàn)結(jié)果，并將結(jié)果與現(xiàn)有的算法進(jìn)行了對(duì)比分析。關(guān)鍵詞 計(jì)算幾何；正四面體映射；點(diǎn)投影；凹多面體；成功回路；enhanced marching cubes；minkowski和iiiabstractabstractcomputational geometry is an important embranchment of computer theoretical science. the subject has already made a tremendous development and

7、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, computer graphics, and so on, especially in the field of robotics, it is an

8、 important tool for computing collision-free 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.

9、in order to reduce the amount of computing 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 pr

10、oblem. through this method, it can reduce the problem in 3d to 2d. secondly, convex decomposition is an important step of computing minkowski sum of two non-convex polyhedral. so, for effectively computing the minkowski sum of non-convex polyhedral, the papers uses the idea of set theory and graph t

11、heory and propose a new algorithm to decompose non-convex polyhedron that based on successful loop after studying the convex decomposition algorithms. at the same time, the complexity of the algorithm is analyzed.thirdly, the paper gives the overall idea of computing the minkowski sum of non-convex

12、polyhedral. it uses successful loop to decompose non-convex polyhedral into convex pieces, then computes 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 mi

13、nkowski sum of the sub polyhedral. finally, we validate the above algorithm and give the results. we also do some comparison and analysis with the existing algorithm.keywords computational geometry; regular tetrahedron map; point projection; non-convex polyhedron; successful loop; enhanced marching

14、cubes; minkowski sum目錄目錄摘 要iabstractii第1章 緒論11.1 課題研究意義11.2 minkowski和算法的研究現(xiàn)狀21.2.1 國外研究現(xiàn)狀31.2.2 國內(nèi)研究現(xiàn)狀41.3 minkowski和算法的應(yīng)用61.3.1 機(jī)器人路徑規(guī)劃61.3.2 碰撞檢測(cè)61.4 本文研究內(nèi)容71.5 本文組織結(jié)構(gòu)8第2章 理論基礎(chǔ)92.1 相關(guān)的幾何定義92.1.1 歐幾里得空間92.1.2 點(diǎn)92.1.3 直線與線段92.1.4 多面體102.1.5 平面圖及平面劃分102.1.6 凸集與凸包102.2 基礎(chǔ)知識(shí)及內(nèi)容102.2.1 minkowski和的定義102

15、.2.2 minkowski和的性質(zhì)112.2.3 平面劃分的疊置122.2.4 邊界表示法132.2.5 移動(dòng)立方體算法132.3 算法與數(shù)據(jù)結(jié)構(gòu)132.3.1 算法142.3.2 數(shù)據(jù)結(jié)構(gòu)152.4 本章小結(jié)18第3章 計(jì)算凸多面體的精確minkowski和193.1 引言193.2 現(xiàn)有的minkowski和求和算法193.3 相關(guān)定義213.4 正四面體映射213.4.1 正四面體映射的定義213.4.2 空間坐標(biāo)轉(zhuǎn)換關(guān)系223.4.3 數(shù)據(jù)結(jié)構(gòu)及相關(guān)信息243.5 點(diǎn)投影253.5.1 點(diǎn)投影的定義253.5.2 空間坐標(biāo)轉(zhuǎn)換關(guān)系263.5.3 數(shù)據(jù)結(jié)構(gòu)及相關(guān)信息283.6 基于正四

16、面體映射和點(diǎn)投影的minkowski和求和算法283.6.1 算法思想293.6.2 算法描述303.6.3 算法分析333.7 本章小結(jié)34第4章 計(jì)算凹多面體的minkowski和354.1 引言354.2 凹多面體minkowski和求和算法概述354.3 凹多面體凸剖分算法364.3.1 凸剖分算法的研究現(xiàn)狀364.3.2 相關(guān)定義與定理374.3.3 基于成功回路的凹多面體的剖分算法394.3.4 算法分析434.4 合并子minkowski和多面體434.4.1 相關(guān)定義434.4.2 合并子minkowski和多面體算法概述444.4.3 改進(jìn)的合并算法454.4.4 算法分析4

17、74.5 計(jì)算簡單凹多面體的minkowski和算法總體思想474.6 本章小結(jié)48第5章 實(shí)驗(yàn)與分析495.1 實(shí)驗(yàn)環(huán)境設(shè)置495.2 leda簡介495.3 精確實(shí)數(shù)計(jì)算505.4 minkowski和求和算法的實(shí)驗(yàn)驗(yàn)證515.4.1 凸多面體minkowski和求和算法實(shí)現(xiàn)及分析525.4.2 簡單凹多面體minkowski和求和算法實(shí)現(xiàn)及分析565.5 本章小結(jié)61結(jié) 論63參考文獻(xiàn)65第1章 緒論第1章 緒論1.1 課題研究意義“計(jì)算幾何”這個(gè)術(shù)語最初是由minsky和papert作為模式識(shí)別的代用詞被提出來，到了a.r.forrost才有了正式的定義：“對(duì)幾何外形信息的計(jì)算機(jī)表示、

18、分析和綜合”。到了20世紀(jì)70年代末，shamos(沙莫斯)和hoey(霍伊)利用計(jì)算機(jī)有效地計(jì)算出平面點(diǎn)集的voronoi圖，并發(fā)表了一篇著名的論文，從此一門新的學(xué)科計(jì)算幾何從算法設(shè)計(jì)與分析中孕育而生1。該領(lǐng)域中的問題所帶來的挑戰(zhàn)性，也使得一大批科研人員為之嘔心瀝血、辛勤耕耘，從而使這一嶄新的研究領(lǐng)域在比較短的時(shí)間內(nèi)取得了輝煌的成果，對(duì)許多問題已經(jīng)有了一系列比較成熟的計(jì)算幾何算法。minkowski和算法作為計(jì)算幾何研究領(lǐng)域中的一個(gè)分支，在理論和應(yīng)用上都有著重要的意義。它廣泛應(yīng)用于機(jī)器人學(xué)、計(jì)算機(jī)圖形學(xué)、固體建模、計(jì)算機(jī)動(dòng)畫和cad/cam等領(lǐng)域2。尤其在機(jī)器人學(xué)領(lǐng)域，minkowski和算

19、法起到了重要的作用，主要應(yīng)用在機(jī)器人的運(yùn)動(dòng)規(guī)劃中。機(jī)器人學(xué)(robotics)是與機(jī)器人設(shè)計(jì)、制造和應(yīng)用等相關(guān)的學(xué)科，主要研究機(jī)器人的控制與被處理物體之間的相互關(guān)系3。機(jī)器人學(xué)有著極其廣泛的研究和應(yīng)用領(lǐng)域，這些領(lǐng)域體現(xiàn)出廣泛的學(xué)科交叉，涉及眾多的課題，如機(jī)器人控制、智能、傳感、機(jī)器人裝配以及機(jī)器語言等，在工業(yè)、農(nóng)業(yè)、空間和海洋以及國防等領(lǐng)域得到越來越普遍的應(yīng)用。機(jī)器人學(xué)的最終目標(biāo)之一，就是設(shè)計(jì)出一個(gè)獨(dú)立自主的機(jī)器人，它能夠接受高級(jí)任務(wù)并且在沒有人的干涉下自主執(zhí)行并完成任務(wù)4。路徑規(guī)劃問題是指在有障礙物的工作環(huán)境中尋找一條恰當(dāng)?shù)膹慕o定初始位姿到終止位姿的運(yùn)動(dòng)路徑，使機(jī)器人在運(yùn)動(dòng)過程中能安全、無碰

20、撞地繞過所有障礙物5。因此，能否對(duì)運(yùn)動(dòng)路徑進(jìn)行快速而準(zhǔn)確地規(guī)劃成為衡量機(jī)器人智能高低的一個(gè)重要標(biāo)準(zhǔn)。為了更好地解決機(jī)器人的路徑規(guī)劃問題，人們往往用多面體模型來模擬工作空間中的機(jī)器人與障礙物，其中多面體又可以分為凸多面體和凹多面體。這樣，檢測(cè)機(jī)器人與障礙物之間的碰撞情況就轉(zhuǎn)換為檢測(cè)多個(gè)幾何體之間的碰撞情況6。根據(jù)工作環(huán)境，機(jī)器人的路徑規(guī)劃可以分為動(dòng)態(tài)路徑規(guī)劃和靜態(tài)路徑規(guī)劃。動(dòng)態(tài)環(huán)境即時(shí)變環(huán)境，含有運(yùn)動(dòng)軌跡已知或未知的障礙物。對(duì)于軌跡已知的情況下的規(guī)劃可以將其轉(zhuǎn)化為若干靜態(tài)問題解決；但對(duì)于運(yùn)動(dòng)軌跡未知的情況，機(jī)器人需要在運(yùn)動(dòng)中不斷地檢測(cè)與障礙物之間的碰撞情況。在靜態(tài)環(huán)境下，機(jī)器人僅僅能夠做平移或翻

21、轉(zhuǎn)運(yùn)動(dòng)，通常障礙物為靜態(tài)的剛性物體，并且機(jī)器人與障礙物的幾何形狀和位置是已知的。在這種條件下，機(jī)器人可根據(jù)先驗(yàn)環(huán)境模型找出從起始點(diǎn)到目標(biāo)點(diǎn)的可行或最優(yōu)路徑，并沿著這條路徑順利地完成任務(wù)。這個(gè)看似簡單的問題在計(jì)算幾何學(xué)中卻成為具有挑戰(zhàn)性的問題，并且成為機(jī)器人研究領(lǐng)域中的一個(gè)研究熱點(diǎn)問題。minkowski和是計(jì)算無碰撞路徑的一個(gè)重要工具，可以定義為，在歐幾里得空間中，假設(shè)p和q為兩個(gè)封閉的幾何對(duì)象，那么p和q的minkowski和為幾何對(duì)象m，其中p和q分別是p和q上的點(diǎn)，p+q是p和q的位置矢量和7。也就是說若，則有。假設(shè)多面體p為工作空間中的任意一個(gè)障礙物，多面體r為沿平面做平移運(yùn)動(dòng)的機(jī)器人

22、，則p所對(duì)應(yīng)的r障礙物為，其中-r與r關(guān)于坐標(biāo)原點(diǎn)對(duì)稱。除此之外，minkowski和還可以用來計(jì)算兩個(gè)多面體之間的滲透深度、精確檢測(cè)物體之間的碰撞情況以及應(yīng)用到機(jī)器人裝配仿真等等，有著很廣泛的應(yīng)用8?？梢?，研究兩個(gè)幾何對(duì)象的minkowski和求和算法，對(duì)于解決機(jī)器人的路徑規(guī)劃問題有著十分重要的現(xiàn)實(shí)價(jià)值。1.2 minkowski和算法的研究現(xiàn)狀1983年，t.lozano-perez首次利用minkowski和來計(jì)算位姿空間障礙物(configuration space obstacle)，并應(yīng)用到機(jī)器人的運(yùn)動(dòng)規(guī)劃中9。目前研究人員已經(jīng)提出了計(jì)算三維空間內(nèi)兩個(gè)多面體的minkowski和的

23、多種不同方法，主要目標(biāo)都是計(jì)算minkowski和的邊界值，并提供一些方法來表示它10。其中，計(jì)算凸多面體的minkowski和的方法已經(jīng)有了成熟的算法，而凹多面體的minkowski和一直停留在獲得近似值。1.2.1 國外研究現(xiàn)狀1987年，l.j.guibas和r.seidel提出了計(jì)算簡單多胞體minkowski和多面體的敏感輸出(output-sensitive)算法，該算法定義了二維平面上的一個(gè)操作，稱作卷積(convolution)11。1996年，j.basch和l.guibas等人擴(kuò)展了上述算法，提出了以定義在多面體運(yùn)動(dòng)軌跡上的卷積計(jì)算為基礎(chǔ)的方法來計(jì)算三維空間內(nèi)多面體的min

24、kowski和12。1993年，p.k.ghosh為計(jì)算凸多面體和凹多面體的minkowski和提出了統(tǒng)一的算法，它以傾斜圖(slope diagram)表示法為基礎(chǔ)13。計(jì)算兩個(gè)多面體的minkowski和等同于分別計(jì)算兩個(gè)多面體的傾斜圖，然后合并它們的傾斜圖，并從合并的傾斜圖中提取minkowski和的邊界值14。通過使用立體投影(stereographic projection)方法，多面體的傾斜圖轉(zhuǎn)換為二維圖形，這樣就把問題降低到較低維數(shù)的空間中進(jìn)行解決。1997年，b.aronov和m.shair等人提出了計(jì)算普通多邊形或多面體的minkowski和的基本框架：首先，對(duì)每個(gè)多邊形(或

25、多面體)進(jìn)行凸剖分，得到若干個(gè)子凸多邊形(或多面體)；然后，計(jì)算取自不同多邊形(或多面體)的所有可能成對(duì)的子凸剖分的minkowski和；最后，合并第二步中所有子minkowski和多邊形(多面體)15?；谏厦娴钠史挚蚣?，2002年，p.k.agarwal和e.flato等人給出了計(jì)算凹多邊形的minkowski和算法，并提出了多種不同的剖分方法16。由于凹多面體的minkowski和求和算法過于復(fù)雜，目前，人們主要研究能夠得到滿足某些標(biāo)準(zhǔn)的近似值的求和算法，如文獻(xiàn)17,18。2000年，e.flato和d.halperin在文獻(xiàn)19中給出了計(jì)算普通多邊形的minkowski和算法，該算法是

26、基于cgal(computational geometry algorithm library)20實(shí)現(xiàn)的。2001年，基于ghosh在文獻(xiàn)13中提出的傾斜圖表示法，h.bekker和j.b.t.m.roerdink比較了三種計(jì)算凸多面體minkowski和的方法，最終提出了在線性時(shí)間內(nèi)計(jì)算三維空間凸多面體minkowski和的新方法，但是該方法只對(duì)非常簡單的凸多面體適用21。2002年，e. flato和f.fogel等人給出了minkowski和算法的應(yīng)用領(lǐng)域，提供了為建造平面集合的精確、有效的minkowski和所使用的軟件包22。2003年，y.y.wu和j.j.shah等人分別對(duì)基于

27、凸包(convex hull)的凸多面體的minkowski和求和算法與基于傾斜圖的凸多面體的minkowski和求和算法進(jìn)行了優(yōu)化23。遵循文獻(xiàn)13提出的方法，2007年，e.fogel和d.halperin提出了基于立方體高斯映射cgm(cubical gaussian map)計(jì)算三維空間內(nèi)凸多面體的精確minkowski和算法24，該算法也是基于cgal實(shí)現(xiàn)的。1.2.2 國內(nèi)研究現(xiàn)狀國內(nèi)對(duì)minkowski和算法的研究起步較晚。其中，對(duì)凸多面體的minkowski和算法的研究取得了一些很好的成果；對(duì)凹多面體的剖分和子minkowski和多面體的合并的研究也有了一定的進(jìn)展。2007年，

28、郭希娟和高艷麗提出了基于正四面體中心投影rtcp(regular tetrahedron central projection)和三角形內(nèi)簡單平面凸劃分的疊置算法計(jì)算凸多面體精確minkowski和的優(yōu)化算法25?；谡拿骟w中心投影算法，2008年，郭希娟和謝蕾又給出了進(jìn)一步優(yōu)化基于正四面體高斯映射rtgm(regular tetrahedron gaussian map)的算法26。通過對(duì)國內(nèi)外研究現(xiàn)狀的分析，可以得出計(jì)算多邊形或者多面體的minkowski和算法主要有六種，即基于凸包的求和算法、基于凸剖分的求和算法、基于傾斜圖的求和算法、基于立方體高斯映射的求和算法、基于正四面體中心投影

29、的求和算法以及基于正四面體高斯映射的算法。其中，基于凸包的minkowski和求和算法是非常著名的算法之一，該算法直接源于minkowski和的定義，它可以表示為：，其中，ch表示凸包操作，、分別表示多面體p和q中頂點(diǎn)的集合15。在計(jì)算minkowski和多面體的過程中，該算法需要區(qū)分內(nèi)部點(diǎn)、外部點(diǎn)和邊界點(diǎn)，創(chuàng)建這些點(diǎn)集的凸包不但需要很高的計(jì)算費(fèi)用，并且該算法的計(jì)算結(jié)果不是圖而是一個(gè)點(diǎn)集?；趦A斜圖的minkowski和求和算法，根據(jù)高斯映射的規(guī)則，把多面體的體元(包括多面體的頂點(diǎn)、棱、面)映射到單位球表面，并采用立體投影方法把每個(gè)多面體的傾斜圖轉(zhuǎn)化為平面圖形，然后計(jì)算平面圖形的疊置，從疊置的

30、結(jié)果中抽取minkowski和的邊界值。采用立體投影方法不僅會(huì)使算法在處理退化情況時(shí)存在著很大的局限性，而且會(huì)增加算法的實(shí)現(xiàn)難度，很難得到精確的計(jì)算結(jié)果?；诹⒎襟w高斯映射的minkowski和求和算法，通過自定義的立方體高斯映射，把三維空間內(nèi)的凸多面體的體元映射到立方體表面，從而得到六個(gè)平面劃分面，計(jì)算兩個(gè)凸多面體的minkowski和就等同于計(jì)算六對(duì)平面劃分的疊置。通過計(jì)算六對(duì)平面劃分中各面的附加信息，得到minkowski和多面體的立方體高斯映射表示，最后求逆映射得到精確的minkowski和多面體?；谡拿骟w中心投影的minkowski和算法，首先按照高斯映射規(guī)則，將凸多面體映射到單

31、位球面上，再取單位球面的外切正四面體，通過自定義的正四面體中心投影得到凸多面體在正四面體上的投影。求兩個(gè)凸多面體的minkowski和等同于求四對(duì)平面劃分的疊置。通過計(jì)算四對(duì)平面劃分中各面的附加信息，得到新多面體的正四面體中心投影，最后求逆映射得到minkowski和多面體?；谡拿骟w高斯映射的minkowski和算法，為計(jì)算兩個(gè)給定位置和形態(tài)的凸多面體的minkowski和表示，取凸多面體的外切正四面體，根據(jù)自定義的正四面體高斯映射把凸多面體映射到外切正四面體的四個(gè)表面上，求兩個(gè)凸多面體的minkowski和等同于求四對(duì)平面劃分的疊置，通過計(jì)算平面劃分中各面的附加信息，得到新多面體的正四面

32、體高斯映射，最后求逆映射得到minkowski和多面體?；谕蛊史值膍inkowski和算法，是計(jì)算凹多邊形或凹多面體的minkowski和的常用算法。對(duì)于二維空間內(nèi)的凹多邊形而言，常用的方法就是把凹多邊形剖分為若干個(gè)凸多邊形，通過計(jì)算凸多邊形minkowski子和的并來得到凹多邊形的minkowski和。理論上，剖分策略的選擇與求和速度無關(guān)，但實(shí)際上，它嚴(yán)重影響著整個(gè)求和算法的運(yùn)行時(shí)間，特別是計(jì)算三維空間內(nèi)的凹多面體的minkowski和。因此，迫切需要尋找某種策略來降低計(jì)算凹多面體的minkowski和的求和算法的時(shí)間復(fù)雜度，同時(shí)由于基于剖分法中的合并算法的復(fù)雜度很高，目前仍然沒有人提出計(jì)

33、算凹多面體的精確minkowski和的算法。因此研究凹多面體的精確minkowski和求和算法是一項(xiàng)具有挑戰(zhàn)性及重要意義的課題。1.3 minkowski和算法的應(yīng)用minkowski和算法在許多領(lǐng)域中有著廣泛的應(yīng)用，如機(jī)器人學(xué)、碰撞檢測(cè)、模擬仿真、計(jì)算機(jī)圖形學(xué)等等，下面重點(diǎn)介紹該算法在機(jī)器人路徑規(guī)劃和碰撞檢測(cè)中的應(yīng)用。1.3.1 機(jī)器人路徑規(guī)劃機(jī)器人學(xué)的最終目標(biāo)之一，就是設(shè)計(jì)出獨(dú)立自主的機(jī)器人。在指揮這種機(jī)器人時(shí)，只需要告訴它去做什么，而不必告訴它如何去做，其中尤為重要的一個(gè)方面就是，機(jī)器人應(yīng)該懂得如何對(duì)自己的運(yùn)動(dòng)進(jìn)行規(guī)劃27。路徑規(guī)劃是機(jī)器人學(xué)算法中的一個(gè)重要問題，其本質(zhì)是在眾多障礙物之間

34、為機(jī)器人尋找一條最優(yōu)或近似最優(yōu)的無碰撞路徑，該問題經(jīng)常用位姿空間方法來描述。所謂的位姿空間，也稱c空間，是機(jī)器人的參數(shù)空間；機(jī)器人的工作空間是機(jī)器人在其中實(shí)際運(yùn)動(dòng)的那個(gè)空間，也就是真實(shí)的世界。自由c空間(free configuration space)是機(jī)器人避免與障礙物發(fā)生碰撞的所有位置點(diǎn)的集合27。為了規(guī)劃路徑，需要擁有一個(gè)能夠捕捉自由位姿空間連通性的表示，而minkowski和算法可以來計(jì)算所需的表示，并且能夠獲得一條精確的無碰撞路徑。假設(shè)多面體p為工作空間中的障礙物，多面體r為移動(dòng)機(jī)器人，那么通過計(jì)算位姿空間障礙物來確定一條無碰撞的路徑，這個(gè)問題就轉(zhuǎn)變?yōu)橛?jì)算多面體p與-r的minko

35、wski和，其中-r與r關(guān)于坐標(biāo)原點(diǎn)對(duì)稱。1.3.2 碰撞檢測(cè)碰撞檢測(cè)是檢測(cè)兩個(gè)物體在空間中是否重疊或它們的邊界線是否至少共享一個(gè)點(diǎn)17。在虛擬環(huán)境中，由于用戶的交互，物體之間經(jīng)常發(fā)生碰撞，為保持虛擬環(huán)境的真實(shí)感和用戶的沉浸感，快速精確的碰撞檢測(cè)是必不可少的。傳統(tǒng)的碰撞檢測(cè)方法主要有空間分解法和層次包圍盒技術(shù)，這兩種算法都只能近似的檢測(cè)物體是否發(fā)生碰撞，minkowski和算法能夠精確地檢測(cè)出物體之間是否發(fā)生碰撞。該問題用滲透深度來描述，兩個(gè)多面體p和q的滲透深度是指使得兩個(gè)多面體不相交，其中一個(gè)多面體必須移動(dòng)的最小距離17。通過計(jì)算原心到minkowski和()表面上的最小距離來得到。若滲透

36、深度大于等于零，說明兩個(gè)多面體發(fā)生碰撞，反之，兩個(gè)多面體不會(huì)發(fā)生碰撞。1.4 本文研究內(nèi)容本文在對(duì)國內(nèi)外研究現(xiàn)狀全面分析的基礎(chǔ)上，完成對(duì)三維空間內(nèi)凹多面體minkowski和求和算法的進(jìn)一步研究，主要包括下述內(nèi)容。(1)計(jì)算簡單凸多面體的minkowski和的求和算法 通過深入研究正四面體中心投影算法和正四面體高斯映射算法，發(fā)現(xiàn)這兩種算法都需要計(jì)算四次劃分平面疊置，并且都沒有給出具體的映射函數(shù)關(guān)系式。因此，本文提出了正四面體映射和點(diǎn)投影的概念，把三維空間的問題轉(zhuǎn)換到二維空間進(jìn)行解決，且只需要計(jì)算一對(duì)平面劃分的疊置，更高效的計(jì)算凸多面體的精確minkowski和。(2)簡單凹多面體的剖分算法 通

37、過深入研究國內(nèi)外凹多面體的剖分算法，發(fā)現(xiàn)大多數(shù)的剖分算法會(huì)生成大量新點(diǎn)，產(chǎn)生很多凸多面體。因此，本文采用圖論和集合論的思想，提出了基于成功回路的凹多面體的剖分算法，該算法不僅不產(chǎn)生新的頂點(diǎn)，而且能夠處理有空洞的多面體。(3)計(jì)算簡單凹多面體的minkowski和求和算法 首先，根據(jù)(2)中提出的剖分算法對(duì)凹多面體進(jìn)行剖分，得到若干子凸多面體；其次，利用(1)中提出的求和算法計(jì)算所有可能成對(duì)的子凸多面體的minkowski和；最后，在合并子凸minkowski和多面體時(shí)，利用已改進(jìn)的enhanced marching cubes算法獲得凹多面體的近似的minkowski和多面體邊界。1.5 本文

38、組織結(jié)構(gòu)論文分為5章，其余部分組織如下。第2章介紹與本課題相關(guān)的基礎(chǔ)理論。首先，是對(duì)基本幾何定義的介紹；然后，闡述了minkowski和的定義、性質(zhì)及相關(guān)的幾何操作；最后，介紹有關(guān)算法的基本知識(shí)，該部分為課題的研究打下了堅(jiān)實(shí)的理論基礎(chǔ)。第3章提出了一種新的計(jì)算凸多面體的minkowski和的求和算法。首先，介紹現(xiàn)有的求和算法，分析它的主要思想；然后，以提高算法的執(zhí)行效率為目標(biāo)，提出正四面體映射和點(diǎn)投影的概念，給出正四面體映射和點(diǎn)投影的映射規(guī)則，并由此提出基于該映射的凸多面體的精確minkowski和求和算法。最后，對(duì)算法的時(shí)間復(fù)雜度進(jìn)行了分析。第4章提出了一種新的凹多面體的剖分算法，并給出了計(jì)

39、算凹多面體的minkowski和求和算法思想。以提高算法的精確度和效率為目標(biāo)，首先，本章采用圖論和集合論的思想，提出了基于成功回路的凹多面體的剖分算法；其次，在合并子凸多面體minkowski和時(shí)，利用現(xiàn)有已改進(jìn)的enhanced marching cubes算法，最終獲得近似的多面體minkowski和邊界；最后，給出計(jì)算簡單凹多面體minkowski和的算法的總體思想。第5章是實(shí)驗(yàn)與分析，對(duì)所研究的內(nèi)容及算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證并給出實(shí)驗(yàn)結(jié)果。最后，對(duì)本課題進(jìn)行了全面總結(jié)，同時(shí)針對(duì)課題中存在的問題提出了進(jìn)一步改進(jìn)的思路，并規(guī)劃了未來的研究方向。7第2章 理論基礎(chǔ)第2章 理論基礎(chǔ)下面給出一些本章中

40、將要用到的幾何概念、定義和基礎(chǔ)知識(shí)。2.1 相關(guān)的幾何定義本文考慮的對(duì)象是歐幾里得三維空間中的點(diǎn)集，假設(shè)有一個(gè)參考坐標(biāo)系，使得每個(gè)點(diǎn)表示為相應(yīng)維數(shù)的笛卡爾坐標(biāo)的向量。除了點(diǎn)之外，還將考慮包含兩個(gè)給定點(diǎn)的直線、直線上兩定點(diǎn)確定的直線段、三個(gè)給定點(diǎn)確定的平面等。下面給出本文所涉及到的基本幾何對(duì)象的定義。2.1.1 歐幾里得空間若用(或)表示維歐幾里得空間，那么具有度量的實(shí)數(shù)的元組空間，稱為歐幾里得空間28。2.1.2 點(diǎn)中的點(diǎn)定義為一個(gè)元組。點(diǎn)也可以解釋為有個(gè)分量的向量，此向量的起點(diǎn)為坐標(biāo)原點(diǎn)，終點(diǎn)為點(diǎn)28。點(diǎn)是整個(gè)幾何學(xué)的基礎(chǔ)，它只有位置，沒有大小。2.1.3 直線與線段在中給定兩個(gè)不同的點(diǎn)和，

41、線性組合(是實(shí)數(shù)，即)是中的一條直線28。給定中兩個(gè)不同的點(diǎn)和，若在線性組合中加入條件，則得到點(diǎn)和的凸組合，即(，)，35第3章 計(jì)算凸多面體的精確minkowski和此凸組合描述了連接兩點(diǎn)和的直線段，并記為(無序?qū)?28。線段是直線的一部分，并以兩個(gè)端點(diǎn)為界限。2.1.4 多面體由若干平面多邊形圍成的封閉連通的空間區(qū)域稱為多面體(允許有洞)29。一般說來，多面體是指邊界和內(nèi)部域的并。多邊形的頂點(diǎn)和邊是多面體的頂點(diǎn)和邊，多邊形是多面體的小面。2.1.5 平面圖及平面劃分假設(shè)圖g=(v，e)，其中v為頂點(diǎn)集，e為邊集，如果圖g能夠沒有交叉地嵌入平面，那么稱圖g為平面圖。平面圖的直線平面嵌入確定平

42、面的一個(gè)劃分，稱為平面劃分(也稱平面剖分)28。設(shè)平面圖的頂點(diǎn)數(shù)、邊數(shù)和區(qū)域數(shù)分別為v，e和f，則由歐拉公式有v-e+f=2。2.1.6 凸集與凸包假設(shè)s是二維平面上的非空點(diǎn)集，p1和p2是s中任意兩點(diǎn)，若存在一點(diǎn)p=tp1+(1-t)p2，其中，則稱s是凸集30。這就是說，如果s中任意兩點(diǎn)所連線段全部位于s之中，那么s是凸的。此定義可以推廣到高維。平面中n個(gè)點(diǎn)的有限集合s的凸包c(diǎn)h(s)是一個(gè)凸多邊形30。在中，s的ch(s)是包含s的最小凸域的邊界，其頂點(diǎn)為s中的點(diǎn)，并且s中所有的點(diǎn)均包含在ch(s)內(nèi)。2.2 基礎(chǔ)知識(shí)及內(nèi)容下面將給出minkowski和的定義、性質(zhì)及相關(guān)的幾何操作。2.

43、2.1 minkowski和的定義minkowski和的定義是由德國數(shù)學(xué)家hermann minkowski最早提出的。在歐幾里得空間內(nèi)，假設(shè)p和q為兩個(gè)封閉的幾何對(duì)象，它們的minkowski和可以表示為：在不改變兩個(gè)操作數(shù)相對(duì)方位的情況下，一個(gè)操作數(shù)q沿著另一個(gè)操作數(shù)p的外輪廓滑行，q的參考點(diǎn)經(jīng)過的軌跡就是p和q的minkowski和。如圖2-1所示。圖2-1 p和q的minkowski和fig. 2-1 the minkowski sum of p and q另外，p和q的minkowski和也可以表示為幾何對(duì)象m，其中p和q分別為屬于幾何對(duì)象p和q的點(diǎn)，為位置矢量與的矢量和。例如，在歐

44、幾里得二維平面內(nèi)，假設(shè)并且，那么有。下面給出二維平面內(nèi)兩個(gè)三角形的minkowski和，如圖2-2所示。pqqp圖2-2 三角形p和q的minkowski和fig. 2-2 minkowski sum of triangle p and q2.2.2 minkowski和的性質(zhì)從上面的定義可知，計(jì)算兩個(gè)幾何對(duì)象s1與s2的minkowski和具有下列性質(zhì)31,32。(1)與實(shí)數(shù)運(yùn)算相似，求兩個(gè)幾何對(duì)象的minkowski和滿足交換規(guī)則和分配規(guī)則，即式子s1s2=s2s1與s1(s2s3)=(s1s2)(s1s3)成立。(2)設(shè)幾何對(duì)象s1與s2為兩個(gè)凸多邊形，分別含有n和m條邊，則minkow

45、ski和是由不超過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ì)算所需

46、要的時(shí)間為o(n3m3)。2.2.3 平面劃分的疊置求平面劃分的疊置是將兩個(gè)或者多個(gè)平面劃分圖層進(jìn)行疊加，并產(chǎn)生一個(gè)新平面劃分圖層的操作，其結(jié)果是將原來平面劃分中的圖元分割成新圖元，新圖元綜合了原來兩個(gè)圖層或者多個(gè)圖層的屬性33。給定兩個(gè)平面劃分d1和d2，它們的疊置是一個(gè)新的平面劃分，記作overlay(d1,d2)。如果在overlay(d1,d2)中存在一張面f，在d1和d2中分別存在面和，那么面f是的一個(gè)極大連通子集27。簡單的說是由來自d1和d2的邊共同在平面上導(dǎo)出一個(gè)子區(qū)域劃分，如圖2-3所示，黃色點(diǎn)為新的交點(diǎn)。圖2-3 平面劃分的疊置fig. 2-3 overlay of pla

47、nar subdivisions一般的疊置問題，首先給出分別對(duì)應(yīng)于d1和d2的兩個(gè)雙向鏈接邊表，然后計(jì)算出對(duì)應(yīng)于overlay(d1,d2)的雙向鏈接邊表，同時(shí)要求對(duì)overlay(d1,d2)中的每張平面劃分面加上標(biāo)注，以指明在d1和d2中它分別屬于哪張平面劃分面，這樣能夠直接訪問存儲(chǔ)在這些面記錄中的附加信息。雙向鏈接邊表的定義將在2.3節(jié)中給出。2.2.4 邊界表示法物體可以通過描述它的邊界來表示，稱為邊界表示法34。邊界就是物體內(nèi)部點(diǎn)與外部點(diǎn)的分界面。定義了物體的邊界，該物體也就被唯一的定義了。邊界表示法的一個(gè)很重要的特點(diǎn)是描述了物體的信息，包括幾何信息與拓?fù)湫畔蓚€(gè)方面。物體的幾何信息

48、是指頂點(diǎn)、邊、面的位置、大小、形狀等幾何數(shù)據(jù)。拓?fù)湫畔⑹侵肝矬w上所有的頂點(diǎn)、棱邊、面間的連接情況35。2.2.5 移動(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)部的等值面。2.3 算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)專門研究從解決

49、非數(shù)值計(jì)算的現(xiàn)實(shí)問題中抽象出來的數(shù)據(jù)在計(jì)算機(jī)中如何表示、快速存取和處理的方法。計(jì)算幾何與計(jì)算機(jī)科學(xué)中的算法設(shè)計(jì)與分析、數(shù)據(jù)結(jié)構(gòu)等學(xué)科的關(guān)系非常密切，它常常要用到這些學(xué)科的知識(shí)。設(shè)計(jì)求解幾何問題的算法首先應(yīng)該具備兩個(gè)條件，一是分析并理解問題的幾何特征，二是掌握計(jì)算幾何中的幾何結(jié)構(gòu)、特殊的算法設(shè)計(jì)方法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。由于本文的研究內(nèi)容與幾何算法的設(shè)計(jì)與分析相關(guān)，因此就必須介紹一下關(guān)于算法和數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)。2.3.1 算法算法是對(duì)特定問題求解步驟的一種描述，是指令的有限序列，是求解一個(gè)問題類的無二義性的有窮過程28。這里的求解過程是指求解問題執(zhí)行的一步一步動(dòng)作的集合，每一步動(dòng)作只需要有限的存儲(chǔ)

50、單元和有限的操作時(shí)間。簡單的說，算法就是解決特定問題的方法。描述一個(gè)算法可以采用文字?jǐn)⑹?，也可以采用傳統(tǒng)流程圖、n-s圖或pad圖等等。一個(gè)算法具有下列重要特性。(1)有窮性 算法只執(zhí)行有限步，并且每步應(yīng)該在有限的時(shí)間內(nèi)完成。(2)確定性 算法中的每一條指令必須有確切的含義，無二義性。(3)可行性 算法中描述的操作都必須足夠基本，即都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。(4)輸入 算法具有零個(gè)或多個(gè)輸入。(5)輸出 算法具有一個(gè)或多個(gè)輸出，沒有輸出的算法沒有任何意義。算法的復(fù)雜度是衡量算法效率的方法，其中包括算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度。為了說明復(fù)雜度的概念，先介紹問題規(guī)模的概

51、念。隨著處理問題的數(shù)據(jù)增大，處理會(huì)越來越困難復(fù)雜，把描述數(shù)據(jù)增大程度的量叫做問題規(guī)模37。規(guī)模越大，消耗的時(shí)間越多。利用某算法處理一個(gè)問題規(guī)模為n的輸入所需要的時(shí)間，稱為該算法的時(shí)間復(fù)雜度，它是規(guī)模n的函數(shù)，記為t(n)。算法的空間復(fù)雜度是指解決問題的算在執(zhí)行時(shí)所占用的存儲(chǔ)空間，記作s(n)28。下面主要討論算法的時(shí)間復(fù)雜度。由于一般不需要知道精確的時(shí)間耗費(fèi)，只要知道時(shí)間耗費(fèi)的增長率大體在什么范圍內(nèi)即可，因此引入算法復(fù)雜度階的概念。如果對(duì)某一個(gè)正常數(shù)c，一個(gè)算法能在時(shí)間cn2內(nèi)處理規(guī)模是n的輸入，則稱此算法的時(shí)間復(fù)雜度是o(n2)，讀作“n2階”。一般情況下，都是取一個(gè)簡單形式的函數(shù)作為階數(shù)的

52、規(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ī)模為

53、n的輸入出現(xiàn)的概率不同，所以有時(shí)要考慮加權(quán)平均特性。2.3.2 數(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è)計(jì)時(shí)首先要確定相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。本文除了用到通用的數(shù)據(jù)結(jié)構(gòu)鄰接表、隊(duì)列以外，還用到一種特殊的結(jié)構(gòu)：雙向鏈接邊表dcel(doubly connected edge list)27。雙向鏈接邊表適于表示嵌入到平面的平面劃分，它是一種簡單而有效的數(shù)據(jù)結(jié)構(gòu)，并且是一種基于邊的表示方法，同時(shí)包含頂點(diǎn)和面(平面劃分面)的信息。也就是說，對(duì)于任一個(gè)子區(qū)域，與之相對(duì)應(yīng)的雙向鏈接邊表為其中的每個(gè)頂

54、點(diǎn)，每條半邊和每張面都設(shè)置了一個(gè)記錄，即頂點(diǎn)記錄、半邊記錄和面記錄，在這些記錄中，分別存有幾何信息、拓?fù)湫畔⒑透郊有畔ⅰＴ陔p向鏈接邊表數(shù)據(jù)結(jié)構(gòu)中，規(guī)定每條無向邊都由兩條具有相對(duì)方向的半邊(half edge)表示，這兩條半邊互稱為孿生半邊，并且都與它左側(cè)的面相關(guān)聯(lián)；對(duì)于任何一條半邊，都有唯一的一條后繼半邊，以及唯一的一條前驅(qū)半邊；每條有向半邊都有起點(diǎn)和終點(diǎn)。下面給出dcel結(jié)構(gòu)的各組成部分，如圖2-4所示。一般情況下，在對(duì)應(yīng)頂點(diǎn)的頂點(diǎn)記錄中，設(shè)有一個(gè)名為coordinates(v)的域，用來存放頂點(diǎn)的坐標(biāo)。此外，還有一個(gè)名為incidentedge(v)的指針，指向以頂點(diǎn)為起點(diǎn)的某一條半邊。在

55、對(duì)應(yīng)于面的面記錄中，設(shè)有一名為outercomponent(f )的指針，指向該面的外邊界(outer boundary)上的任意一條半邊。若是無界面(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)無需

56、存儲(chǔ)，因?yàn)樗扔趏rigin(twin(e)。半邊起點(diǎn)的選取，要使得從半邊的起點(diǎn)走向終點(diǎn)的過程中，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)圖2-4 dcel結(jié)構(gòu)的各組成部分fig. 2-4 component of dcel structure