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

一、算法的時(shí)間復(fù)雜性T(n):利用某算法處理一個(gè)問題規(guī)模為n的輸入所需要的時(shí)間?？臻g：為了解求問題的實(shí)例而執(zhí)行的計(jì)算步驟所需要額內(nèi)存空間(或字)數(shù)目，不包括用來存儲(chǔ)輸入的空間。算法空間復(fù)雜性不可能超過運(yùn)行時(shí)間的復(fù)雜性。元運(yùn)算:對(duì)于任何計(jì)算步驟，不管輸入數(shù)據(jù)或執(zhí)行的算法，它的代價(jià)總是以一個(gè)時(shí)間常量為上界，則稱該計(jì)算步驟為元運(yùn)算?；诒容^的排序問的最優(yōu)算法：我們通常把在O(nlgn)時(shí)間內(nèi)用元素比較法排序的任何算法，稱為基于比較的排序問題的最優(yōu)算法。一般來說，如果可以證明任何一個(gè)求解問題A的算法必定是Q(f(n))，那么我們把在O(f(n))時(shí)間內(nèi)求解任何問題A的任何算法都稱為問題A的最優(yōu)算法。算法設(shè)計(jì)原則:正確性確定性清晰性。算法的要素:1.待解問題的描述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)交。線段在多邊形內(nèi)判斷步驟:1.先求出所有和線段相交的多邊形的頂點(diǎn)2?然后按照X-Y坐標(biāo)排序(X坐標(biāo)小的排在前面，對(duì)于X坐標(biāo)相同的點(diǎn)，丫坐標(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)仁Q1Q2，要計(jì)算的就是L0和L1的交點(diǎn)：第一步：首先判斷L0和L1是否相交2?若L1不平行與丫軸，則交點(diǎn)橫坐標(biāo)為P1的橫坐標(biāo)，代入到L1的直線方程中可以計(jì)算出交點(diǎn)縱坐標(biāo)。第三步：若L1平行于y軸，則第四步：若L0平行于x軸，有2種情況，第五步：若L1平行于x軸，則，第六步：若L1和L0斜率均存在，貝I」。中心點(diǎn)的計(jì)算：多邊形的中心點(diǎn)（又叫質(zhì)心或重心）可以通過將多邊形分割成為三角形，求取三角形的中心點(diǎn)，然后將三角形的中心點(diǎn)加權(quán)求和取得。三點(diǎn)畫圓：算法關(guān)鍵是求取圓心和園半徑：第一步：求取圓心，第二步：求取半徑R，IIR=（（xa-xp）A2+（ya-yp）A2）A1/2Op是圓心。四、矢量線柵格化三種方法：八方向柵格化、全路徑柵格化、恒密度柵格化。矢量面格式向柵格面格式轉(zhuǎn)換又稱為多邊形填充，就是在矢量表示的多邊形邊界內(nèi)部的所有柵格點(diǎn)上賦以相應(yīng)的多邊形編碼，從而形成柵格數(shù)據(jù)陣列。方法有：內(nèi)部點(diǎn)擴(kuò)散算法（種子，八方向擴(kuò)散）射線算法和掃II描算法、邊界代數(shù)算法（積分、拓?fù)洌〇鸥駭?shù)據(jù)矢量化有4個(gè)基本步驟:1.邊界提取2?邊界線追蹤3?拓?fù)潢P(guān)系生成4?去除多余點(diǎn)及曲線圓滑。細(xì)化算法：柵格數(shù)據(jù)需要細(xì)化，以提取其中軸線，因?yàn)椋?.中軸線是柵格數(shù)據(jù)曲線的標(biāo)準(zhǔn)化存儲(chǔ)形式2?實(shí)現(xiàn)細(xì)化是將柵格曲線矢量化的前提3?在有些算法中可以提高計(jì)算精度。細(xì)化算法可分兩大類：第一大類是基于距離變換，首先得到骨架像元，然后跟蹤距離變換圖中的“山脊線”，并將其作為中軸線；第二類是基于在不破壞柵格拓?fù)溥B通性的前提下，按對(duì)稱的原則刪除影像邊緣的柵格點(diǎn)。四例：1?用距離變換法捜尋中軸線（減細(xì)）2?最大數(shù)值計(jì)算法（V值4、1）3?經(jīng)典的細(xì)化算法4?邊緣跟蹤剝皮法?多邊形柵格轉(zhuǎn)矢量的雙邊界捜索算法：基本思想：通過邊界提取，將左右多邊形信息保存在邊界點(diǎn)上，每條邊界弧段由兩個(gè)并行的邊界鏈組成，分別記錄該邊界弧段的左右多邊形編號(hào)。具體步驟：1?邊界點(diǎn)和結(jié)點(diǎn)提取2?邊界線搜索與左右多邊形信息記錄3?多余點(diǎn)去除。多邊形柵格轉(zhuǎn)矢量的單邊界搜索算法：?jiǎn)芜吔缢阉魉惴〞r(shí)通過對(duì)傳統(tǒng)的區(qū)域跟蹤算法進(jìn)行改進(jìn)而形成的，傳統(tǒng)區(qū)域跟蹤算法中，對(duì)區(qū)域的描述由兩部分組成：區(qū)域外輪廓和內(nèi)部孔洞。單邊界搜索算法流程:1?跟蹤、搜索第一層所有的區(qū)域并記錄外輪廓和內(nèi)部孔洞信息2?根據(jù)跟蹤到的孔洞信息找出下一層中未跟蹤過的區(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è)扇形（“喇叭口”），根據(jù)曲線上各節(jié)點(diǎn)是在扇形外還是在扇形內(nèi)，決定節(jié)點(diǎn)是保留還是舍去。其優(yōu)點(diǎn)是光欄法不僅算法嚴(yán)密，能按給定閾值保留曲線特征點(diǎn)，并按時(shí)處理，運(yùn)算量小，占用內(nèi)存少。鏈?zhǔn)骄幋a：多邊形邊界可定義為：由某一原點(diǎn)開始并按某些基本方向確定的單位矢量鏈。（東0東南1東北7）游程長(zhǎng)度編碼：游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程長(zhǎng)度編碼結(jié)構(gòu)是逐行將相鄰?fù)档木W(wǎng)格合并，并記錄合并后網(wǎng)格的值及合并網(wǎng)格的長(zhǎng)度，其目的是壓縮柵格數(shù)據(jù)量，消除數(shù)據(jù)間的冗余。塊式編碼：塊式編碼是將游程長(zhǎng)度編碼擴(kuò)大到二維的情況，把多邊形范圍劃分成由像元組成的正方形，然后對(duì)各個(gè)正方形進(jìn)行編碼。差分映射法：就是選擇某一參照值對(duì)有關(guān)柵格的屬性值進(jìn)行求差運(yùn)算，根據(jù)差值得到一個(gè)新的柵格數(shù)據(jù)層。（分行選取和全區(qū)選?。┩?fù)潢P(guān)系左轉(zhuǎn)算法描述如下:1.順序取一個(gè)結(jié)點(diǎn)作為起始結(jié)點(diǎn)，取完為止；取過該結(jié)點(diǎn)的方位角最小的未使用過的或僅使用一次，且使用過的方向與本次相反的弧段作為起始弧段。2?取這條弧段的另一個(gè)結(jié)點(diǎn)，找這個(gè)結(jié)點(diǎn)關(guān)聯(lián)的弧段集合中的本條弧段的下一條弧段，如果本條弧段是最后一條弧段，則取弧段集合的第一條弧段，作為下一條弧段。3?判斷是否回到起點(diǎn)，如果是，則形成了一個(gè)多邊形，記錄下它，并且根據(jù)弧段的方向，設(shè)置組成該多邊形的左右多邊形信息；否則轉(zhuǎn)2。4?取起始點(diǎn)上開始的，剛才所形成多邊形的最后一條邊作為新的起始弧段，轉(zhuǎn)2;若這條弧段已經(jīng)使用過兩次，即形成了兩個(gè)多邊形，轉(zhuǎn)1。島的判斷問題算法如下：1.計(jì)算所有多邊形的面積2?分別對(duì)面積為正的多邊形和面積為負(fù)的多邊形排序，分別形成正多邊形和負(fù)多邊形集合。3?如果負(fù)多邊形集合的個(gè)數(shù)為1，結(jié)束程序；否則，從面積為正的多邊形集合中，順序取出一個(gè)多邊形，如果正多邊形已經(jīng)都被訪問過，則程序結(jié)束。4?依次從負(fù)多邊形集合中取出負(fù)多邊形，判斷當(dāng)前取出的正多邊形是否包含該多邊形，如果包含，就將該負(fù)多邊形加入當(dāng)前取出的正多邊形中，形成復(fù)雜多邊形，設(shè)置負(fù)多邊形的組成弧段的拓?fù)湫畔ⅲ呢?fù)多邊形集合中刪除該負(fù)多邊形。當(dāng)所有負(fù)多邊形都被訪問一遍后轉(zhuǎn)3.六、直線方程的所有形式：P(t)=Po+tVi=PO+t(Pi-Po)=(1-t)Po+tPi 。(yO-y1)x+(x1-xO)y+(xOy1-x1yO)=O。P(t)=(xO+tcos05yO+tsin0)點(diǎn)到直線 距 離 計(jì) 算 公式:d(P,L)=((y0-y1)x+(x1-x0)y+(x0y1-x1y0))/((x1-x0)A2+(y1-y0)A2)A1/2.三角形面積計(jì)算公式:A=1/2*bh,A=1/2*absin0，A=(s(s-a)(s-b)(s-c))i/2,s=1/2*(a+b+c),A=1/4*(4a2b2-(a2+b2-C2)2)i/2，A=b2/2(cot 0 +cot p ) oA=1/2|v*w|=1/2|(v1-v0)(v2-v0)|,2A=(x1-x0)(y2-y0)-(x2-x0)(y1-y0)o四邊形面積計(jì)算公式：A=((s-a)(s-b)(s-c)(s-d))1/2 ，A(v0v1v2v3)=|(v1-v0)*(v3-v0)|，A=(x1-x0)(y3-y0)-(x3-x0)(y1-y0)，A=1/2|(v2-v0)*(v3-v1)|，2A=(x2-x0)(y3-y1)-(x3-x1)(y2-y0)o任意二維平面多邊形面積計(jì)算方法與公式：A多邊形噸a(4)，4=apvm+1，注意：對(duì)于一個(gè)逆時(shí)針多邊形，當(dāng)點(diǎn)P在邊VVi+1的左邊，則A的面積是正的；相反，當(dāng)點(diǎn)p在邊vm+1的右邊，并且位于多邊形外部，則4的面積是負(fù)的。如果是一個(gè)順時(shí)針多邊形，則符號(hào)相反，并且內(nèi)部的三角形面積為負(fù)的。七、空間索引：就是指依據(jù)空間對(duì)象的位置和形狀或空間對(duì)象之間的某種空間關(guān)系，按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)，其中包括空間對(duì)象的概要信息。B樹的定義：一個(gè)m階的B樹，或?yàn)榭諛?，或是為滿足下列特征的m叉樹。（1）樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹；（2）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩顆子樹；（3）除根之外的所有非終端結(jié)點(diǎn)至少有[m/2]棵子樹；（4）所有的非葉結(jié)點(diǎn)中包含下列信息數(shù)據(jù)（A0i<K15A1,D1>5<K25A25D2>5...5Kn5An5Dn>）式中金=1,2…n）為關(guān)鍵字，且KjVKi+1（i=O,…n）為指向子樹根節(jié)點(diǎn)的指針，且指針Ai-1所指的子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki（i=1，…n）;An所指的子樹中所有結(jié)點(diǎn)的關(guān)鍵字均大于Kn;Dn為數(shù)據(jù)指針，指向關(guān)鍵字Kn所在的數(shù)據(jù)記錄。<KAD>稱為結(jié)點(diǎn)的一個(gè)元素。（5）所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息（可以看作是外部結(jié)點(diǎn)查詢失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空）插入算法：設(shè)將元素<K,A,D>插入B樹中。（1）首先在樹中查找K，若查找到，算法結(jié)束（假定B樹中不容許有相同的關(guān)鍵字存在）若沒有查到，設(shè)最后查到的結(jié)點(diǎn)為N。將關(guān)鍵字K插入結(jié)點(diǎn)N中，若結(jié)點(diǎn)N的元素的個(gè)數(shù)小于等于m-1，將A指向葉結(jié)點(diǎn)，插入結(jié)束，若結(jié)點(diǎn)N的元素關(guān)鍵字的個(gè)數(shù)為m，則需分裂結(jié)點(diǎn)N。（2）設(shè)插入關(guān)鍵字K后的結(jié)點(diǎn)情況如下（A0,<K1,A1,D1>,<K2,A2,D2>^.<Km,Am,Dm>）創(chuàng)建一新結(jié)點(diǎn)L，將N中的第[m/2+1]以及其后的所有元素，共m-[m/2]個(gè)元素移入新結(jié)點(diǎn)L中。再將元素<K[m/2],A[m/2],D[m/2]>移出N，插入結(jié)點(diǎn)N的父結(jié)點(diǎn)。N的父結(jié)點(diǎn)還可能需要分裂，最壞的情況是分裂一直延續(xù)到根結(jié)點(diǎn)，最后產(chǎn)生新的根結(jié)點(diǎn)，樹高增加1。當(dāng)插入操作引起了s個(gè)結(jié)點(diǎn)的分裂時(shí)，磁盤訪問的次數(shù)為h（讀取搜索路徑上的結(jié)點(diǎn)）+2s（回寫兩個(gè)分裂出的新結(jié)點(diǎn)）+1（回寫新的根結(jié)點(diǎn)或插入后沒有導(dǎo)致分裂的結(jié)點(diǎn)）因此，所需要的磁盤訪問次數(shù)是h+2s+1，最多可達(dá)3h+1。R樹的定義:設(shè)M為結(jié)點(diǎn)中單元的最大數(shù)目，m（1<=mv=M/2）為非根結(jié)點(diǎn)中單元個(gè)數(shù)的下限。（1）每個(gè)葉子結(jié)點(diǎn)包含的單元個(gè)數(shù)介于m與M之間，除非它同時(shí)是根結(jié)點(diǎn)。（2）每個(gè)葉子結(jié)點(diǎn)中的單元（l,SpatialObjectlD）中，I是包含該n維空間對(duì)象的MBR，SpatialObjectID是該空間對(duì)象的IDO（3）每個(gè)非葉子結(jié)點(diǎn)的子結(jié)點(diǎn)樹介于m到M之間，除非它同時(shí)是跟結(jié)點(diǎn)。（4）每個(gè)非葉子的結(jié)點(diǎn)的單元（|，PointerToChild）中，I是包含子結(jié)點(diǎn)的MBR，PointerToChild是指向子結(jié)點(diǎn)的指針。通過該指針能訪問到子結(jié)點(diǎn)。（5）根結(jié)點(diǎn)最少有兩個(gè)字結(jié)點(diǎn)，除非它同時(shí)是葉子的結(jié)點(diǎn)。（6）所有的葉子結(jié)點(diǎn)都處于樹的同一層上。插入算法：新空間對(duì)象的插入操作:（1）為新的空間對(duì)象，尋找一個(gè)合適的葉子結(jié)點(diǎn)（2）將新的空間對(duì)象記錄到葉子的結(jié)點(diǎn)中，（3）調(diào)整樹的結(jié)構(gòu)（4）生成新的根結(jié)點(diǎn)。選擇合適的葉子結(jié)點(diǎn):（1）初始化（2）判斷是否為葉子結(jié)點(diǎn)（3）選擇合適的子樹。調(diào)整樹的結(jié)構(gòu)：（1）初始化（2）判斷是否是根結(jié)點(diǎn)（3）調(diào)整父結(jié)點(diǎn)相應(yīng)單元的I（4）根據(jù)需要進(jìn)一步分裂父結(jié)點(diǎn)。常規(guī)四叉樹缺點(diǎn)：所占的內(nèi)外存空間比較大，原因在于它不僅要記錄每個(gè)結(jié)點(diǎn)值，還需記錄結(jié)點(diǎn)的一個(gè)前趨結(jié)點(diǎn)及四個(gè)后繼結(jié)點(diǎn)，以反映結(jié)點(diǎn)之間的聯(lián)系。對(duì)柵格數(shù)據(jù)進(jìn)行運(yùn)算時(shí)，還要作遍歷樹結(jié)點(diǎn)的運(yùn)算。這樣就增加了操作的復(fù)雜性。線性四叉樹的基本思想和優(yōu)缺點(diǎn)：線性四叉樹不像常規(guī)四叉樹那樣存儲(chǔ)樹中各個(gè)結(jié)點(diǎn)及其相互間關(guān)系，而是通過編碼四叉樹的葉結(jié)點(diǎn)來表示數(shù)據(jù)塊的層次和空間關(guān)系。葉結(jié)點(diǎn)都具有一個(gè)反映位置的關(guān)鍵字，亦稱位置碼，表示它所處位置。實(shí)質(zhì)是把原來大小相等的柵格集合轉(zhuǎn)變成大小不等的正方形集合，并對(duì)不同尺寸和位置的正方形集合賦予一個(gè)位置碼。缺點(diǎn)：位置碼的位數(shù)決定分割的層數(shù)，圖形越復(fù)雜，分割的層數(shù)越多，相應(yīng)的位置碼得位數(shù)亦越多，這種自上而下的分割方法需要大量重復(fù)運(yùn)算，效率比較低。線性四又樹的編碼方法：基于深度和層次碼的線性四叉樹編碼；基于四進(jìn)制的線性四叉樹編碼；四叉樹的十進(jìn)制編碼。的概念：指的是完成一個(gè)任務(wù)所需要的具體步驟和方法。常用的算法有窮舉搜索法，遞歸法，回溯法，貪心法，分治法。算法設(shè)計(jì)的原則:正確性，確定性，清晰性。時(shí)間復(fù)雜性：去除了表示算法運(yùn)行時(shí)間的函數(shù)中的低階項(xiàng)和首項(xiàng)系數(shù)，就稱度量算法的漸進(jìn)運(yùn)行時(shí)間?？臻g復(fù)雜性：為了求解問題實(shí)例而執(zhí)行的計(jì)算步驟所需要的內(nèi)存空間數(shù)目，它不包括分配用來存儲(chǔ)輸入的空間.元運(yùn)算：對(duì)于任何計(jì)算步驟，他的代價(jià)是以一個(gè)時(shí)間常量為上界，而不管輸入數(shù)據(jù)或執(zhí)行的算法，這個(gè)計(jì)算步驟叫做元運(yùn)算。(算術(shù)，比較，邏輯，賦值)最優(yōu)算法：如果可以證明任何一個(gè)求解的問題A的算法必定是Q(f(n)),那么我們把在o（f（n））時(shí)間內(nèi)求解問題A的任何算法都稱為問題A的最優(yōu)算法。關(guān)系運(yùn)算是指用于檢驗(yàn)兩個(gè)幾何對(duì)象的特定的拓?fù)淇臻g關(guān)系的邏輯方法。判斷兩直線相交：1）快速排斥實(shí)驗(yàn)，設(shè)以線段p1p2，Q1Q2為對(duì)角線的矩形不想交，則兩線段不相交。2）跨立實(shí)驗(yàn)如果兩個(gè)線段相交，則一定跨立對(duì)方運(yùn)用矢量乘法乘積小于零則位于兩邊。判斷點(diǎn)是不是在多邊形內(nèi)1）射線法，一條射線從點(diǎn)P開始，穿過多邊形的邊界的次數(shù)成為交點(diǎn)數(shù)目，當(dāng)交點(diǎn)數(shù)目為偶數(shù)時(shí)，點(diǎn)在多邊形外部，不然在內(nèi)部。2）轉(zhuǎn)角發(fā)，多邊形環(huán)繞點(diǎn)P的次數(shù)成為環(huán)繞數(shù)，環(huán)繞數(shù)為零，在多邊形外部，不然在內(nèi)部。判斷線段是不是在多邊形內(nèi)：線段在多邊形內(nèi)的必要條件是兩個(gè)端點(diǎn)都在多邊形內(nèi)，線段和多邊形的所有邊都不內(nèi)交。如果多邊形的一個(gè)頂點(diǎn)和線段相交，還必須判斷兩個(gè)相鄰交點(diǎn)之間的線段是不是包含與多邊形內(nèi)部。計(jì)算線段或直線與線段的交點(diǎn)：第一步判斷兩條線是不是相交，如果不像交，沒有交點(diǎn)。第二到第五步分別判斷平行與X,丫軸的情況。第六步兩條線斜率都存在并且不為零。中心點(diǎn)的計(jì)算：重心（分割三角形，加權(quán)求的，權(quán)重為三角形面積站的多邊形面積比例）三點(diǎn)畫圓：求圓心P，求取圓的半徑。柵格數(shù)據(jù)向矢量格式的轉(zhuǎn)換步驟：1）邊界提取，采用高通濾波將柵格圖像二值化或者以特殊值標(biāo)識(shí)邊界點(diǎn)。2）邊界線追蹤，對(duì)每個(gè)邊界弧段由一個(gè)結(jié)點(diǎn)向另一個(gè)結(jié)點(diǎn)搜索，通常對(duì)每個(gè)已知邊界點(diǎn)需沿除了進(jìn)入方向的其他七個(gè)方向搜索下一個(gè)邊界，直到連成邊界弧段。3）拓?fù)潢P(guān)系生成，對(duì)于矢量表示得邊界弧段數(shù)據(jù)，判斷其與原圖上各多邊形的空間關(guān)系，以形成完整的拓?fù)浣Y(jié)構(gòu)并建立與屬性數(shù)據(jù)的聯(lián)系。4）去除多余點(diǎn)及曲線圓滑，由于搜索是逐個(gè)柵格進(jìn)行的，必須去除由此造成的多余點(diǎn)記錄，以減少數(shù)據(jù)繁雜，搜索結(jié)果，曲線由于柵格精度的限制可能不夠圓滑，需要采用一定的插補(bǔ)算法進(jìn)行光滑處理，常用的算法有線性迭代法，分段三次多項(xiàng)式插值法，正軸拋物線平均加權(quán)法。tn斜軸拋物線平均加權(quán)法，樣條函數(shù)插值法。多邊形柵格轉(zhuǎn)矢量的雙邊界捜索算法：思想是通過邊界提取，將左右多邊形信息保存在邊界點(diǎn)上，每條邊界弧段甴兩個(gè)并行的邊界鏈組成，分別記錄該邊界弧段的左右多邊形編號(hào)。邊界線搜索采用2*2的柵格窗口，在每個(gè)窗口內(nèi)4個(gè)柵格數(shù)據(jù)的模式，可以唯一地確定下一個(gè)窗口的搜索方向和該弧段的拓?fù)潢P(guān)系，極大的加快了搜索速度，拓?fù)潢P(guān)系也很容易建立，步驟tn（1）邊界點(diǎn)和結(jié)點(diǎn)提取2）邊界線搜索與左右多邊形信息記錄3）多余點(diǎn)去除。單邊界捜索算法：對(duì)區(qū)域的描述由兩部分組成，區(qū)域外輪廓和內(nèi)部孔洞，確定外輪廓跟蹤起始點(diǎn)，對(duì)區(qū)域的外輪廓進(jìn)行跟蹤和記錄，對(duì)區(qū)域內(nèi)部的所有孔洞進(jìn)行掃描跟蹤和記錄。將圖像中的所有區(qū)域按包含關(guān)系分為若干層，每一層至少包含一個(gè)區(qū)域?qū)ο螅鞒蹋?搜索跟蹤第一層所有的區(qū)域并記錄外輪廓和內(nèi)部孔洞信息2根據(jù)跟蹤到的空孔洞信息找出下一層中未跟蹤過的區(qū)域的外輪廓跟蹤起始點(diǎn)；3跟蹤找到的新區(qū)域并記錄其外輪廓和內(nèi)部孔洞信息4重復(fù)2，3步直到該層所有區(qū)域都已被跟蹤完畢5重復(fù)2-4步知道整幅圖像內(nèi)所有區(qū)域都已被跟蹤完畢。拓?fù)潢P(guān)系生成過程：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)號(hào)，多邊形內(nèi)部標(biāo)識(shí)號(hào)的自動(dòng)生成?？臻g索引：是指依據(jù)空間對(duì)象的位置和形狀或空間對(duì)象之間的目中空間關(guān)系，按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)，其中包括空間對(duì)象的概要信息。B樹定義：一個(gè)M階的B樹1）樹中每個(gè)結(jié)點(diǎn)至多有M棵子樹2）若根結(jié)點(diǎn)不是葉子節(jié)點(diǎn)。至少有兩棵子樹3）除根之外的所有非終端節(jié)點(diǎn)至少有M/2（取整）棵子樹4）所有的非葉結(jié)點(diǎn)中包含（A0，<K1,A1,D1>,..…<KN,AN,DN>）Ki為關(guān)鍵字，Ai為指針,Dn為數(shù)據(jù)指針5）所有的葉子節(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息。R樹定義：1）每個(gè)葉子節(jié)點(diǎn)包含的單元個(gè)數(shù)介于m和M之間，除非它同時(shí)是根節(jié)點(diǎn)。2）每個(gè)葉子結(jié)點(diǎn)中的單元中，I是包含該n維空間對(duì)象的MBR,ID。3）每個(gè)葉子節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)介于m和M之間，除非它是根節(jié)點(diǎn)。4）每個(gè)非葉子節(jié)點(diǎn)的單元中，I是包含子節(jié)點(diǎn)的MBR，POINTER是指向子節(jié)點(diǎn)的指針，通過該指針能訪問到子結(jié)點(diǎn)5）根節(jié)點(diǎn)最少有兩個(gè)子結(jié)點(diǎn)，除非它同時(shí)是葉子結(jié)點(diǎn)6）所有的葉子節(jié)點(diǎn)都處于樹的同一層上。

算法的設(shè)計(jì)原則是—正確性—、—確定性_、—清晰性_。算法的復(fù)雜度包括—算法的時(shí)間復(fù)雜度—、—算法的空間復(fù)雜度_。Egenhofer(1993)構(gòu)造出一個(gè)由 邊界_、_內(nèi)部_、_外部 的點(diǎn)集組成的9—交空間關(guān)系模型(9IM)。折線段的拐向判斷方法可以直接由矢量叉積的性質(zhì)推出。對(duì)于有公共端點(diǎn)的線段PP和PP，通過計(jì)算(P-P)X(P-P)的符號(hào)便可以確定折線段的拐向：若01122010(P-P)x(P-P)>0,則PP在P點(diǎn)拐向右側(cè)后得到PP；若(p-P)20100111220x(P-P)<0,則PP在P點(diǎn)拐向左側(cè)后得到PP;若(P-P)x(P-1001112201P)=0,則P、P、P三點(diǎn)共線 。0012在空間查詢中，最常用的兩種查詢是—按屬性信息的要求來查詢定位空間位置_和—根據(jù)對(duì)象的空間位置查詢有關(guān)的屬性信息?。實(shí)現(xiàn)一種地圖投影點(diǎn)的坐標(biāo)變換為另一種地圖投影點(diǎn)的坐標(biāo)，就是要找出fx=f1($Y) 關(guān)系式，其方法有_解析變換法_、_數(shù)值解析Iy=f(Ey)2變換法和數(shù)值變化法(X2,y2)，…'S=1￡2(X2,y2)，…'S=1￡2i=ixiX

i+1yiy.i+1P(X,y)表示，其面積為nn n軸線或邊界上的相鄰三點(diǎn)P、P、P，用 右手螺旋i-1i i+1 法則判斷軸線(邊界)轉(zhuǎn)折點(diǎn)的凸凹性，若拇指向下，則P點(diǎn)左側(cè)為—凸—，右側(cè)為凹_。i在下面選項(xiàng)中，不屬于數(shù)據(jù)挖掘步驟的是(B)。A數(shù)據(jù)變換 A數(shù)據(jù)變換 B數(shù)據(jù)分類C數(shù)據(jù)清理 D知識(shí)表示有六種多項(xiàng)式時(shí)間算法最為常見，其關(guān)系為(D)。A0(1)<0(logn)<0(nlogn)<0(n)<0(n2)<0(n3)B0(1)<0(logn)<0(n)<0(n2)<0(nlogn)<0(n3)C0(1)<0(nlogn)<0(n)<0(logn)<0(n2)<0(n3)D0(1)<0(logn)<0(n)<0(nlogn)<0(n2)<0(n3)

我國(guó)現(xiàn)在采用的1980國(guó)家大地坐標(biāo)系應(yīng)用的是哪種地球橢球體參數(shù)（B）。A克拉索夫斯基橢球 B1975國(guó)際橢球CWGS-84系橢球 D1980國(guó)際橢球磁盤訪問次數(shù)是影響空間索引性能的關(guān)鍵指標(biāo)，下面哪種空間索引方法是比較優(yōu)秀的空間索引方法。（A）ACELL樹 BR樹 CB+樹 DR+樹（A）反映城市的帶狀延伸程度，帶狀延伸越明顯則延伸率越大，反映城市的離散程度越大。A伸延率 B緊湊度 C緊湊度指數(shù) D放射狀指數(shù)在矢量緩沖區(qū)的實(shí)現(xiàn)算法中對(duì)于雙線問題最簡(jiǎn)單的方法是（C）。A凸角圓弧法 B疊置算法 C角平分線法D圓弧擬合法下圖按照前序遍歷的方法寫出結(jié)果。（A）TOC\o"1-5"\h\zAa+ b * c -d - e / fB-+ a * b -c d / e fCab c d - *+ e f / -D沒有正確答案）。A聚類分析 B疊置分析C主成分分析）。A聚類分析 B疊置分析C主成分分析D層次分析法下面關(guān)于點(diǎn)緩沖區(qū)邊界生成算法的敘述哪一條正確？（A）A等分的圓心角越小，步長(zhǎng)越小，誤差越?。籅等分的圓心角越大，步長(zhǎng)越小，誤差越?。籆等分的圓心角越大，步長(zhǎng)越小，誤差越大；D等分的圓心角越小，步長(zhǎng)越大，誤差越小。在下面選項(xiàng)中，不屬于B-樹的性質(zhì)的是（D）。A多叉樹 B查找樹 C平衡樹 D二叉樹無向圖的鄰接矩陣是不對(duì)稱的。 （X）在多邊形的方向判斷中，多邊形邊界順時(shí)針方向稱為負(fù)方向。 （X）TOC\o"1-5"\h\z算法。 （）判斷圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小于等于圓心到矩四邊的距離的最小值。 （）網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)的基本組成部分和屬性是鏈和結(jié)點(diǎn)。 （）所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存仍然相鄰這種存儲(chǔ)方式是鏈接存儲(chǔ)方式。 （X）緊湊度是反映城市的緊湊程度，其中圓形區(qū)域被認(rèn)為最緊湊，緊湊度為1。其它形狀的區(qū)域，其離散程度越小則緊湊度越低。 （X）緩沖區(qū)實(shí)現(xiàn)算法有矢量方法和柵格方法兩種。 （）對(duì)于塊式編碼來說，圖斑越碎，壓縮比越高。 （X）矢量數(shù)據(jù)的壓縮往往是不可逆的，數(shù)據(jù)壓縮后數(shù)據(jù)量變小了，但數(shù)據(jù)的精度不變。 （X）維述擴(kuò)展的9交集模型關(guān)系非常復(fù)雜，通過對(duì)大量的空間關(guān)系進(jìn)行歸納和分類,得出5種基本的空間關(guān)系，這5種關(guān)系定義為空間關(guān)系的最小集,他們具有哪些特征？（1）相互之間不能進(jìn)行轉(zhuǎn)化；（2）能覆蓋所有的空間關(guān)系模式；（3）能應(yīng)用于同維與不同維的幾何目標(biāo)；（4）每一種關(guān)系對(duì)應(yīng)于唯一的DE-9IM矩陣；（5）任何其它的DE-9IM關(guān)系可以通過用這5種基本關(guān)系進(jìn)行表達(dá)。簡(jiǎn)述Dijkstra算法的步驟。（1）引進(jìn)一個(gè)輔助向量D,它的每個(gè)分量D[i]表示當(dāng)前所找到的從起點(diǎn)vm到每個(gè)終點(diǎn)vi的最短路徑的長(zhǎng)度。假設(shè)用帶權(quán)的鄰接矩陣arcs來表示帶權(quán)有向圖，arcs[i][j]表示?。紇i,若<vi,vj>不連通，則arcs[i][j]=8。那么D[i]的初值為：D[i]=arcs[m][i]vieV此外，將已找到的從vm出發(fā)的最短路徑的終點(diǎn)的集合記為S,它的初始狀態(tài)為空集。選擇vj使得D[j]=Min{D[i]|vieV-S}Vj就是當(dāng)前求得的一條從vm出發(fā)的最短路徑的終點(diǎn)。其中j為這條最短路徑的終點(diǎn)，將其加入到終點(diǎn)集合S,令S=SU{j}修改輔助向量D,即修改從vm出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長(zhǎng)度。顯然，若D[j]+arcs[j][k]<D[k],貝廿表明從vm出發(fā)，經(jīng)過vj到達(dá)vk的路徑更短。因此，如果D[j]+arcs[j][k]<D[k]，則修改D[k]為D[k]=D[j]+arcs[j][k]重復(fù)操作第二步、第三步共n-1次。由此求得從v到圖上其余各頂點(diǎn)的最短路徑是依路徑長(zhǎng)度遞增的序列。在動(dòng)態(tài)緩沖區(qū)生成算法中主要是針對(duì)哪兩類特殊情況提出的？并寫出他們的生成方法。答：動(dòng)態(tài)緩沖區(qū)生成是針對(duì)兩類特殊情況提出的：一類是流域問題：從流域上游的某一點(diǎn)出發(fā)沿流域下朔，河流的影響半徑或流域的輻射范圍逐漸擴(kuò)大；相反，則逐漸縮小。另一類是污染問題。污染源對(duì)鄰近對(duì)象的影響程度隨距離的增大而逐漸縮小。對(duì)于流域問題，可以基于線目標(biāo)的緩沖區(qū)生成算法，采用分段處理