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

三維空間內(nèi)凹多面體的Minkowski和的算法研究第1章 緒論1.1 課題研究意義“計算幾何”這個術(shù)語最初是由Minsky和Papert作為模式識別的代用詞被提出來，到了A.R.Forrost才有了正式的定義：“對幾何外形信息的計算機(jī)表示、分析和綜合”。到了20世紀(jì)70年代末，Shamos(沙莫斯)和Hoey(霍伊)利用計算機(jī)有效地計算出平面點(diǎn)集的Voronoi圖，并發(fā)表了一篇著名的，從此一門新的學(xué)科計算幾何從算法設(shè)計與分析中孕育而生1。該領(lǐng)域中的問題所帶來的挑戰(zhàn)性，也使得一大批科研人員為之嘔心瀝血、辛勤耕耘，從而使這一嶄新的研究領(lǐng)域在比較短的時間內(nèi)取得了輝煌的成果，對許多問題已經(jīng)有了一系列比較成熟的計算幾何算法。Minkowski和算法作為計算幾何研究領(lǐng)域中的一個分支，在理論和應(yīng)用上都有著重要的意義。它廣泛應(yīng)用于機(jī)器人學(xué)、計算機(jī)圖形學(xué)、固體建模、計算機(jī)動畫和CAD/CAM等領(lǐng)域2。尤其在機(jī)器人學(xué)領(lǐng)域，Minkowski和算法起到了重要的作用，主要應(yīng)用在機(jī)器人的運(yùn)動規(guī)劃中。機(jī)器人學(xué)(Robotics)是與機(jī)器人設(shè)計、制造和應(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è)計出一個獨(dú)立自主的機(jī)器人，它能夠接受高級任務(wù)并且在沒有人的干涉下自主執(zhí)行并完成任務(wù)4。路徑規(guī)劃問題是指在有障礙物的工作環(huán)境中尋找一條恰當(dāng)?shù)膹慕o定初始位姿到終止位姿的運(yùn)動路徑，使機(jī)器人在運(yùn)動過程中能安全、無碰撞地繞過所有障礙物5。因此，能否對運(yùn)動路徑進(jìn)行快速而準(zhǔn)確地規(guī)劃成為衡量機(jī)器人智能高低的一個重要標(biāo)準(zhǔn)。為了更好地解決機(jī)器人的路徑規(guī)劃問題，人們往往用多面體模型來模擬工作空間中的機(jī)器人與障礙物，其中多面體又可以分為凸多面體和凹多面體。這樣，檢測機(jī)器人與障礙物之間的碰撞情況就轉(zhuǎn)換為檢測多個幾何體之間的碰撞情況6。根據(jù)工作環(huán)境，機(jī)器人的路徑規(guī)劃可以分為動態(tài)路徑規(guī)劃和靜態(tài)路徑規(guī)劃。動態(tài)環(huán)境即時變環(huán)境，含有運(yùn)動軌跡已知或未知的障礙物。對于軌跡已知的情況下的規(guī)劃可以將其轉(zhuǎn)化為若干靜態(tài)問題解決；但對于運(yùn)動軌跡未知的情況，機(jī)器人需要在運(yùn)動中不斷地檢測與障礙物之間的碰撞情況。在靜態(tài)環(huán)境下，機(jī)器人僅僅能夠做平移或翻轉(zhuǎn)運(yùn)動，通常障礙物為靜態(tài)的剛性物體，并且機(jī)器人與障礙物的幾何形狀和位置是已知的。在這種條件下，機(jī)器人可根據(jù)先驗(yàn)環(huán)境模型找出從起始點(diǎn)到目標(biāo)點(diǎn)的可行或最優(yōu)路徑，并沿著這條路徑順利地完成任務(wù)。這個看似簡單的問題在計算幾何學(xué)中卻成為具有挑戰(zhàn)性的問題，并且成為機(jī)器人研究領(lǐng)域中的一個研究熱點(diǎn)問題。Minkowski和是計算無碰撞路徑的一個重要工具，可以定義為，在歐幾里得空間中，假設(shè)P和Q為兩個封閉的幾何對象，那么P和Q的Minkowski和為幾何對象M，其中p和q分別是P和Q上的點(diǎn)，p+q是p和q的位置矢量和7。也就是說若，則有。假設(shè)多面體P為工作空間中的任意一個障礙物，多面體R為沿平面做平移運(yùn)動的機(jī)器人，則P所對應(yīng)的R障礙物為，其中-R與R關(guān)于坐標(biāo)原點(diǎn)對稱。除此之外，Minkowski和還可以用來計算兩個多面體之間的滲透深度、精確檢測物體之間的碰撞情況以及應(yīng)用到機(jī)器人裝配仿真等等，有著很廣泛的應(yīng)用8?？梢?，研究兩個幾何對象的Minkowski和求和算法，對于解決機(jī)器人的路徑規(guī)劃問題有著十分重要的現(xiàn)實(shí)價值。1.2 Minkowski和算法的研究現(xiàn)狀1983年，T.Lozano-perez首次利用Minkowski和來計算位姿空間障礙物(Configuration Space Obstacle)，并應(yīng)用到機(jī)器人的運(yùn)動規(guī)劃中9。目前研究人員已經(jīng)提出了計算三維空間內(nèi)兩個多面體的Minkowski和的多種不同方法，主要目標(biāo)都是計算Minkowski和的邊界值，并提供一些方法來表示它10。其中，計算凸多面體的Minkowski和的方法已經(jīng)有了成熟的算法，而凹多面體的Minkowski和一直停留在獲得近似值。1.2.1 國外研究現(xiàn)狀1987年，L.J.Guibas和R.Seidel提出了計算簡單多胞體Minkowski和多面體的敏感輸出(Output-Sensitive)算法，該算法定義了二維平面上的一個操作，稱作卷積(Convolution)11。1996年，J.Basch和L.Guibas等人擴(kuò)展了上述算法，提出了以定義在多面體運(yùn)動軌跡上的卷積計算為基礎(chǔ)的方法來計算三維空間內(nèi)多面體的Minkowski和12。1993年，P.K.Ghosh為計算凸多面體和凹多面體的Minkowski和提出了統(tǒng)一的算法，它以傾斜圖(Slope Diagram)表示法為基礎(chǔ)13。計算兩個多面體的Minkowski和等同于分別計算兩個多面體的傾斜圖，然后合并它們的傾斜圖，并從合并的傾斜圖中提取Minkowski和的邊界值14。通過使用立體投影(Stereographic Projection)方法，多面體的傾斜圖轉(zhuǎn)換為二維圖形，這樣就把問題降低到較低維數(shù)的空間中進(jìn)行解決。1997年，B.Aronov和M.Shair等人提出了計算普通多邊形或多面體的Minkowski和的基本框架：首先，對每個多邊形(或多面體)進(jìn)行凸剖分，得到若干個子凸多邊形(或多面體)；然后，計算取自不同多邊形(或多面體)的所有可能成對的子凸剖分的Minkowski和；最后，合并第二步中所有子Minkowski和多邊形(多面體)15?；谏厦娴钠史挚蚣埽?0XX年，P.K.Agarwal和E.Flato等人給出了計算凹多邊形的Minkowski和算法，并提出了多種不同的剖分方法16。由于凹多面體的Minkowski和求和算法過于復(fù)雜，目前，人們主要研究能夠得到滿足某些標(biāo)準(zhǔn)的近似值的求和算法，如文獻(xiàn)17,18。2000年，E.Flato和D.Halperin在文獻(xiàn)19中給出了計算普通多邊形的Minkowski和算法，該算法是基于CGAL(putational Geometry Algorithm Library)20實(shí)現(xiàn)的。20XX年，基于Ghosh在文獻(xiàn)13中提出的傾斜圖表示法，H.Bekker和J.B.T.M.Roerdink比較了三種計算凸多面體Minkowski和的方法，最終提出了在線性時間內(nèi)計算三維空間凸多面體Minkowski和的新方法，但是該方法只對非常簡單的凸多面體適用21。20XX年，E. Flato和F.Fogel等人給出了Minkowski和算法的應(yīng)用領(lǐng)域，提供了為建造平面集合的精確、有效的Minkowski和所使用的軟件包22。20XX年，Y.Y.Wu和J.J.Shah等人分別對基于凸包(Convex Hull)的凸多面體的Minkowski和求和算法與基于傾斜圖的凸多面體的Minkowski和求和算法進(jìn)行了優(yōu)化23。遵循文獻(xiàn)13提出的方法，20XX年，E.Fogel和D.Halperin提出了基于立方體高斯映射CGM(Cubical Gaussian Map)計算三維空間內(nèi)凸多面體的精確Minkowski和算法24，該算法也是基于CGAL實(shí)現(xiàn)的。1.2.2 國內(nèi)研究現(xiàn)狀國內(nèi)對Minkowski和算法的研究起步較晚。其中，對凸多面體的Minkowski和算法的研究取得了一些很好的成果；對凹多面體的剖分和子Minkowski和多面體的合并的研究也有了一定的進(jìn)展。20XX年，郭希娟和高艷麗提出了基于正四面體中心投影RTCP(Regular Tetrahedron Central Projection)和三角形內(nèi)簡單平面凸劃分的疊置算法計算凸多面體精確Minkowski和的優(yōu)化算法25?；谡拿骟w中心投影算法，20XX年，郭希娟和謝蕾又給出了進(jìn)一步優(yōu)化基于正四面體高斯映射RTGM(Regular Tetrahedron Gaussian Map)的算法26。通過對國內(nèi)外研究現(xiàn)狀的分析，可以得出計算多邊形或者多面體的Minkowski和算法主要有六種，即基于凸包的求和算法、基于凸剖分的求和算法、基于傾斜圖的求和算法、基于立方體高斯映射的求和算法、基于正四面體中心投影的求和算法以及基于正四面體高斯映射的算法。其中，基于凸包的Minkowski和求和算法是非常著名的算法之一，該算法直接源于Minkowski和的定義，它可以表示為：，其中，CH表示凸包操作，、分別表示多面體P和Q中頂點(diǎn)的集合15。在計算Minkowski和多面體的過程中，該算法需要區(qū)分內(nèi)部點(diǎn)、外部點(diǎn)和邊界點(diǎn)，創(chuàng)建這些點(diǎn)集的凸包不但需要很高的計算費(fèi)用，并且該算法的計算結(jié)果不是圖而是一個點(diǎn)集?；趦A斜圖的Minkowski和求和算法，根據(jù)高斯映射的規(guī)則，把多面體的體元(包括多面體的頂點(diǎn)、棱、面)映射到單位球表面，并采用立體投影方法把每個多面體的傾斜圖轉(zhuǎn)化為平面圖形，然后計算平面圖形的疊置，從疊置的結(jié)果中抽取Minkowski和的邊界值。采用立體投影方法不僅會使算法在處理退化情況時存在著很大的局限性，而且會增加算法的實(shí)現(xiàn)難度，很難得到精確的計算結(jié)果。基于立方體高斯映射的Minkowski和求和算法，通過自定義的立方體高斯映射，把三維空間內(nèi)的凸多面體的體元映射到立方體表面，從而得到六個平面劃分面，計算兩個凸多面體的Minkowski和就等同于計算六對平面劃分的疊置。通過計算六對平面劃分中各面的附加信息，得到Minkowski和多面體的立方體高斯映射表示，最后求逆映射得到精確的Minkowski和多面體?；谡拿骟w中心投影的Minkowski和算法，首先按照高斯映射規(guī)則，將凸多面體映射到單位球面上，再取單位球面的外切正四面體，通過自定義的正四面體中心投影得到凸多面體在正四面體上的投影。求兩個凸多面體的Minkowski和等同于求四對平面劃分的疊置。通過計算四對平面劃分中各面的附加信息，得到新多面體的正四面體中心投影，最后求逆映射得到Minkowski和多面體?；谡拿骟w高斯映射的Minkowski和算法，為計算兩個給定位置和形態(tài)的凸多面體的Minkowski和表示，取凸多面體的外切正四面體，根據(jù)自定義的正四面體高斯映射把凸多面體映射到外切正四面體的四個表面上，求兩個凸多面體的Minkowski和等同于求四對平面劃分的疊置，通過計算平面劃分中各面的附加信息，得到新多面體的正四面體高斯映射，最后求逆映射得到Minkowski和多面體?；谕蛊史值腗inkowski和算法，是計算凹多邊形或凹多面體的Minkowski和的常用算法。對于二維空間內(nèi)的凹多邊形而言，常用的方法就是把凹多邊形剖分為若干個凸多邊形，通過計算凸多邊形Minkowski子和的并來得到凹多邊形的Minkowski和。理論上，剖分策略的選擇與求和速度無關(guān)，但實(shí)際上，它嚴(yán)重影響著整個求和算法的運(yùn)行時間，特別是計算三維空間內(nèi)的凹多面體的Minkowski和。因此，迫切需要尋找某種策略來降低計算凹多面體的Minkowski和的求和算法的時間復(fù)雜度，同時由于基于剖分法中的合并算法的復(fù)雜度很高，目前仍然沒有人提出計算凹多面體的精確Minkowski和的算法。因此研究凹多面體的精確Minkowski和求和算法是一項(xiàng)具有挑戰(zhàn)性及重要意義的課題。1.3 Minkowski和算法的應(yīng)用Minkowski和算法在許多領(lǐng)域中有著廣泛的應(yīng)用，如機(jī)器人學(xué)、碰撞檢測、模擬仿真、計算機(jī)圖形學(xué)等等，下面重點(diǎn)介紹該算法在機(jī)器人路徑規(guī)劃和碰撞檢測中的應(yīng)用。1.3.1 機(jī)器人路徑規(guī)劃機(jī)器人學(xué)的最終目標(biāo)之一，就是設(shè)計出獨(dú)立自主的機(jī)器人。在指揮這種機(jī)器人時，只需要告訴它去做什么，而不必告訴它如何去做，其中尤為重要的一個方面就是，機(jī)器人應(yīng)該懂得如何對自己的運(yùn)動進(jìn)行規(guī)劃27。路徑規(guī)劃是機(jī)器人學(xué)算法中的一個重要問題，其本質(zhì)是在眾多障礙物之間為機(jī)器人尋找一條最優(yōu)或近似最優(yōu)的無碰撞路徑，該問題經(jīng)常用位姿空間方法來描述。所謂的位姿空間，也稱C空間，是機(jī)器人的參數(shù)空間；機(jī)器人的工作空間是機(jī)器人在其中實(shí)際運(yùn)動的那個空間，也就是真實(shí)的世界。自由C空間(Free Configuration Space)是機(jī)器人避免與障礙物發(fā)生碰撞的所有位置點(diǎn)的集合27。為了規(guī)劃路徑，需要擁有一個能夠捕捉自由位姿空間連通性的表示，而Minkowski和算法可以來計算所需的表示，并且能夠獲得一條精確的無碰撞路徑。假設(shè)多面體P為工作空間中的障礙物，多面體R為移動機(jī)器人，那么通過計算位姿空間障礙物來確定一條無碰撞的路徑，這個問題就轉(zhuǎn)變?yōu)橛嬎愣嗝骟wP與-R的Minkowski和，其中-R與R關(guān)于坐標(biāo)原點(diǎn)對稱。1.3.2 碰撞檢測碰撞檢測是檢測兩個物體在空間中是否重疊或它們的邊界線是否至少共享一個點(diǎn)17。在虛擬環(huán)境中，由于用戶的交互，物體之間經(jīng)常發(fā)生碰撞，為保持虛擬環(huán)境的真實(shí)感和用戶的沉浸感，快速精確的碰撞檢測是必不可少的。傳統(tǒng)的碰撞檢測方法主要有空間分解法和層次包圍盒技術(shù)，這兩種算法都只能近似的檢測物體是否發(fā)生碰撞，Minkowski和算法能夠精確地檢測出物體之間是否發(fā)生碰撞。該問題用滲透深度來描述，兩個多面體P和Q的滲透深度是指使得兩個多面體不相交，其中一個多面體必須移動的最小距離17。通過計算原心到Minkowski和()表面上的最小距離來得到。若滲透深度大于等于零，說明兩個多面體發(fā)生碰撞，反之，兩個多面體不會發(fā)生碰撞。1.4 本文研究內(nèi)容本文在對國內(nèi)外研究現(xiàn)狀全面分析的基礎(chǔ)上，完成對三維空間內(nèi)凹多面體Minkowski和求和算法的進(jìn)一步研究，主要包括下述內(nèi)容。(1)計算簡單凸多面體的Minkowski和的求和算法 通過深入研究正四面體中心投影算法和正四面體高斯映射算法，發(fā)現(xiàn)這兩種算法都需要計算四次劃分平面疊置，并且都沒有給出具體的映射函數(shù)關(guān)系式。因此，本文提出了正四面體映射和點(diǎn)投影的概念，把三維空間的問題轉(zhuǎn)換到二維空間進(jìn)行解決，且只需要計算一對平面劃分的疊置，更高效的計算凸多面體的精確Minkowski和。(2)簡單凹多面體的剖分算法 通過深入研究國內(nèi)外凹多面體的剖分算法，發(fā)現(xiàn)大多數(shù)的剖分算法會生成大量新點(diǎn)，產(chǎn)生很多凸多面體。因此，本文采用圖論和集合論的思想，提出了基于成功回路的凹多面體的剖分算法，該算法不僅不產(chǎn)生新的頂點(diǎn)，而且能夠處理有空洞的多面體。(3)計算簡單凹多面體的Minkowski和求和算法 首先，根據(jù)(2)中提出的剖分算法對凹多面體進(jìn)行剖分，得到若干子凸多面體；其次，利用(1)中提出的求和算法計算所有可能成對的子凸多面體的Minkowski和；最后，在合并子凸Minkowski和多面體時，利用已改進(jìn)的Enhanced Marching Cubes算法獲得凹多面體的近似的Minkowski和多面體邊界。1.5 本文組織結(jié)構(gòu)分為5章，其余部分組織如下。第2章介紹與本課題相關(guān)的基礎(chǔ)理論。首先，是對基本幾何定義的介紹；然后，闡述了Minkowski和的定義、性質(zhì)及相關(guān)的幾何操作；最后，介紹有關(guān)算法的基本知識，該部分為課題的研究打下了堅實(shí)的理論基礎(chǔ)。第3章提出了一種新的計算凸多面體的Minkowski和的求和算法。首先，介紹現(xiàn)有的求和算法，分析它的主要思想；然后，以提高算法的執(zhí)行效率為目標(biāo)，提出正四面體映射和點(diǎn)投影的概念，給出正四面體映射和點(diǎn)投影的映射規(guī)則，并由此提出基于該映射的凸多面體的精確Minkowski和求和算法。最后，對算法的時間復(fù)雜度進(jìn)行了分析。第4章提出了一種新的凹多面體的剖分算法，并給出了計算凹多面體的Minkowski和求和算法思想。以提高算法的精確度和效率為目標(biāo)，首先，本章采用圖論和集合論的思想，提出了基于成功回路的凹多面體的剖分算法；其次，在合并子凸多面體Minkowski和時，利用現(xiàn)有已改進(jìn)的Enhanced Marching Cubes算法，最終獲得近似的多面體Minkowski和邊界；最后，給出計算簡單凹多面體Minkowski和的算法的總體思想。第5章是實(shí)驗(yàn)與分析，對所研究的內(nèi)容及算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證并給出實(shí)驗(yàn)結(jié)果。最后，對本課題進(jìn)行了全面總結(jié)，同時針對課題中存在的問題提出了進(jìn)一步改進(jìn)的思路，并規(guī)劃了未來的研究方向。第2章 理論基礎(chǔ)下面給出一些本章中將要用到的幾何概念、定義和基礎(chǔ)知識。2.1 相關(guān)的幾何定義本文考慮的對象是歐幾里得三維空間中的點(diǎn)集，假設(shè)有一個參考坐標(biāo)系，使得每個點(diǎn)表示為相應(yīng)維數(shù)的笛卡爾坐標(biāo)的向量。除了點(diǎn)之外，還將考慮包含兩個給定點(diǎn)的直線、直線上兩定點(diǎn)確定的直線段、三個給定點(diǎn)確定的平面等。下面給出本文所涉及到的基本幾何對象的定義。2.1.1 歐幾里得空間若用(或)表示維歐幾里得空間，那么具有度量的實(shí)數(shù)的元組空間，稱為歐幾里得空間28。2.1.2 點(diǎn)中的點(diǎn)定義為一個元組。點(diǎn)也可以解釋為有個分量的向量，此向量的起點(diǎn)為坐標(biāo)原點(diǎn)，終點(diǎn)為點(diǎn)28。點(diǎn)是整個幾何學(xué)的基礎(chǔ)，它只有位置，沒有大小。2.1.3 直線與線段在中給定兩個不同的點(diǎn)和，線性組合(是實(shí)數(shù)，即)是中的一條直線28。給定中兩個不同的點(diǎn)和，若在線性組合中加入條件，則得到點(diǎn)和的凸組合，即(，)，此凸組合描述了連接兩點(diǎn)和的直線段，并記為(無序?qū)?28。線段是直線的一部分，并以兩個端點(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為平面圖。平面圖的直線平面嵌入確定平面的一個劃分，稱為平面劃分(也稱平面剖分)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個點(diǎn)的有限集合S的凸包CH(S)是一個凸多邊形30。在中，S的CH(S)是包含S的最小凸域的邊界，其頂點(diǎn)為S中的點(diǎn)，并且S中所有的點(diǎn)均包含在CH(S)內(nèi)。2.2 基礎(chǔ)知識及內(nèi)容下面將給出Minkowski和的定義、性質(zhì)及相關(guān)的幾何操作。2.2.1 Minkowski和的定義Minkowski和的定義是由德國數(shù)學(xué)家Hermann Minkowski最早提出的。在歐幾里得空間內(nèi)，假設(shè)P和Q為兩個封閉的幾何對象，它們的Minkowski和可以表示為：在不改變兩個操作數(shù)相對方位的情況下，一個操作數(shù)Q沿著另一個操作數(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和也可以表示為幾何對象M，其中p和q分別為屬于幾何對象P和Q的點(diǎn)，為位置矢量與的矢量和。例如，在歐幾里得二維平面內(nèi)，假設(shè)并且，那么有。下面給出二維平面內(nèi)兩個三角形的Minkowski和，如圖2-2所示。PQQP圖2-2 三角形P和Q的Minkowski和Fig. 2-2 Minkowski Sum of triangle P and Q2.2.2 Minkowski和的性質(zhì)從上面的定義可知，計算兩個幾何對象S1與S2的Minkowski和具有下列性質(zhì)31,32。(1)與實(shí)數(shù)運(yùn)算相似，求兩個幾何對象的Minkowski和滿足交換規(guī)則和分配規(guī)則，即式子S1S2=S2S1與S1(S2S3)=(S1S2)(S1S3)成立。(2)設(shè)幾何對象S1與S2為兩個凸多邊形，分別含有n和m條邊，則Minkowski和是由不超過n+m條邊構(gòu)成的凸多邊形。(3)設(shè)S1與S2為兩個多邊形，分別含有n和m個頂點(diǎn)，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個頂點(diǎn)，S1與S2的Minkowski和所需要的時間分為下列幾種情況。若S1與S2均為凸多面體，則計算所需要的時間為O(n2m2)。若S1與S2均為非凸多面體，則計算所需要的時間為O(n3m3)。2.2.3 平面劃分的疊置求平面劃分的疊置是將兩個或者多個平面劃分圖層進(jìn)行疊加，并產(chǎn)生一個新平面劃分圖層的操作，其結(jié)果是將原來平面劃分中的圖元分割成新圖元，新圖元綜合了原來兩個圖層或者多個圖層的屬性33。給定兩個平面劃分D1和D2，它們的疊置是一個新的平面劃分，記作Overlay(D1,D2)。如果在Overlay(D1,D2)中存在一張面f，在D1和D2中分別存在面和，那么面f是的一個極大連通子集27。簡單的說是由來自D1和D2的邊共同在平面上導(dǎo)出一個子區(qū)域劃分，如圖2-3所示，黃色點(diǎn)為新的交點(diǎn)。圖2-3 平面劃分的疊置Fig. 2-3 Overlay of planar subdivisions一般的疊置問題，首先給出分別對應(yīng)于D1和D2的兩個雙向鏈接邊表，然后計算出對應(yīng)于Overlay(D1,D2)的雙向鏈接邊表，同時要求對Overlay(D1,D2)中的每張平面劃分面加上標(biāo)注，以指明在D1和D2中它分別屬于哪張平面劃分面，這樣能夠直接訪問存儲在這些面記錄中的附加信息。雙向鏈接邊表的定義將在2.3節(jié)中給出。2.2.4 邊界表示法物體可以通過描述它的邊界來表示，稱為邊界表示法34。邊界就是物體內(nèi)部點(diǎn)與外部點(diǎn)的分界面。定義了物體的邊界，該物體也就被唯一的定義了。邊界表示法的一個很重要的特點(diǎn)是描述了物體的信息，包括幾何信息與拓?fù)湫畔蓚€方面。物體的幾何信息是指頂點(diǎn)、邊、面的位置、大小、形狀等幾何數(shù)據(jù)。拓?fù)湫畔⑹侵肝矬w上所有的頂點(diǎn)、棱邊、面間的連接情況35。2.2.5 移動立方體算法移動立方體MC(Marching Cubes)算法是基于規(guī)則體數(shù)據(jù)抽取等值面的經(jīng)典算法36。傳統(tǒng)的MC算法的基本思想是逐個處理數(shù)據(jù)場中的立方體(體單元)，分類出與等值面相交的立方體，采用插值計算出等值面與立方體的交點(diǎn)。根據(jù)立方體每一頂點(diǎn)與等值面的相對位置，將等值面與立方體的交點(diǎn)按一定方式連接生成等值面，作為等值面在該立方體內(nèi)的一個逼近。該算法對體數(shù)據(jù)中的體素逐個進(jìn)行處理，每個被處理的體素，以三角面片表示其內(nèi)部的等值面。2.3 算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)專門研究從解決非數(shù)值計算的現(xiàn)實(shí)問題中抽象出來的數(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)的基本知識。2.3.1 算法算法是對特定問題求解步驟的一種描述，是指令的有限序列，是求解一個問題類的無二義性的有窮過程28。這里的求解過程是指求解問題執(zhí)行的一步一步動作的集合，每一步動作只需要有限的存儲單元和有限的操作時間。簡單的說，算法就是解決特定問題的方法。描述一個算法可以采用文字?jǐn)⑹觯部梢圆捎脗鹘y(tǒng)流程圖、N-S圖或PAD圖等等。一個算法具有下列重要特性。(1)有窮性 算法只執(zhí)行有限步，并且每步應(yīng)該在有限的時間內(nèi)完成。(2)確定性 算法中的每一條指令必須有確切的含義，無二義性。(3)可行性 算法中描述的操作都必須足夠基本，即都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(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ù)雜度。由于一般不需要知道精確的時間耗費(fèi)，只要知道時間耗費(fèi)的增長率大體在什么范圍內(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ù))，則稱此算法為多項(xiàng)式時間算法。當(dāng)n很大時，指數(shù)時間算法和多項(xiàng)式時間算法存在很大的差別。以多項(xiàng)式時間為限界的算法稱為有效算法。因此應(yīng)該盡可能選用多項(xiàng)式階O(nk)的算法，而不希望用指數(shù)階的算法。算法的時間復(fù)雜度可分為最壞情況的時間復(fù)雜性和平均情況的時間復(fù)雜性30。對于給定規(guī)模為n的各種輸入，某算法執(zhí)行每條指令所需要的時間之和的最大值，稱為該算法的最壞情況的時間復(fù)雜性；對于給定規(guī)模為n的各種輸入，執(zhí)行每條指令所需要的時間之和的平均值，稱為平均情況的時間復(fù)雜性(或期望復(fù)雜性或平均特性)。由于規(guī)模為n的輸入出現(xiàn)的概率不同，所以有時要考慮加權(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è)計時首先要確定相應(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)，并且是一種基于邊的表示方法，同時包含頂點(diǎn)和面(平面劃分面)的信息。也就是說，對于任一個子區(qū)域，與之相對應(yīng)的雙向鏈接邊表為其中的每個頂點(diǎn)，每條半邊和每張面都設(shè)置了一個記錄，即頂點(diǎn)記錄、半邊記錄和面記錄，在這些記錄中，分別存有幾何信息、拓?fù)湫畔⒑透郊有畔?。在雙向鏈接邊表數(shù)據(jù)結(jié)構(gòu)中，規(guī)定每條無向邊都由兩條具有相對方向的半邊(Half Edge)表示，這兩條半邊互稱為孿生半邊，并且都與它左側(cè)的面相關(guān)聯(lián)；對于任何一條半邊，都有唯一的一條后繼半邊，以及唯一的一條前驅(qū)半邊；每條有向半邊都有起點(diǎn)和終點(diǎn)。下面給出DCEL結(jié)構(gòu)的各組成部分，如圖2-4所示。一般情況下，在對應(yīng)頂點(diǎn)的頂點(diǎn)記錄中，設(shè)有一個名為Coordinates(v)的域，用來存放頂點(diǎn)的坐標(biāo)。此外，還有一個名為IncidentEdge(v)的指針，指向以頂點(diǎn)為起點(diǎn)的某一條半邊。在對應(yīng)于面的面記錄中，設(shè)有一名為Outerponent(f )的指針，指向該面的外邊界(Outer Boundary)上的任意一條半邊。若是無界面(Unbouned Face)，則此指針為Null。此外，還有一個名為Innerponent(f )的列表，其中設(shè)有多個指針，分別對應(yīng)于該面的各個空洞；每個指針?biāo)傅?，是其對?yīng)空洞的邊界上的某一條半邊。在對應(yīng)于半邊的半邊記錄中，設(shè)有一個名為Origin(e)的指針，指向該半邊的起點(diǎn)；另有一個名為Twin(e)的指針，指向其孿生半邊；還有一個名為IncidentFace(e)的指針，指向位于半邊左邊的面，即半邊參與圍成的那張面。半邊的終點(diǎn)無需存儲，因?yàn)樗扔贠rigin(Twin(e)。半邊起點(diǎn)的選取，要使得從半邊的起點(diǎn)走向終點(diǎn)的過程中，IncidentFace(e)位于的左側(cè)。此外，半邊記錄中還設(shè)有兩個指針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 ponent of DCEL structure每個頂點(diǎn)和每條邊所對應(yīng)的信息量，都是常數(shù)規(guī)模的。面記錄占用的空間可能會更多一些，因?yàn)槊鎓中含有多少個空洞，列表Innerponent(f )中就需要有多少項(xiàng)。然而，只要將所有的Innerponent(f )列表合起來統(tǒng)計，就會發(fā)現(xiàn)其中指向任何一條半邊的指針都不會超過一個。由此可以得出結(jié)論：每個平面劃分所需存儲空間的規(guī)模，與該平面劃分本身的復(fù)雜度呈線性關(guān)系。e1,a下面給出了一個簡單的平面劃分區(qū)域的子區(qū)域所對應(yīng)的雙向鏈接邊表，如圖2-5所示。表2-1、表2-2和表2-3分別給出相應(yīng)的頂點(diǎn)記錄、面記錄、半邊記錄。e1,be4,ae4,be3,be3,af1e2,ae2,bv4v3v2v1f2圖2-5 簡單的平面劃分Fig. 2-5 Simple planar subdivision表2-1 頂點(diǎn)記錄Table 2-1 Records of verticesVertexCoordinatesIncidentEdgev1(0,4)e1,av2(2,4)e4,bv3(2,2)e2,av4(1,2)e2,b表2-2 面記錄Table 2-2 Records of facetsFaceOuterponentInnerponentsf1Nulle1,af2e4,aNull表2-3 半邊記錄Table 2-3 Records of half edgesHalf-edgeOriginTwinIncidentFaceNextPreve1,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)用中，頂點(diǎn)v本身可能不含任何屬性信息，此時，就可以將它們各自的坐標(biāo)，直接存儲在相關(guān)聯(lián)的半邊的Oringe( )域中，而不必專門為頂點(diǎn)記錄定義一種數(shù)據(jù)類型。除此之外，在很多實(shí)際應(yīng)用中，子區(qū)域劃分中的面并不具有任何含義，此時可以完全舍棄掉面記錄，以及各半邊對應(yīng)的IncidentFace( )域。在雙向鏈接表的某些實(shí)現(xiàn)中，可能要求平面劃分的頂點(diǎn)和邊所對應(yīng)的圖是連通的，既然連通圖對應(yīng)的子區(qū)域劃分絕對不會出現(xiàn)空洞，因此列表Innerponent( )也就不必存在了。2.4 本章小結(jié)本章主要對Minkowski和算法涉及的基本知識進(jìn)行了簡要的介紹。幾何學(xué)是整個Minkowski和算法設(shè)計的基礎(chǔ)，本章首先介紹了與研究內(nèi)容相關(guān)的基本幾何對象的定義。其次，描述了Minkowski和的概念及性質(zhì)，并介紹了相關(guān)的幾何操作，如平面劃分的疊置、移動立方體算法等。最后，介紹了有關(guān)算法的基本知識，重點(diǎn)介紹了雙向鏈接邊表。通過對算法所涉及的基本知識的介紹，為后續(xù)研究奠定了基礎(chǔ)。第3章 計算凸多面體的精確Minkowski和3.1 引言在歐幾里得三維空間中，求兩個凸多面體的Minkowski和是一項(xiàng)重要的幾何操作，它等同于兩個凸多面體中所有點(diǎn)的矢量和的集合38。為了提高算法的執(zhí)行效率、加快求和速度，在深入分析現(xiàn)有算法的基礎(chǔ)上，本章脫離以往算法中基于傳統(tǒng)的高斯映射的算法，提出一種全新的計算凸多面體精確Minkowski和的算法。該算法以文獻(xiàn)27中的子區(qū)域劃分的疊置算法為基礎(chǔ)，通過給出一種自定義的映射方式，即正四面體映射和點(diǎn)投影，把三維空間的問題轉(zhuǎn)換到二維空間進(jìn)行解決，求兩個凸多面體的Minkowski和就等同于計算一對平面劃分的疊置。除此之外，還根據(jù)求和的需要及特征完成了屬性分配過程。3.2 現(xiàn)有的Minkowski和求和算法為了求兩個凸多面體的Minkowski和，研究人員已經(jīng)提出了多種有效的方法。下面主要介紹基于立方體高斯映射的凸多面體Minkowski和求和算法，并對其進(jìn)行分析?；诟咚褂成涞亩x，E.Fogel和D.Halperin在文獻(xiàn)24中提出了CGM的概念。它可以描述為：在歐幾里得三維空間內(nèi)，凸多面體的CGM是一個從多面體體元到立方體表面的集值函數(shù)。首先，為凸多面體P的每個點(diǎn)p分配一條指向P的支撐平面的法線向量，則P的每個小面均對應(yīng)著一條法向量，使所有法向量的起始點(diǎn)都處在立方體的中心，這樣多面體的一個小面就能夠映射為立方體某個面上的一個點(diǎn)；然后，按照同樣的映射規(guī)則，多面體的一條邊至多映射為三條連接的線段，它們分別位于三個鄰接的立方體表面上；多面體的一個頂點(diǎn)映射為一個凸多邊形，此多邊形至多位于五個鄰接的立方體表面上。在這里，立方體的邊平行于坐標(biāo)軸，并且長度為2。與基于傾斜圖的求和方法相似，該算法同樣是把三維空間中的問題轉(zhuǎn)換到二維空間進(jìn)行解決，而兩者不同之處在于，后者通過把多面體體元映射到立方體表面，以達(dá)到降維的目的。下面給出這種求和算法的簡單描述。算法3.1：基于CGM的兩個凸多面體的Minkowski和的算法CGMO。輸入：由CGM表示的凸多面體；輸出：,其中P為由CGM表示的Minkowski和多面體。CGMO (P0, P1 Pr, P)Begin(1) P;(2) for (i=1; ir; +i)把的所有邊插入到P中;(3) for (i=0; ir; +i)把的附加信息加入到的相應(yīng)附加信息中;(4) 計算存儲在邊界半邊和邊界頂點(diǎn)內(nèi)的附加信息;(5) 計算Minkowski和多面體的每個小面的方程式;(6) Return P;End在步驟2中，對于Pi表面上的每一條映射邊(不妨設(shè)為e)，均對應(yīng)著一條含有指針的線段l，l在拓?fù)渖系扔谶卐，其指針指向邊e的任意一條半邊。在這一步中，實(shí)際上是把線段l插入到P的表面劃分中；當(dāng)此步結(jié)束時，在P的表面劃分中，每條邊(不妨設(shè)為)都含有一個指針，該指針指向所源于的半邊。整個插入過程主要基于平面直線掃描算法27。在步驟3中，Pi的每個平面劃分面都存儲著相應(yīng)的附加信息，這些附加信息是與劃分面相對應(yīng)的多面體Pi的頂點(diǎn)坐標(biāo)。也就是說，Minkowski和多面體的頂點(diǎn)坐標(biāo)被存儲在P的劃分面內(nèi)。為了計算P的附加信息，對于每個輸入值，都需要遍歷P的所有平面劃分面。采用上面的求和算法計算兩個凸多面體的Minkowski和等同于計算六對平面劃分的疊置，并通過計算存儲在劃分面中的附加信息，最終能夠得到由CGM表示的Minkowski和多面體。該算法僅僅適用于計算凸多面體的Minkowski和，對于凹多面體的情況無能為力。3.3 相關(guān)定義定義4.1：體元 在歐幾里得三維空間中，稱多面體的頂點(diǎn)、棱、面為多面體的體元25。定義4.2：凸多面體(非凸多面體) 把多面體的任一個面展成平面，如果其余的面都位于這個平面的同一側(cè)，這樣的多面體叫凸多面體。反之，則為非凸多面體。定義4.3：外包正四面體 假設(shè)一凸多面體在正四面體內(nèi)部，且正四面體的中心在凸多面體內(nèi)部，則稱該正四面體為凸多面體的外包正四面體。定義4.4：鄰接表(Adjacency List) 對于圖G中的每個頂點(diǎn)vi，把所有鄰接于vi的頂點(diǎn)vj鏈成一個帶頭結(jié)點(diǎn)的單鏈表，這個單鏈表就稱為頂點(diǎn)vi的鄰接表37。3.4 正四面體映射下面首先給出正四面體映射的定義，然后通過選定的空間坐標(biāo)系，根據(jù)映射規(guī)則把凸多面體上的體元映射到正四面體的表面，并給出了具體的映射關(guān)系式。3.4.1 正四面體映射的定義定義4.5：正四面體映射 以凸多面體的外包正四面體的中心為起點(diǎn)(求解時對所有凸多面體的外包正四面體，都定義為單位正四面體)，向凸多面體上的任意點(diǎn)(包括凸多面體的頂點(diǎn)以及邊上的點(diǎn))引射線，該射線與正四面體的交點(diǎn)，為凸多面體體元在正四面體上的映射點(diǎn)，該映射稱為正四面體映射。正四面體映射的映射過程為：凸多面體的點(diǎn)映射為正四面體的面上的點(diǎn)；邊映射為一條或多條連接的線段，并且這些線段處在一個或幾個鄰接的三角形面內(nèi)，假設(shè)凸多面體棱AB的兩個端點(diǎn)映射在不同的面上，分別為面和面，則AB映射為兩條線段，這兩條線段的交點(diǎn)在面和面的相交線上；面映射至多處在三個連接面內(nèi)的凸多邊形。這樣，通過映射得到凸多面體的正四面體映射，也就是正四面體表面的劃分，記作T。并且由于映射源為凸多面體，因此對四個三角形面的劃分均為凸劃分。正四面體映射的每個面由三個頂點(diǎn)和三條邊進(jìn)行初始化，這些頂點(diǎn)和邊定義了一個正三角形。在創(chuàng)建正四面體映射時，這些頂點(diǎn)、邊或者邊的一部分都可能成為投影的真實(shí)圖元，同時還需要引入非真實(shí)圖元，它不僅可以加快遍歷，而且對于計算兩個平面劃分的疊置也是必要的。3.4.2 空間坐標(biāo)轉(zhuǎn)換關(guān)系為了有效的計算凸多面體Minkowski和的精確值，首先必須對三維空間中的每個點(diǎn)定義精確的坐標(biāo)值，同時還需要恰當(dāng)?shù)倪x取坐標(biāo)系。下面給出本文選取的坐標(biāo)系，如圖4-1，空間坐標(biāo)系的原點(diǎn)O為底面三角形的中心，x軸平行于，正方向?yàn)橄蛄康姆较?，y軸正方向?yàn)閤軸逆時針旋轉(zhuǎn)90度方向，z軸正方向?yàn)橄蛄康姆较?。其中，O為正四面體的中心。p3xyOp1p0p2zO圖4-1 坐標(biāo)系的選取Fig. 4-1 Choosing of Coordinate System給定了坐標(biāo)系的選取，可以得到凸多面體映射到正四面體表面的坐標(biāo)轉(zhuǎn)換關(guān)系式。設(shè)A為凸多面體上任意的一點(diǎn)，坐標(biāo)為(x,y,z)。則映射關(guān)系式分為以下幾種情況。若射線OA與底面相交，通過正四面體映射在面上的新坐標(biāo)為，則兩個坐標(biāo)之間的映射關(guān)系為式(4-1)，其中。 (4-1)若射線OA與側(cè)面相交，通過正四面體映射在面上的新坐標(biāo)為，則兩個坐標(biāo)之間的映射關(guān)系為式(4-2)。 (4-2)若射線OA與側(cè)面相交，通過正四面體映射在面上的新坐標(biāo)為，則兩個坐標(biāo)之間的映射關(guān)系為式(4-3)。 (4-3)若射線OA與側(cè)面相交，通過正四面體映射在面上的新坐標(biāo)為，則兩個坐標(biāo)之間的映射關(guān)系為式(4-4)。 (4-4)對于任意兩個點(diǎn)和，如果，三個條件中至少有一個成立，則映射后；同時，對于映射后的任意點(diǎn)都對應(yīng)著唯一的，因此該映射是可逆的。3.4.3 數(shù)據(jù)結(jié)構(gòu)及相關(guān)信息凸多面體的正四面體映射前后需記錄一些信息，第一次記錄映射前凸多面體的頂點(diǎn)和頂點(diǎn)之間的關(guān)聯(lián)關(guān)系，以及多面體的棱，用于映射后劃分平面；第二次是記錄正四面體表面的劃分，用于3.5節(jié)中投影后劃分平面。對于第一次記錄，采用數(shù)據(jù)結(jié)構(gòu)中的鄰接表來記錄頂點(diǎn)的坐標(biāo)值及與該頂點(diǎn)相關(guān)的邊。對凸多面體中的每個頂點(diǎn)建立一個單鏈表（n個頂點(diǎn)建立n個單鏈表），第個單鏈表中的結(jié)點(diǎn)表示與頂點(diǎn)的所有鄰接頂點(diǎn)，因此也稱為鄰接表，即中每個表結(jié)點(diǎn)均有兩個域，存放與相鄰接的頂點(diǎn)的序號的鄰接點(diǎn)域adjvex和將鄰接表的所有表結(jié)點(diǎn)鏈在一起的鏈域next。例如：頂點(diǎn)vi鄰接表的頭結(jié)點(diǎn)包含兩個域：存放頂點(diǎn)vi的信息(坐標(biāo)值)的頂點(diǎn)域vertex和vi的鄰接表的頭指針即指針域firstedge。對于第二次記錄，采用DCEL數(shù)據(jù)結(jié)構(gòu)表示平面劃分中頂點(diǎn)、半邊和面(指平面劃分面)之間的關(guān)聯(lián)關(guān)系，特定地設(shè)置頂點(diǎn)記錄、半邊記錄和面記錄。設(shè)置情況如下，其中頂點(diǎn)記錄為：頂點(diǎn)的坐標(biāo)，以該頂點(diǎn)為起點(diǎn)的任意一條關(guān)聯(lián)半邊；半邊記錄為：半邊的終點(diǎn)，半邊的孿生半邊，半邊的后繼半邊，半邊的相關(guān)面，在半邊的相關(guān)面中存儲著與它相關(guān)聯(lián)的平面劃分面，若關(guān)聯(lián)面為三角形以外的區(qū)域，則記為Null；面記錄為：與該面相關(guān)聯(lián)的任意一條半邊。在這些記錄中不僅存有幾何的、拓?fù)涞男畔?，而且還存儲著一些輔助信息。對于整個求和過程，這些信息是十分必要的。其中，頂點(diǎn)的輔助信息為：(1)該頂點(diǎn)是否為真實(shí)圖元(即是否存在凸多面體上的點(diǎn)映射到正四面體的頂點(diǎn))；(2)該頂點(diǎn)是否處在正四面體的頂點(diǎn)位置、棱上或者三角形面內(nèi)；半邊的輔助信息為：該半邊是否為真實(shí)圖元(即是否存在凸多面體的棱映射為該半邊)。通過本節(jié)給出的坐標(biāo)之間的映射關(guān)系，可以把凸多面體上的頂點(diǎn)坐標(biāo)轉(zhuǎn)換為相應(yīng)的正四面體表面上的坐標(biāo)，并記錄相應(yīng)的信息。為了便于平面劃分疊置的計算，需要把三維空間問題轉(zhuǎn)換到二維平面下解決，下面將給出正四面體側(cè)面劃分節(jié)點(diǎn)投影到面P的方法。3.5 點(diǎn)投影下面首先給出點(diǎn)投影的定義，然后根據(jù)投影規(guī)則把正四面體表面上的劃分點(diǎn)投影到平面P，并給出了具體的點(diǎn)投影關(guān)系式。3.5.1 點(diǎn)投影的定義定義4.6：點(diǎn)投影 將正四面體表面(包括棱)上的任意劃分點(diǎn)投影到指定區(qū)域，稱為點(diǎn)投影。如圖4-2。p1p3xyOp1p0p2zOp2p0nkm圖4-2 正四面體的側(cè)面劃分節(jié)點(diǎn)投影到平面PFig. 4-2 The no