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