空間數(shù)據(jù)組織算法(參考版)
2025-02-14 11:13本頁面
【正文】 2023年 3月 2日星期四 7時(shí) 46分 55秒 19:46:552 March 2023 1一個(gè)人即使已登上頂峰，也仍要自強(qiáng)不息。 2023年 3月 2日星期四 下午 7時(shí) 46分 55秒 19:46: 1最具挑戰(zhàn)性的挑戰(zhàn)莫過于提升自我。勝人者有力，自勝者強(qiáng)。 :46:5519:46Mar232Mar23 1越是無能的人，越喜歡挑剔別人的錯(cuò)兒。 , March 2, 2023 閱讀一切好書如同和過去最杰出的人談話。 2023年 3月 2日星期四 7時(shí) 46分 55秒 19:46:552 March 2023 1空山新雨后，天氣晚來秋。 2023年 3月 2日星期四 下午 7時(shí) 46分 55秒 19:46: 1楚塞三湘接，荊門九派通。 19:46:5519:46:5519:46Thursday, March 2, 2023 1不知香積寺，數(shù)里入云峰。 19:46:5519:46:5519:463/2/2023 7:46:55 PM 1成功就是日復(fù)一日那一點(diǎn)點(diǎn)小小努力的積累。 下午 7時(shí) 46分 55秒 下午 7時(shí) 46分 19:46: 沒有失敗，只有暫時(shí)停止成功！。 2023年 3月 下午 7時(shí) 46分 :46March 2, 2023 1行動(dòng)出成果，工作出財(cái)富。 :46:5519:46:55March 2, 2023 1他鄉(xiāng)生白發(fā)，舊國見青山。 :46:5519:46Mar232Mar23 1故人江海別，幾度隔山川。 , March 2, 2023 雨中黃葉樹，燈下白頭人。 （ 3）依次取負(fù)多邊形上的點(diǎn)，判斷點(diǎn)是否在正多邊形中，如果所有點(diǎn)都在正多邊形中則負(fù)多邊形被正多邊形所包含，否則，負(fù)多邊形不被正多邊形所包含。 76 （ 3）島的判斷 ? 上述算法中，判斷負(fù)多邊形是否被正多邊形包含是關(guān)鍵，具體的算法為： （ 1）判斷負(fù)多邊形面積的絕對(duì)值是否小于正多邊形的面積，如果不小于，則負(fù)多邊形必不為正多邊形所包含，結(jié)束程序；否則執(zhí)行下一步。 75 （ 3）島的判斷 （ 4）依次從負(fù)多邊形集合中取出負(fù)多邊形，判斷當(dāng)前取出的正多邊形是否包含該負(fù)多邊形，如果包含，就將該負(fù)多邊形加入當(dāng)前取出的正多邊形中，形成復(fù)雜多邊形，設(shè)置負(fù)多邊形的組成弧段的拓?fù)湫畔?，并從?fù)多邊形集合中刪除該負(fù)多邊形。 （ 3）如果負(fù)多邊形集合的個(gè)數(shù)為 1，結(jié)束程序 。 74 （ 3）島的判斷 島的判斷問題的算法如下： （ 1）計(jì)算所有多邊形的面積。任意多邊形的面積可以通過積分來解決，設(shè)多邊形的節(jié)點(diǎn)坐標(biāo)串為（ x1，y1），（ x2， y2）， … ，（ xn， yn)，那么多邊形的面積可以表示為 式中，△ x=xi+1xi。 ? 根據(jù)左轉(zhuǎn)算法，由單條弧段或多條弧段順序構(gòu)成的且不與其他多邊形相交的多邊形即單多邊形會(huì)被追蹤兩次，形成兩個(gè)多邊形，一個(gè)多邊形節(jié)點(diǎn)方向是順時(shí)針的，另一個(gè)多邊形的節(jié)點(diǎn)方向是逆時(shí)針的，如果一個(gè)多邊形包含另一個(gè)多邊形，則必然是順時(shí)針多邊形包含逆時(shí)針多邊形。 72 （ 3）島的判斷 ? 島的判斷是指找出多邊形互相包含的情況，即尋找復(fù)雜多邊形。從 N2結(jié)點(diǎn)開始，具有最小方位角的弧段是 N2N1，但 N2N1已經(jīng)被使用兩次，不選； 繼續(xù)選取下一條弧段 N2N5；然而上一次該弧段的訪問方向與本次相同，所以也不選；繼續(xù)選取下一條弧段 N2N3作為起始弧段，形成多邊形 A4。 70 （ 2）左轉(zhuǎn)算法 （ 3） A2的結(jié)束弧段為 N4N1， 選 N1作為起始點(diǎn) ， N1N4作為起始弧段 ， 根據(jù) 、 左轉(zhuǎn)算法 ， 形成多邊形 A3， 這個(gè)多邊形的方向是逆時(shí)針方向 ， 對(duì)于逆時(shí)針方向的多邊形 ， 不設(shè)置左右多邊形信息 。 69 （ 2）左轉(zhuǎn)算法 （ 1）從 N1結(jié)點(diǎn)開始，選擇具有最小方位角的弧段 N1N2作為起始弧段；轉(zhuǎn)入 N2點(diǎn)，根據(jù)左轉(zhuǎn)算法選擇 N2N5弧段，轉(zhuǎn)入 N5結(jié)點(diǎn)選擇 N5N1弧段，形成多邊形 A1，設(shè)置組成多邊形 A1的弧段的左右多邊形信息。 （ 4）取起始點(diǎn)上開始的，剛才所形成多邊形的最后一條邊作為新的起始弧段， 轉(zhuǎn) (2)；若這條弧段已經(jīng)使用過兩次，即形成了兩個(gè)多邊形，轉(zhuǎn) (1)。 （ 2）取這條弧段的另一個(gè)結(jié)點(diǎn)，找這個(gè)結(jié)點(diǎn)關(guān)聯(lián)的弧段集合中的本條弧段的下一條弧段，如果條弧段是最后一條弧段，則取弧段集合的第一條弧段，作為下一條弧段。 66 （ 2）左轉(zhuǎn)算法 ? 算法基本思想 ：從組成多邊形邊界的某一條弧段開始，如果該弧段的方向角最小或介于同一結(jié)點(diǎn)的其他弧段方向角之間，則 逆時(shí)針方向 尋找最小夾角偏差所對(duì)應(yīng)的弧段為多邊形的后續(xù)弧段；如果該弧段與 X軸正向夾角為最大，則從該弧段的同一結(jié)點(diǎn)出發(fā)的其他弧段中，方向角最小的弧段是該多邊形的后續(xù)弧段。 63 ? （１）計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角 ,并按由小到大排序 ? （２）左轉(zhuǎn)算法 ? （３）島的判斷 64 （１）計(jì)算結(jié)點(diǎn)關(guān)聯(lián)弧段的方位角 ? 每個(gè)結(jié)點(diǎn)都關(guān)聯(lián)有若干條弧段，結(jié)點(diǎn)或者為弧段的頭結(jié)點(diǎn)或者為弧段的尾結(jié)點(diǎn)，設(shè)結(jié)點(diǎn)為 N，則弧段的 方位角 定義為：結(jié)點(diǎn) N與弧段上與其最接近結(jié)點(diǎn) V的連線與 Ｘ 軸的正向夾角。 62 ? 每條弧段對(duì)應(yīng)著兩個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)在合并前對(duì)應(yīng)著一條弧段，在合并結(jié)點(diǎn)的過程中，需要將結(jié)點(diǎn)對(duì)應(yīng)的弧段也合并在一起。 ? 減少計(jì)算量方法 ：分兩步，首先是判斷兩條弧段的最小矩形壁包 (MBR)是否相交或具有包含關(guān)系，如果不相交或沒有包含關(guān)系，那么可以斷定兩條弧段是互不相交的；如果相交或具有包含關(guān)系，則進(jìn)一步判斷第一條弧段的每一條組成線段是否和第二條弧段的 MBR相交或被包含，如果不相交或沒有被包含則可以判斷這一部分線段不會(huì)和第二條弧段相交，否則可以使用這一條線段與組成第二條弧段的各個(gè)線段進(jìn)行相交關(guān)系的判定來確定交點(diǎn)。將第一條弧段與所有其他弧段的相交關(guān)系判斷完畢后，通過記錄下的交點(diǎn)位置將第一條弧段分割，然后依次取出下一條弧段進(jìn)行同樣的處理，直到所有弧段處理完畢 。 57 58 59 （ 3）弧段相交打斷處理 ? 弧段與弧段相交關(guān)系的判斷，可以通過取每一條弧段與其他未判斷過的所有弧段目標(biāo)進(jìn)行相交關(guān)系判斷而得，從而要進(jìn)行 （ n 1) + ( n 2) +…+ 3 + 2 + 1 = n （ n – 1） /2次判斷。 56 （ 2）自相交弧段處理 ? 具有自相交特征的弧段至少具有 4個(gè) (結(jié) )節(jié)點(diǎn)，由 3個(gè)點(diǎn)或 2個(gè)點(diǎn)組成的弧段不可能自相交。令： 如果 dx ? dy39。 ? 設(shè)直線
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1