GIS算法基礎重點

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

算法的設計原則是—正確性—、—確定性_、—清晰性_。算法的復雜度包括—算法的時間復雜度—、—算法的空間復雜度_。Egenhofer(1993)構造出一個由 邊界_、_內部_、_外部 的點集組成的9—交空間關系模型(9IM)。折線段的拐向判斷方法可以直接由矢量叉積的性質推出。對于有公共端點的線段PP和PP，通過計算(P-P)X(P-P)的符號便可以確定折線段的拐向：若01122010(P-P)x(P-P)>0,則PP在P點拐向右側后得到PP；若(p-P)20100111220x(P-P)<0,則PP在P點拐向左側后得到PP;若(P-P)x(P-1001112201P)=0,則P、P、P三點共線 。0012在空間查詢中，最常用的兩種查詢是—按屬性信息的要求來查詢定位空間位置_和—根據(jù)對象的空間位置查詢有關的屬性信息?。實現(xiàn)一種地圖投影點的坐標變換為另一種地圖投影點的坐標，就是要找出fx=f1($Y) 關系式，其方法有_解析變換法_、_數(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軸線或邊界上的相鄰三點P、P、P，用 右手螺旋i-1i i+1 法則判斷軸線(邊界)轉折點的凸凹性，若拇指向下，則P點左側為—凸—，右側為凹_。i在下面選項中，不屬于數(shù)據(jù)挖掘步驟的是(B)。A數(shù)據(jù)變換 A數(shù)據(jù)變換 B數(shù)據(jù)分類C數(shù)據(jù)清理 D知識表示有六種多項式時間算法最為常見，其關系為(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)

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