GIS算法基礎(chǔ)重點(diǎn)

《GIS算法基礎(chǔ)重點(diǎn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、標(biāo)準(zhǔn)文檔一、算法的時(shí)間復(fù)雜性T(n)：利用某算法處理一個(gè)問(wèn)題規(guī)模為n的輸入所需要的時(shí)間。空間：為了解求問(wèn)題的實(shí)例而執(zhí)行的計(jì)算步驟所需要額內(nèi)存空間（或字）數(shù)目，不包括用來(lái)存儲(chǔ)輸入的空間。算法空間復(fù)雜性不可能超過(guò)運(yùn)行時(shí)間的復(fù)雜性。元運(yùn)算:對(duì)于任何計(jì)算步驟，不管輸入數(shù)據(jù)或執(zhí)行的算法，它的代價(jià)總是以一個(gè)時(shí)間常量為上界，則稱該計(jì)算步驟為元運(yùn)算?；诒容^的排序問(wèn)題的最優(yōu)算法：我們通常把在O(nlgn)時(shí)間內(nèi)用元素比較法排序的任何算法，稱為基于比較的排序問(wèn)題的最優(yōu)算法。一般來(lái)說(shuō)，如果可以證明任何一個(gè)求解問(wèn)題A的算法必定是Ω(f(n)),那么我們把在O(f(n))時(shí)間內(nèi)求解任

2、何問(wèn)題A的任何算法都稱為問(wèn)題A的最優(yōu)算法。算法設(shè)計(jì)原則:正確性確定性清晰性。算法的要素：1.待解問(wèn)題的描述2.算法設(shè)計(jì)的任務(wù)3.算法分析。二、關(guān)系運(yùn)算：指的是用于檢驗(yàn)兩個(gè)幾何對(duì)象的特定的拓?fù)淇臻g關(guān)系的邏輯方法。兩步確定兩條線段是否相交：1.快速排斥實(shí)驗(yàn)（矩形不相交）2.跨立實(shí)驗(yàn)（判斷線段P1P2是否和Q1Q2跨立依據(jù)是：(P1-Q1)*(Q2-Q1)*(Q2-Q1)*(P2-Q1)>=0.）判斷點(diǎn)是否在多邊形內(nèi)常用算法：1.射線法（又叫奇偶測(cè)試法）2.轉(zhuǎn)角法。線段在多邊形內(nèi)的一個(gè)重要條件是線段的兩個(gè)端點(diǎn)都在多邊形內(nèi)，第二個(gè)必要條件是線段和多邊形的所有邊都不內(nèi)交

3、。線段在多邊形內(nèi)判斷步驟實(shí)用文案標(biāo)準(zhǔn)文檔：1.先求出所有和線段相交的多邊形的頂點(diǎn)2.然后按照X-Y坐標(biāo)排序（X坐標(biāo)小的排在前面，對(duì)于X坐標(biāo)相同的點(diǎn)，Y坐標(biāo)小的排在前面，這種排序準(zhǔn)則也是為了保證水平和垂直情況的判斷正確），這樣相鄰的兩個(gè)點(diǎn)就是在線段上相鄰的兩交點(diǎn)，如果任意相鄰兩點(diǎn)的中點(diǎn)也在多邊形內(nèi)，則該線段一定在多邊形內(nèi)。計(jì)算線段或直線與線段的交點(diǎn)：設(shè)一條線段為L(zhǎng)0=P1P2，另一條線段或直線為L(zhǎng)1=Q1Q2，要計(jì)算的就是L0和L1的交點(diǎn)：第一步：首先判斷L0和L1是否相交2.若L1不平行與Y軸，則交點(diǎn)橫坐標(biāo)為P1的橫坐標(biāo)，代入到L1的直線方程中可以計(jì)算出交點(diǎn)縱

4、坐標(biāo)。第三步：若L1平行于y軸，則第四步：若L0平行于x軸，有2種情況，第五步：若L1平行于x軸，則，第六步：若L1和L0斜率均存在，則。中心點(diǎn)的計(jì)算：多邊形的中心點(diǎn)（又叫質(zhì)心或重心）可以通過(guò)將多邊形分割成為三角形，求取三角形的中心點(diǎn)，然后將三角形的中心點(diǎn)加權(quán)求和取得。三點(diǎn)畫圓：算法關(guān)鍵是求取圓心和園半徑：第一步：求取圓心，第二步：求取半徑R，R=（（xa-xp）^2+(ya-yp)^2）^1/2。p是圓心。四、矢量線柵格化三種方法：八方向柵格化、全路徑柵格化、恒密度柵格化。矢量面格式向柵格面格式轉(zhuǎn)換又稱為多邊形填充，就是在矢量表示的多邊形邊界內(nèi)部的所有柵格點(diǎn)

5、上賦以相應(yīng)的多邊形編碼，從而形成柵格數(shù)據(jù)陣列。方法有：內(nèi)部點(diǎn)擴(kuò)散算法（種子，八方向擴(kuò)散）、射線算法和掃描算法、邊界代數(shù)算法（積分、拓?fù)洌?。柵格?shù)據(jù)矢量化有4個(gè)基本步驟：1.邊界提取2.邊界線追蹤3.拓?fù)潢P(guān)系生成4.去除多余點(diǎn)及曲線圓滑。細(xì)化算法：實(shí)用文案標(biāo)準(zhǔn)文檔柵格數(shù)據(jù)需要細(xì)化，以提取其中軸線，因?yàn)椋?.中軸線是柵格數(shù)據(jù)曲線的標(biāo)準(zhǔn)化存儲(chǔ)形式2.實(shí)現(xiàn)細(xì)化是將柵格曲線矢量化的前提3.在有些算法中可以提高計(jì)算精度。細(xì)化算法可分兩大類：第一大類是基于距離變換，首先得到骨架像元，然后跟蹤距離變換圖中的“山脊線”，并將其作為中軸線；第二類是基于在不破壞柵格拓?fù)溥B通性的前提

6、下，按對(duì)稱的原則刪除影像邊緣的柵格點(diǎn)。四例：1.用距離變換法搜尋中軸線（減細(xì)）2.最大數(shù)值計(jì)算法（V值4、1）3.經(jīng)典的細(xì)化算法4.邊緣跟蹤剝皮法.多邊形柵格轉(zhuǎn)矢量的雙邊界搜索算法：基本思想：通過(guò)邊界提取，將左右多邊形信息保存在邊界點(diǎn)上，每條邊界弧段由兩個(gè)并行的邊界鏈組成，分別記錄該邊界弧段的左右多邊形編號(hào)。具體步驟：1.邊界點(diǎn)和結(jié)點(diǎn)提取2.邊界線搜索與左右多邊形信息記錄3.多余點(diǎn)去除。多邊形柵格轉(zhuǎn)矢量的單邊界搜索算法：?jiǎn)芜吔缢阉魉惴〞r(shí)通過(guò)對(duì)傳統(tǒng)的區(qū)域跟蹤算法進(jìn)行改進(jìn)而形成的，傳統(tǒng)區(qū)域跟蹤算法中，對(duì)區(qū)域的描述由兩部分組成：區(qū)域外輪廓和內(nèi)部孔洞。單邊界搜索算法流

7、程：1.跟蹤、搜索第一層所有的區(qū)域并記錄外輪廓和內(nèi)部孔洞信息2.根據(jù)跟蹤到的孔洞信息找出下一層中未跟蹤過(guò)的區(qū)域的外輪廓跟蹤起始點(diǎn)（即找出一個(gè)新區(qū)域）3.跟蹤找到的新區(qū)域并記錄其外輪廓和內(nèi)部孔洞信息4.重復(fù)23步，直到該層所有區(qū)域都已被跟蹤完畢5重復(fù)2到3步，直到整幅圖像內(nèi)所有區(qū)域都已被跟蹤完畢。五、道格拉斯-普克法優(yōu)點(diǎn)是具有最小的線性位移，壓縮效果占優(yōu)，缺點(diǎn)是需對(duì)整條曲線完成數(shù)字化后方能進(jìn)行壓縮，且計(jì)算工作量較大。光欄法原理：它按照預(yù)先定義的一個(gè)扇形（“喇叭口”實(shí)用文案標(biāo)準(zhǔn)文檔），根據(jù)曲線上各節(jié)點(diǎn)是在扇形外還是在扇形內(nèi)，決定節(jié)點(diǎn)是保留還是舍去。其優(yōu)點(diǎn)是光欄法不

8、僅算法嚴(yán)密，能按給定閾值保留曲線特征點(diǎn)