梯形圖算法的實(shí)現(xiàn)

1、梯形圖算法的實(shí)現(xiàn)計(jì)算幾何實(shí)驗(yàn)報(bào)告 許振華 李靈坡選題背景平面排列問(wèn)題是計(jì)算機(jī)很重要的組成部分，并且有著廣泛的應(yīng)用背景，如GPS等。其基本思想是利用平面上已知的一定數(shù)目的曲線排列，將平面劃分為一些相互連接的單元，并滿足一點(diǎn)的目的。這些單元可以包括點(diǎn)、曲線和面。利用這些單元就可以實(shí)現(xiàn)平面映射從而實(shí)現(xiàn)相關(guān)的應(yīng)用。點(diǎn)定位問(wèn)題是平面排排列問(wèn)題中比較重要而且比較基礎(chǔ)的內(nèi)容，它可以描述為：給定一定數(shù)目的曲線，通過(guò)一定的處理構(gòu)建一個(gè)數(shù)據(jù)結(jié)構(gòu)，這樣對(duì)于給定的任何一點(diǎn)可以有效地找到和這個(gè)點(diǎn)對(duì)應(yīng)的單元。實(shí)現(xiàn)這個(gè)目的有一種很簡(jiǎn)單的算法就是遍歷所有的邊和定點(diǎn)，然后找到和要查詢的點(diǎn)對(duì)應(yīng)的單元。這種算法不需要任何其他的空間

2、存儲(chǔ)，簡(jiǎn)單方便，但是這種算法的復(fù)雜度為O(n)，對(duì)于大規(guī)模問(wèn)題來(lái)說(shuō)，查詢速度非常慢，而對(duì)于普通的查詢來(lái)說(shuō)，往往有O(logn)的性能，算法還有很多提升的空間。一種更有效的做法就是將搜索區(qū)域按照空間分成垂直的條帶狀，并對(duì)于每個(gè)帶內(nèi)部的進(jìn)行查找，這樣在X和Y方向上同時(shí)進(jìn)行二分查找，可以在O(logn)的時(shí)間內(nèi)實(shí)現(xiàn)點(diǎn)的查詢，只是這種算法需要的空間復(fù)雜度為O(n2)。對(duì)于這種方法，Snarnack和Tarjan使用優(yōu)先查找樹(shù)的結(jié)構(gòu)將算法的空間復(fù)雜度降低了許多。本文介紹的算法室友Mulmuley和Seidel基于隨機(jī)插入構(gòu)建(randomized incremental construction)思想而

3、提出的，算法將搜索結(jié)構(gòu)分解成一些豎直的梯形，并構(gòu)建一個(gè)有向循環(huán)圖作為查找結(jié)構(gòu)，其空間復(fù)雜度為O(n)，查詢的時(shí)間復(fù)雜度的期望值為O(logn)，在這里我們稱之為梯形圖算法。算法描述本次實(shí)驗(yàn)中的算法針對(duì)沒(méi)有重合的線段排列中的點(diǎn)定位問(wèn)題進(jìn)行。依據(jù)線段的分布，將空間分成一些點(diǎn)、線段和梯形的集合，并構(gòu)建與之對(duì)應(yīng)的查找結(jié)構(gòu)。在本算法中每個(gè)梯形的圖片 1：梯形結(jié)構(gòu)圖片 2：平面劃分結(jié)構(gòu)如圖1所示：有兩條線段（或者是搜索區(qū)域的邊界）構(gòu)成了梯形的上下邊，兩個(gè)定點(diǎn)所在的豎直線段構(gòu)成了梯形另外兩邊。整體的表面劃分和搜索結(jié)構(gòu)如圖2和圖3所示。具體的算法描述可以參見(jiàn)作者論文 R. Seidel. A simple a

4、nd fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl., 1(1):5164, 1991.。圖片 3：搜索結(jié)構(gòu)算法實(shí)現(xiàn)本次試驗(yàn)中我們?cè)赩C6.0框架下采用MFC對(duì)于梯形圖算法進(jìn)行實(shí)現(xiàn)和仿真。其中，對(duì)于平面圖的劃分采用DCEL的方式進(jìn)行存儲(chǔ)，并輔助以一個(gè)有向循環(huán)圖進(jìn)行查找，算法主要包括6中數(shù)據(jù)結(jié)構(gòu)：Point，Hsegment，F(xiàn)ace，Dpoint，Segment和Tra

5、pezoid。其中前三種結(jié)構(gòu)的內(nèi)容和功能和DCEL結(jié)構(gòu)相同，Dpoint用于存儲(chǔ)查找結(jié)構(gòu)的每一個(gè)節(jié)點(diǎn)，可能包括三種類型：點(diǎn)、線段和梯形。Segment和Trapezoid是輔助結(jié)構(gòu)，用來(lái)存儲(chǔ)對(duì)應(yīng)的邊界點(diǎn)。在查找結(jié)構(gòu)中，每個(gè)點(diǎn)類型查詢點(diǎn)包含一個(gè)指向Point的指針，每個(gè)線段類型查詢點(diǎn)包含一個(gè)指向Segment的指針，梯形類型的查詢點(diǎn)Trapezoid結(jié)構(gòu)的指針，這三種指針以聯(lián)合的形式存放于Dpoint結(jié)構(gòu)內(nèi)，共用一塊內(nèi)存，具體參見(jiàn)附帶源碼。算法采用逐步插入更新的方法實(shí)現(xiàn)。每一條線段插入后都會(huì)生成一個(gè)完整的平面劃分圖和查找結(jié)構(gòu)。每次插入新的線段時(shí)，平面劃分和相應(yīng)的數(shù)據(jù)結(jié)構(gòu)都要進(jìn)行更新。依據(jù)新插入線

6、段和需要更新的梯形之間的關(guān)系具體包括一下三種情況：線段在梯形內(nèi)、線段從一邊穿過(guò)梯形、線段貫穿梯形，分別采用不同的函數(shù)進(jìn)行處理，具體操作參加鄧?yán)蠋熣n件06.pl.e.TrapMap，12-14, 2008。在每一步的實(shí)現(xiàn)過(guò)程中，要使用已經(jīng)生成的查找表尋找和點(diǎn)對(duì)應(yīng)的梯形，這樣每一步的執(zhí)行都要利用上一步生產(chǎn)的查找結(jié)構(gòu)。本算法實(shí)現(xiàn)過(guò)程沒(méi)有利用任何現(xiàn)成代碼，所有代碼完全由自己編寫完成。技術(shù)難點(diǎn)和解決在本次算法實(shí)現(xiàn)過(guò)程中，主要的困難存在于幾個(gè)方面，對(duì)應(yīng)的問(wèn)題描述和以及解決方法如下。1. DCEL結(jié)構(gòu)的使用由于DCEL結(jié)構(gòu)已經(jīng)有很多現(xiàn)成的代碼，特別是在CGAL算法庫(kù)中。在實(shí)驗(yàn)初期試圖使用現(xiàn)成的DCEL結(jié)構(gòu)進(jìn)

7、行處理，但是由于在實(shí)驗(yàn)中，需要使用的功能相對(duì)比較特殊也比較簡(jiǎn)單，這里重新實(shí)現(xiàn)了DCEL結(jié)構(gòu)，并按照自己算法的要求設(shè)計(jì)了一些特殊的操作函數(shù)。由于DCEL是雙向連接的機(jī)制并且包括三種的結(jié)構(gòu)，在進(jìn)行函數(shù)設(shè)計(jì)的時(shí)候必須同時(shí)考慮和當(dāng)前操作部位相關(guān)的所有數(shù)據(jù)結(jié)構(gòu)的變化情況。在本實(shí)驗(yàn)中進(jìn)行函數(shù)設(shè)計(jì)的時(shí)候，本著每次都盡可能的保證所有結(jié)構(gòu)中的數(shù)據(jù)盡可能完整的原則，對(duì)于每一步的更新都更新所有相關(guān)的結(jié)構(gòu)，實(shí)現(xiàn)了函數(shù)功能的魯棒性。2. 退化情況的處理這里的退化情況主要包括兩種，一種是插入的線段為豎直線，另一種為插入的線段的端點(diǎn)和兩外線段的端點(diǎn)在共同的豎直線上。對(duì)于第一種情況，我們采用的方法是只講其中的第一個(gè)定點(diǎn)作為查

8、找結(jié)構(gòu)的組成部分，第二個(gè)點(diǎn)作為輔助點(diǎn)用于判斷查詢點(diǎn)是不是在對(duì)應(yīng)的線段上。對(duì)于第二種情況，如果插入線段的定點(diǎn)在對(duì)應(yīng)梯形的豎直邊上（和其它定點(diǎn)在同一豎直線上），就簡(jiǎn)單的將此定點(diǎn)插入到對(duì)應(yīng)的邊上，而不生成新的梯形。這種情況下，對(duì)應(yīng)的定點(diǎn)則不會(huì)出現(xiàn)在查找結(jié)構(gòu)里面，而相應(yīng)的線段則照常顯示。在算法的實(shí)現(xiàn)過(guò)程中，我們將這種特殊情況和標(biāo)準(zhǔn)的情況一起考慮，盡量減少代碼的重復(fù)性當(dāng)這兩種情況同時(shí)出現(xiàn)的時(shí)候，也就是豎直線段同時(shí)在垂直方向上的時(shí)候，則對(duì)應(yīng)的線段對(duì)于平面圖的劃分不產(chǎn)生影響，則無(wú)論是線段還是對(duì)應(yīng)的端點(diǎn)都不會(huì)出現(xiàn)在查找結(jié)構(gòu)中。只是在對(duì)應(yīng)的DCEL結(jié)構(gòu)中加入相應(yīng)的點(diǎn)。3. 樹(shù)結(jié)構(gòu)的顯示由于查找結(jié)構(gòu)比較復(fù)雜，對(duì)于

9、幾條線段的查找結(jié)構(gòu)往往就會(huì)生成比較長(zhǎng)的查找結(jié)構(gòu)，而且對(duì)于線段分布比較復(fù)雜的情況，同一個(gè)梯形可能會(huì)有很多個(gè)不同的上層地點(diǎn)，這樣給查找結(jié)構(gòu)的顯示帶來(lái)和很大的困難。這里我統(tǒng)計(jì)查找結(jié)構(gòu)的層數(shù)和每一層節(jié)點(diǎn)數(shù)的方法，計(jì)算對(duì)應(yīng)的查找結(jié)構(gòu)顯示窗口的大小，從而實(shí)現(xiàn)對(duì)應(yīng)的查找結(jié)構(gòu)。為了避免大量的重復(fù)節(jié)點(diǎn)造成的連接線比較混亂的情況，我們使用樹(shù)的結(jié)構(gòu)顯示對(duì)應(yīng)的DAG，其中相同編號(hào)的編號(hào)對(duì)應(yīng)相同的查找結(jié)構(gòu)。4. 數(shù)據(jù)結(jié)構(gòu)的析構(gòu)由于DCEL是多向的，基本上是以半邊為主線，對(duì)應(yīng)的定點(diǎn)和面幾乎是掛在半邊上的，面和定點(diǎn)之間是一對(duì)多的關(guān)系，這樣容易出現(xiàn)重復(fù)刪除。由于我們使用C+語(yǔ)言實(shí)現(xiàn)，語(yǔ)言本身無(wú)法判斷對(duì)應(yīng)的內(nèi)存空間是不是已經(jīng)被

10、析構(gòu)，所以很容易因?yàn)閷?duì)同一個(gè)位置重復(fù)刪除而出錯(cuò)。在這里為了避免這種情況，我們采用類似堆棧的形式，每次刪除都把和當(dāng)前頂點(diǎn)對(duì)應(yīng)向連接的新頂點(diǎn)放入到當(dāng)前堆棧中。每次都從末尾取一個(gè)頂點(diǎn)進(jìn)行刪除。同樣，對(duì)于DAG結(jié)構(gòu)的刪除也存在對(duì)應(yīng)的問(wèn)題，為了避免重復(fù)刪除，這里采用廣度優(yōu)先的遍歷并以一個(gè)隊(duì)列作為輔助結(jié)構(gòu)進(jìn)行對(duì)應(yīng)空間的析構(gòu)。5. MFC對(duì)MFC界面編程不熟悉是本次實(shí)現(xiàn)過(guò)程中最大的難題。MFC中各種窗口類名目繁多，WINDOWS各種API也讓人眼花繚亂。只能在巨大的信息量中慢慢挑選自己需要的。因此花了很多時(shí)間。本次實(shí)現(xiàn)過(guò)程中主要用到了對(duì)話框類和CSCROLLVIEW類。整個(gè)應(yīng)用程序是基于SDI的框架搭建的。

11、a) 對(duì)話框類重點(diǎn)用對(duì)話框類實(shí)現(xiàn)了界面右側(cè)的控制面板。該對(duì)話框的父窗口是一個(gè)view，當(dāng)view的OnDraw函數(shù)被調(diào)用時(shí)，該對(duì)話框也會(huì)隨著view的大小和位置調(diào)整自己的屬性。但是該對(duì)話框始終保持在該view的右側(cè)。在這個(gè)過(guò)程中，主要用到的函數(shù)首先是CWnd: :SetWindowPos()，用于最終擺放對(duì)話框的位置；其次是CWnd: :GetWindowRect()用于得到view的窗口的位置；以及CDC: :LPtoDP()用于將邏輯坐標(biāo)轉(zhuǎn)化成設(shè)備坐標(biāo)。b) CScrollView類嵌入對(duì)話框中在顯示梯形圖的樹(shù)形結(jié)構(gòu)時(shí)，原本打算采用的是彈出式的對(duì)話框。后來(lái)發(fā)現(xiàn)梯形圖的樹(shù)形結(jié)構(gòu)非常龐大，小對(duì)

12、話框根本容納不下。于是采用在對(duì)話框里嵌入一個(gè)CScrollView的方法來(lái)顯示樹(shù)形結(jié)構(gòu)。但是CScrollView并不能直接嵌入對(duì)話框中，因?yàn)槌跏蓟痸iew的過(guò)程中，需要一個(gè)frame做它的父窗口，因此必須先嵌入一個(gè)CWndFrame，然后再嵌入CScrollView。否則在顯示窗口時(shí)，會(huì)有一句斷言無(wú)法通過(guò)。另外，也嘗試了改變鼠標(biāo)的樣式，用WINAPI :SetCursor()在畫線段時(shí)將鼠標(biāo)設(shè)置成蠟筆，在刪除時(shí)設(shè)置成紅叉。6. OpenGL對(duì)OpenGL的使用不夠熟練也是本次作業(yè)中的一個(gè)難題。如果不能熟練使用OpenGL，很多情況下甚至畫出來(lái)的圖形比直接用CDC還要糟糕。本次實(shí)現(xiàn)過(guò)程中，主要

13、熟悉了OpenGL的 以下幾個(gè)方面c) 主要熟悉了OpenGL的投影模式和模型視角模式的矩陣的操作。因?yàn)楸敬巫鳂I(yè)只涉及到了平面上的物體，因此就用了最簡(jiǎn)單的正交投影模式，用的最多的函數(shù)是glortho()。在設(shè)置完投影矩陣之后，還需要設(shè)置合適的函數(shù)進(jìn)行OpenGL窗口坐標(biāo)和windows窗口坐標(biāo)的相互轉(zhuǎn)化。因?yàn)閣indows的窗口坐標(biāo)是向下為y正方向，左上角為原點(diǎn)，而OpenGL是向上為y正方向，左下角為原點(diǎn)。d) 另外使用了OpenGL的簡(jiǎn)單的畫點(diǎn)，線，多邊形的功能。多邊形的繪制有三種模式可以選擇，用glPolygonMode()如果傳入?yún)?shù)GL_FILL，則得到的是實(shí)心的完整的多邊形；如果傳

14、入?yún)?shù)GL_LINE，則繪制得到的是線框的多邊形；如果傳入?yún)?shù)GL_POINT則繪制得到的是只有頂點(diǎn)的多邊形。e) 最后，使用了OpenGL的抗鋸齒功能，美化了畫出的圖形。圖片 4：抗鋸齒前圖片 5：抗鋸齒后 實(shí)驗(yàn)測(cè)試由于數(shù)據(jù)線段比較多的時(shí)候查找結(jié)構(gòu)比較復(fù)雜，而且占用空間比較大，這里不太容易顯示，這里僅說(shuō)明簡(jiǎn)單線段的查找結(jié)構(gòu)(圖6、圖7)、豎直線比較多的情況下的劃分結(jié)構(gòu)(圖8)復(fù)雜情況的平面劃分(圖911).。圖片 6：平面劃分圖片 7：查找圖圖片 8：多種特殊情況的例子圖片 9：類切草結(jié)構(gòu)的平面劃分圖片 10：樓梯結(jié)構(gòu)圖像圖片 11：隨機(jī)雜亂線段的結(jié)構(gòu)要進(jìn)一步完善的工作由于時(shí)間和作者能力限制

15、，本實(shí)驗(yàn)還有一些問(wèn)題需要進(jìn)一步完善，主要包括以下幾個(gè)方面，這里理出問(wèn)題的特點(diǎn)和作者的擬解決方法：1. 算法的分步動(dòng)態(tài)演示本程序中算法的分步動(dòng)態(tài)演示是采用了最原始的方法，每一次更新線段之后所有的線段重新計(jì)算一次，從而能夠及時(shí)的更新圖形界面。這種實(shí)現(xiàn)方法，對(duì)于僅僅實(shí)現(xiàn)幾十條邊問(wèn)題能夠很快的實(shí)現(xiàn)，如果邊的數(shù)目過(guò)多，則每次重新計(jì)算則是對(duì)計(jì)算資源的嚴(yán)重浪費(fèi)，因此，因此需要更好的方法進(jìn)行處理，主要有幾種思路a) 每次存儲(chǔ)生成的數(shù)據(jù)結(jié)構(gòu)，對(duì)于單步查看的每一步，讀取相應(yīng)的文件并顯示。這種方法能夠快速的顯示算法的過(guò)程，但是對(duì)于大規(guī)模的問(wèn)題，顯然要造成大量的資源浪費(fèi)b) 每次存儲(chǔ)和和上一步有差別的結(jié)構(gòu)，在單步執(zhí)行

16、的時(shí)候讀取并更新：這種方法相對(duì)上一種方法在時(shí)間和空間上都有大量的結(jié)余，但是實(shí)現(xiàn)起來(lái)比較困難，特別是無(wú)論DCEL還是DAG都是有循環(huán)結(jié)構(gòu)的，在執(zhí)行的時(shí)候需要增加很多輔助函數(shù)。c) 動(dòng)態(tài)的刪除新生成的結(jié)構(gòu)。每次回退一步的時(shí)候，查找上一步生成的新結(jié)構(gòu)并將之刪除。這種算法不會(huì)造成多余的空間浪費(fèi)，但是查找每次新生成的空間結(jié)構(gòu)并將其復(fù)原的復(fù)雜度和梯形圖算法本身的復(fù)雜度差不多。需要進(jìn)步不的努力。從整體的對(duì)比來(lái)看，第二種方法會(huì)更有效，但是第三種思路顯得更為完美，可以放在以后進(jìn)行嘗試。2. 算法的效能分析由于梯形圖算法是期望意義下的O(logn)算法，算法的性能和線段插入的順序密切相關(guān)。不同參數(shù)順序的空間結(jié)構(gòu)都

17、一樣，但是查詢效率比較低。對(duì)于生成的線段，隨機(jī)生成查詢插入順尋并統(tǒng)計(jì)一定數(shù)目代表性節(jié)點(diǎn)的查詢效率，對(duì)于理解本算法有比較重要的意義。3. 查找樹(shù)的動(dòng)態(tài)顯示：由于是新手，對(duì)于MFC不熟悉，沒(méi)辦法很好的生成一個(gè)美觀的查找圖。由于查找圖的結(jié)構(gòu)并不是平衡二叉樹(shù)，最后生成的圖的層數(shù)和每一層的節(jié)點(diǎn)數(shù)都不固定，這樣對(duì)于查找結(jié)構(gòu)的長(zhǎng)寬設(shè)置影響很大。由于沒(méi)插入一層就跟新上一步節(jié)點(diǎn)的做法時(shí)間復(fù)雜度超過(guò)了O(n2)，本次實(shí)驗(yàn)沒(méi)有嘗試。如何更有效更美觀的顯示相應(yīng)的查找結(jié)構(gòu)，仍需要進(jìn)一步研究。在算法檢查之前，算法有五個(gè)方面的問(wèn)題，如下：1. 樹(shù)形結(jié)構(gòu)很雜亂，無(wú)法看清楚2. 圖形界面的顏色搭配不夠美觀，操作不夠人性化3.

18、在實(shí)現(xiàn)多個(gè)跨區(qū)域連接和空間釋放的過(guò)程中容易崩潰4. 不能合適的處理開(kāi)始是豎直線段的情況5. 沒(méi)有通過(guò)幾種特殊數(shù)據(jù)的測(cè)試在后來(lái)的實(shí)現(xiàn)過(guò)程中，我們找出了算法出現(xiàn)問(wèn)題的原因，并一一進(jìn)行了改進(jìn)，最終的結(jié)果如當(dāng)前算法所示。界面操作說(shuō)明圖片 12：實(shí)例圖像線段為紅色線條，梯形圖為綠色線條。1. 選擇菜單欄的“文件->導(dǎo)入數(shù)據(jù)”選項(xiàng)，可從txt文件導(dǎo)入線段數(shù)據(jù)，數(shù)據(jù)的格式如下segmentNUMsegment1Begin.x segment1Begin.y segment1End.x segment1End.ysegment2Begin.x segment2Begin.y segment2End.x segment2End.ysegment3Begin.x segment3Begin.y segment3End.x segment3End.y參見(jiàn)文件夾中2. 右側(cè)為主要的控制面板