空間數(shù)據(jù)組織算法(編輯修改稿)
2025-03-02 11:13 本頁面
【文章內(nèi)容簡介】 ? 塊式編碼是將游程長度編碼擴大到二維的情況，把多邊形范圍劃分成由像元組成的正方形，然后對各個正方形進行編碼。 ? 塊式 編碼的數(shù)據(jù)結(jié)構(gòu)由初始位置（行號，列號 )和半徑，再加上記錄單元的代碼組成。 ? 根據(jù)這一編碼原則，圖 形只需 17個單位正方形， 9個 4單位的正方形和 1個 16單位的正方形就能完整表示，總共要 57個數(shù)據(jù)，其中 27對坐標， 3個塊的半徑。 34 ? 塊式編碼的特點：一個多邊形所能包含的正方形越大，多邊形的邊界越簡單，塊式編碼的效果越好。 ? 游程和塊式編碼都對大的復雜多邊形效果并不好。塊式編碼在合并、插入、檢查延伸性、計算面積等操作時有明顯的優(yōu)越性。 35 ? 差分映射法， 就是選擇某一參照值對有關(guān)柵格的屬性值進行求差運算，根據(jù)差值得到一個新的柵格數(shù)據(jù)層。 ? 參照值的選擇有多種方式，即分行選取和全區(qū)選取。若分行選取，則可選為該行首列的屬性值，也可以選為該行的屬性平均值；若全區(qū)選取，則可選為首行首列的屬性值，也可以選為全區(qū)的屬性平均值。 36 ? 圖 。圖 ，以行首屬性值為參照，對圖 ?？梢钥闯?，經(jīng)差分映射處理后，除第一列外，其余柵格的數(shù)據(jù)出現(xiàn)為零、位數(shù)降低或數(shù)字減少。 37 ? 表 的對比，可見，所需字節(jié)數(shù)由原來的 79減少為 44，減少 %。 38 四叉樹編碼 ? 四叉樹又稱四元樹或四分樹，是 最有效 的柵格數(shù)據(jù)壓縮編碼方法 之一 。四分樹將整個圖像區(qū)域逐步分解為一系列方形區(qū)域，且每一個方形區(qū)域具有單一的屬性。最小區(qū)域為一個像元。 39 3 拓撲關(guān)系的生成 ? 拓撲空間關(guān)系是一種對空間結(jié)構(gòu)進行明確定義的數(shù)學方法，具有拓撲關(guān)系的矢量數(shù)據(jù)結(jié)構(gòu)就是拓撲數(shù)據(jù)結(jié)構(gòu)。 ? 它描述了基本空間目標點、線、面之間的關(guān)聯(lián)、鄰接和包含關(guān)系。 ? 矢量數(shù)據(jù)拓撲關(guān)系在空間數(shù)據(jù)的查詢和分析過程中非常重要，拓撲數(shù)據(jù)結(jié)構(gòu)是地理信息系統(tǒng)分析和應用功能所必需的。 ? 拓撲空間關(guān)系信息是空間分析、輔助決策等的基礎(chǔ)，也是GIS區(qū)別于 CAD(計算機輔助設(shè)計 )等的主要標志。 對于拓撲關(guān)系的自動建立問題，研究的 焦點 是 如何提高算法與過程的效率和自動化程度，本節(jié)將講述其實現(xiàn)的基本步驟和要點。 40 3 拓撲關(guān)系的生成 ? 拓撲關(guān)系自動生成算法的一般過程為： （ 1） 弧段處理： 使整幅圖形中的所有弧段，除在端點處相交外，沒有其他交點，即沒有相交或自相交的弧段。 （ 2） 結(jié)點匹配： 建立結(jié)點、弧段關(guān)系。 （ 3） 建立多邊形： 以左轉(zhuǎn)算法或右轉(zhuǎn)算法跟蹤，生成多邊形，建立多邊形與弧段的拓撲關(guān)系。 （ 4） 建立多邊形與多邊形的拓撲關(guān)系： 調(diào)整弧段的左右多邊形標識號。多邊 形內(nèi)部標識號的自動生成。 41 3 拓撲關(guān)系的生成 ? 基本數(shù)據(jù)結(jié)構(gòu) ? 弧段的預處理 ? 結(jié)點匹配算法 ? 建立拓撲關(guān)系 42 基本數(shù)據(jù)結(jié)構(gòu) ? （ 1）拓撲結(jié)點 ? （ 2）拓撲弧段及其表示 ? （ 3）拓撲面及其表示 ? （ 4）拓撲結(jié)點、弧段和面之間的關(guān)系 43 基本數(shù)據(jù)結(jié)構(gòu) ? （ 1）拓撲結(jié)點 ? 結(jié)點用來描述如管線的交點、道路路口等現(xiàn)實世界的特征對象，結(jié)點可以用來檢測弧段與弧段的連接關(guān)系和多邊形特征是否能正確地完成。只與一條弧段相連接的起點或終點叫做懸掛結(jié)點 ，如圖 P點就是懸掛結(jié)點。 ? 結(jié)點一般包括結(jié)點號、結(jié)點坐標、與該結(jié)點連接的弧段集合。 44 基本數(shù)據(jù)結(jié)構(gòu) ? 結(jié)點的數(shù)據(jù)結(jié)構(gòu)可以表示為： 45 基本數(shù)據(jù)結(jié)構(gòu) ?（ 2）拓撲弧段及其表示 拓撲弧段指處于兩個結(jié)點之間的點序列串 ，可以給弧段定義一個方向，或者定義為數(shù)字化弧段時從一個結(jié)點到另一個結(jié)點的采點方向，或者硬性定義一個方向。 定義方向后弧段開始的結(jié)點就稱為 起始結(jié)點 ，弧段結(jié)束的結(jié)點就稱為 結(jié)束結(jié)點 ，由起始結(jié)點到終止結(jié)點的方向稱為“ 起終方向 ” ，由終止結(jié)點到起始結(jié)點的方向稱為 “ 終起方向 ” 。弧段 起終方向左側(cè)的多邊形稱為弧段的左多邊形 ，弧段起終方向右側(cè)的多邊形稱為弧段的右多邊形 。 46 基本數(shù)據(jù)結(jié)構(gòu) ? 如果弧段的起始結(jié)點或終止結(jié)點只與一條弧段相關(guān)聯(lián)，則該弧段稱為 懸掛弧段 ，如圖 L為懸掛弧。一般可以通過標識懸掛弧段來檢測原始矢量數(shù)據(jù)的質(zhì)量。 弧段一般包括弧段號、弧段節(jié)點坐標串、弧段起始和終止結(jié)點、弧段左右多邊形。 47 基本數(shù)據(jù)結(jié)構(gòu) 48 基本數(shù)據(jù)結(jié)構(gòu) ? （ 3）拓撲面及其表示 ? 拓撲面是由一條或若干條弧段首尾相連接而成的邊線所包含的區(qū)域 ，內(nèi)部包含有其他拓撲面的拓撲面一般稱為 復雜面 ，被包含的拓撲面稱為 島 ，沒有島的拓撲面稱為 簡單面 ，如圖。對于拓撲面也可以定義 正反方向 ，一般定義為：當沿拓撲面的邊界前進時，被弧段所包圍的面域始終處于弧段的右側(cè)時的方向就是正方向；反之，則是反方向。 49 基本數(shù)據(jù)結(jié)構(gòu) ? 如圖 ，箭頭所指向的方向就是正方向，可以看出對于拓撲面的外邊界，順時針方向是正方向，而對于內(nèi)邊界逆時針方向就是正方向。 50 基本數(shù)據(jù)結(jié)構(gòu) ? 多邊形一般包括 多邊形號、中心點坐標、多邊形屬性數(shù)據(jù)、多邊形的組成弧段號、多邊形島 的信息?？紤]到組成弧段的方向和多邊形頂點序列的方向存在可能的不一致性以及效率問題，可以改為記錄組成多邊形的弧段指針和方向性信息，即弧段方向與多邊形的方向是否一致。 ? 對于島的信息則通過將構(gòu)成多邊形的邊線分塊來處理的方式體現(xiàn)，比如多邊形包含島嶼，則可以使多邊形的外邊界成為多邊形的第一部分，島嶼作為多邊形的第二、三、四等部分的方式加以解決。 51 52 基本數(shù)據(jù)結(jié)構(gòu) (4)拓撲結(jié)點、弧段和面之間的關(guān)系 53 ? 拓撲關(guān)系自動建立的第一步就是處理弧段，使得弧段不存在自相交和相交現(xiàn)象。 ? （ 1）直線段相交的判斷方法 ? （ 2）自相交弧段處理 ? （ 3）弧段相交打斷處理 54 (1)直線段相交的判斷方法 ? 直線相交的判定方法有很多種，這里介紹較快的一種算法。 ? 設(shè)直線 L過點 P0（ x0， y0）和點 P1（ x1， y1），則直線 L的方程可以表示為： ? 將方程化為參數(shù)形式： y=y0+(y1y0)t, x=x0+(x1x0)t，其中 t∈[0,1] 。 ?
教學課件相關(guān)推薦
鄂ICP備17016276號-1