GIS算法基礎(chǔ)整理(填空)

1、第1章l 算法設(shè)計的原則：P1（）、（）、（）l 算法的復(fù)雜性：P2（）復(fù)雜性和（）復(fù)雜性l 時間復(fù)雜性定義：P2利用某算法處理一個問題規(guī)模n的輸入所需要的時間l 空間復(fù)雜性定義：P8算法在運行過程中臨時占用的存儲空間的大小第2章l 維數(shù)拓展的9交模型：P15 I內(nèi)部、B邊界、E外部，內(nèi)部包括左邊界和下邊界l 模型示例P16：II,IB,IE,BI,BB,BE,EI,EB,EEl T,F,*,0,1,2的含義P16-17l 空間關(guān)系判定：P17 相離、（）、（）、（）、（）。l P表示零維幾何體，L一維，A二維l 用DE-9IM模型表示：P17-20相離FF*FF*相接FT*或( )或( )

2、（除P/P）相交T*T*（P/L P/A L/A）,（ ）(L/L)真包含T*F*F*疊置T*T*T* (A/A P/P) ( ) (L/L)包含a.Contains(b)b.Within(a)相交a.Intersects(b)!a.Disjoint(b)l 矢量叉積定義：P22由（ ）、（ ）、（ ）所組成的平行四邊形的帶（ ）的面積。l 順逆時針關(guān)系：P22 P×Q>0，P在Q的（ ）方向，反之，P在Q的（ ）方向，若為0，則（ ），可能（ ）也可能（ ）l 折線段的拐向判斷：P23 若大于0，則拐向（ ），反之拐向（ ），等于零，三點共線。l 快速排斥試驗P23-24圖l

3、 跨立試驗：P23(P1-Q1)×(Q2-Q1) ×(Q2-Q1) ×(P2-Q1)0P1P2跨立Q1Q2l 前方交會基本概念P40-41l 距離交會基本概念P41-43第3章l 平面坐標(biāo)變換矩陣：P45 T=adgbehcfi，abde縮放、旋轉(zhuǎn)、對稱、錯切變換，cf平移變換，gh投影變換，i伸縮變換l 幾個變換矩陣：P46-49l 相對于某個點的變換：P49 先把坐標(biāo)系原點平移到某個點，在新的坐標(biāo)系下做比例或旋轉(zhuǎn)變換后，再將坐標(biāo)原點平移回去。l 常用的球面坐標(biāo)系：P50 ( )坐標(biāo)系，（ ）坐標(biāo)系，（ ）坐標(biāo)系。l 仿射變換的概念：P54 在保留（ ）條件下，

4、仿射變換允許對長方形目標(biāo)做（ ）、（ ）、（ ）、（ ）變換。l 仿射變換的性質(zhì)：筆記 點變（ ），直線變（ ），點與直線的（ ）關(guān)系不變。l 控制點估算：P54至少需要（ ）個控制點用于估算才有效，用（ ）個或更多控制點來減小測量誤差。l 地圖投影變換的方法：P55 解析變換法、（ ）法、（ ）法。l 一些常識：筆記 北京54坐標(biāo)系克拉夫斯基橢球參數(shù)西安80坐標(biāo)系1975國際橢球參數(shù)GPS WGS-84l 在何種比例尺用何種投影：P62-69小比例尺：( )投影大比例尺：( )投影、( )投影第4章l 矢量線柵格化的方法：P71 ()柵格化、（）柵格化、恒密度柵格化。l 內(nèi)部點擴散法：P73

5、-74 由每個多邊形一個內(nèi)部點（種子點）開始，向其8個方向的鄰點擴散，判斷各個新加入的點是否在多邊形邊界上。若在邊界上，則該新加入點（）。否則把（ ）作為新種子點與原有種子點一起進行新的擴散運算，并將該種子點賦以該多邊形的編號。重復(fù)上述過程直到（ ）并遇到邊界停止為止。l 邊界代數(shù)法：P75-77 單個多邊形：初始化的柵格陣列個柵格值為零，以柵格行列為參考坐標(biāo)軸，由多邊形邊界上某點開始（ ）時針?biāo)阉鬟吔缇€，當(dāng)邊界上行時，位于該邊界左側(cè)的具有相同行坐標(biāo)的所有柵格被（ ）a（a為多邊形編號），當(dāng)下行時，該邊界左邊（前進方向看為右側(cè)）所有柵格點（ ）a，邊界搜索完畢則完成了多邊形的轉(zhuǎn)換。多個多邊形：

6、當(dāng)邊界弧段上行時，該弧段與左圖框之間的柵格增加一個值（左多邊形編號減去右多邊形編號）；當(dāng)邊界弧段下行時，該弧段與左圖框之間柵格增加一個值（右多邊形編號減去左多邊形編號）。l 柵格數(shù)據(jù)矢量化的基本步驟：P78 1. 邊界提取采用高通濾波將柵格圖像（ ）或以（ ）標(biāo)識邊界點。2. 邊界線（ ）對每個（ ）由一個結(jié)點向另一個結(jié)點搜索，通常對每個（ ）需沿除了進入方向的其他7個方向搜索下一個邊界點，直到連成邊界弧段。3. ( )生成對于矢量表示的邊界弧段數(shù)據(jù)，判斷其與原圖上各（ ）的空間關(guān)系，以形成完整的拓?fù)浣Y(jié)構(gòu)并建立與（ ）的聯(lián)系。4. 去除多余點及（ ）由于搜索是逐個（ ）進行的，必須去除由此造成

7、的（ ）記錄，以減少（ ）；搜索結(jié)果，曲線由于（ ）的限制可能不夠圓滑，需采用一定的插補算法進行光滑處理。l 距離變換法：P79 距離變換圖是一種柵格圖像，其中每個像元的灰度值等于它到柵格地圖上相鄰物體的（ ）。l 距離變換法基本思想：P79 反復(fù)進行“（ ）”和“將（ ）結(jié)果和（ ）結(jié)果這兩個柵格圖像做（ ）”兩種基本運算。 終止條件是“若對原圖再（ ），將成為（ ）”。l 骨架圖：P79 從距離變換圖中提取具有（ ）的那些像元所組成的圖像。l 多邊形柵格轉(zhuǎn)矢量的雙邊界搜索算法基本步驟：P841. （ ）和（ ）提取2. （ ）搜索與（ ）信息記錄3. （ ）去除第5章l 矢量數(shù)據(jù)的壓縮包括

8、那些內(nèi)容：P90 一是在不擾亂（ ）的前提下，對（ ）進行合理的抽?。欢菍Γ?）重新進行編碼，以減少所需要的（ ）。l 矢量數(shù)據(jù)壓縮的特點：P90 不可逆，數(shù)據(jù)壓縮后，數(shù)據(jù)量變小，數(shù)據(jù)的精度降低。l 曲線壓縮算法的種類：P90-95 間隔去點法、垂距法和偏角法、道格拉斯-普克法、光欄法。l 曲線壓縮算法的比較：P95-96（ ）方法壓縮效果占優(yōu)但工作量大，其次是（ ）、（ ）。（ ）算法嚴(yán)密，運算量少。l 柵格數(shù)據(jù)的壓縮：P98-102 四叉樹編碼在第7章整理，其它了解一下。l 拓?fù)潢P(guān)系自動生成算法的一般過程：P1031. （ ），使整幅圖形中的所有弧段，在除端點處相交外，沒有其他交點，即沒

9、有相交或自相交的弧段。2. （ ），建立結(jié)點、弧段關(guān)系。3. （ ），以左轉(zhuǎn)算法或右轉(zhuǎn)算法跟蹤，生成多邊形，建立多邊形與弧段的拓?fù)潢P(guān)系。4. 建立（ ）與（ ）的拖布關(guān)系。調(diào)整弧段左右多邊形標(biāo)識號。多邊形內(nèi)部標(biāo)識號自動生成。l 左轉(zhuǎn)算法P114-116第6章l 兩個三維矢量的矢量積的模等于兩矢量構(gòu)成的平行四邊形的面積。P120 其余自己看。第7章l 空間索引：P135 依據(jù)空間對象的（ ）和（ ）或空間對象之間的某種空間關(guān)系，按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)。其中包括空間對象的（ ），如對象的標(biāo)識、外接矩形及指向空間對象實體的（ ）。l B樹和B+樹不適應(yīng)空間數(shù)據(jù)的管理。 P135l R樹的定義

10、：P141-142 R樹的結(jié)點由若干個結(jié)構(gòu)為(I,PointerToChild)的單元組成。非葉子結(jié)點中，I為包含其所有子結(jié)點的最小包含矩形（MBR）。在葉子結(jié)點中，I為空間對象的MBR。 PointToChild是個指針，指向（ ）。但在葉子節(jié)點中，是空間對象的標(biāo)識符（identifier，ID）。根據(jù)ID，可以檢索到空間對象的詳細(xì)信息。l R樹的性質(zhì)：P142 設(shè)M為結(jié)點中單元的最大數(shù)目，m（1mM/2）為非根結(jié)點中單元個數(shù)的下限。1. 每個葉子結(jié)點中包含的單元個數(shù)介于（ ）和（ ）之間，除非它同時是根節(jié)點。2. 每個葉子結(jié)點中的單元（I, SpatialObjectID）中，I是包含（

11、）的MBR，SpatialObjectID是該空間對象的ID。3. 每個非葉子結(jié)點的子節(jié)點數(shù)介于（ ）和（ ）之間，除非它是根節(jié)點。4. 每個非葉子結(jié)點的單元(I,PointerToChild)中，I是包含（ ）的MBR，PointerToChild是指向子節(jié)點的指針。通過該指針能訪問到子節(jié)點。5. 根節(jié)點最少有（ ）個子結(jié)點，除非它同時是葉子結(jié)點。6. 所有的葉子結(jié)點都處于樹的同一層上。l R樹的搜索算法：P142-143l R樹的插入算法：P143-144l R樹的刪除算法：P144l 常用線性四叉樹的編碼方法：P151-155 基于（ ）的線性四叉樹編碼、基于（ ）進制的線性四叉樹編碼、

12、基于（ ）進制的線性四叉樹編碼。 其基本思想自己看。第8章l 空間數(shù)據(jù)內(nèi)插的方法：P159 幾何方法、統(tǒng)計方法、空間統(tǒng)計方法、函數(shù)方法、隨機模擬方法、物理模型模擬方法和綜合方法。l 地理學(xué)第一定律：P159 鄰近的區(qū)域比距離遠(yuǎn)的區(qū)域更相似。l 常用的幾何方法：P159 泰森多邊形（最近距離法）和反距離加權(quán)方法。l 常用的統(tǒng)計方法：P160 趨勢面方法和多元回歸方法。l 空間統(tǒng)計方法：P160 以克里金法及其各種變種為代表。l 常用的函數(shù)方法：P160 傅里葉級數(shù)、樣條函數(shù)、雙線性內(nèi)插、立方卷積法。l 常用的隨機模擬方法：P161高斯過程、馬爾科夫過程、蒙特卡羅方法、人工神經(jīng)網(wǎng)絡(luò)法。l 確定性模

13、擬可研究山區(qū)氣候。P161第9章l 不規(guī)則三角網(wǎng)（TIN）的特點：P1721. TIN是由點生成的，每個點具有一個反映高程值的連續(xù)型實數(shù)值。2. TIN是根據(jù)采樣的數(shù)據(jù)點的值計算出來的，表現(xiàn)為一個連續(xù)的三維的表面。3. TIN是一系列非重疊的三角形或面，這些三角形或面完全填充一個區(qū)域。l 泰森多邊形（Voronoi圖）P173-174l Delaunay三角網(wǎng)是一系列相連的但不重疊的三角形的集合，而且這些三角形的外接圓不包含這個面域的其他任何點。其性質(zhì)：P1741. 保證最鄰近的點構(gòu)成三角形，即三角形的邊長之和盡量最小，且每個Delaunay三角形的外接圓不包含面內(nèi)的其他任何點，稱之為Dela

14、unay三角網(wǎng)的空外接圓性質(zhì)，這個特征已經(jīng)作為創(chuàng)建Delaunay三角網(wǎng)的一項判別標(biāo)準(zhǔn)。2. 最大最小角性質(zhì)：在由點集V中所能形成的三角網(wǎng)中，Delaunay三角網(wǎng)中三角形的最小內(nèi)角盡量最大，即三角形盡量接近等邊三角形。第10章l 緩沖區(qū)分析：P185 是地理信息系統(tǒng)中使用非常頻繁的一種空間分析，是對空間特征進行度量的一種重要方法。l 緩沖區(qū)：P185 是根據(jù)空間數(shù)據(jù)庫中的點、線、面地理實體或規(guī)劃目標(biāo)，自動建立其周圍一定寬度范圍的多邊形。l 幾個概念：P185-1871. 軸線的左側(cè)和右側(cè)軸線（ ）方向的左側(cè)為軸線的左側(cè)。2. 多邊形的方向多邊形邊界（ ）方向為正方向。計算面積為正的多邊形稱為

15、正向多邊形。3. 緩沖區(qū)的外側(cè)和內(nèi)側(cè)緩沖區(qū)的外邊界是正向多邊形，（ ）邊界是負(fù)向多邊形。以多邊形的前進方向為準(zhǔn)，多邊形的左側(cè)成為緩沖區(qū)的（ ）側(cè)。4. 軸線(邊界)轉(zhuǎn)折點的凹凸性右手螺旋法則，如圖。PiPi+1Pi-1凹凸 PiPi+1Pi-1凹凸l 圓弧彌合的方法：P187 將（ ）等分，用等長的弦代替（ ），即用均勻步長的直線段逼近圓弧段。l 凸角圓弧法的基本思想：P188 在軸線兩端用半徑為（ ）的圓弧彌合；在軸線的各轉(zhuǎn)折點，首先判斷該點的（ ），在（ ）側(cè)用半徑為緩沖距的圓弧彌合，在（ ）側(cè)用與該點關(guān)聯(lián)的前后兩相鄰線段的偏移量為緩沖距的兩平行線的交點作為（ ）頂點。這樣，在凸側(cè)用圓弧彌

16、合，保證平行線與軸線等寬；在凹側(cè)平行線交點在角平分線上。l 凸角圓弧法的關(guān)鍵算法：P189-190 1. 判斷軸線轉(zhuǎn)折點的凹凸性若Pi-1以最小的角度掃向Pi時為逆時針，則該點左側(cè)為（ ）右側(cè)為（ ）。2. 求與轉(zhuǎn)折點相鄰的兩線段的方向角3. 求與Pi相鄰的兩線段平行線交點4. 確定圓弧彌合的起始點、終止點和方向起始點（終止點）的轉(zhuǎn)折點沿前（后）一線段的法線方向向遠(yuǎn)距離軸線方向平移一個緩沖距得到的點。為保證生成的緩沖區(qū)邊界是順時針方向，軸線左側(cè)圓弧彌合是（ ）方向，右側(cè)是（ ）方向。l 自相交處理的基本思想：P194 求出緩沖區(qū)邊界上的（ ），判斷這些點是入點還是出點，判斷自相交點之間確定的自

17、相交多邊形的性質(zhì)，是（ ）則保留，否則保留面積最大的（ ）為外邊界l 自相交處理的關(guān)鍵算法： P1941. 判斷自相交點是入點還是出點入點是從緩沖區(qū)外側(cè)進入內(nèi)側(cè)的自相交點，出點是從緩沖區(qū)內(nèi)側(cè)到外側(cè)的自相交點。2. 判斷自相交多邊形是島嶼還是重疊區(qū)經(jīng)過處理生成的緩沖區(qū)多邊形是（ ）方向。邊界自相交形成的多邊形中，負(fù)向多邊形是（ ），正向多邊形中，面積最大者為（ ），其他都是重疊區(qū)。l 四弧段結(jié)點的定義：P196 由四條弧段構(gòu)成的節(jié)點。 由四條以上（必須是偶數(shù)）弧段構(gòu)成的結(jié)點稱為非四弧段結(jié)點。l 緩沖區(qū)多邊形的重疊合并的分類：P197 兩個（ ）緩沖區(qū)多邊形的重疊合并、一（ ）一（ ）、兩個（ ）。l 四弧段結(jié)點上的弧段取舍規(guī)則：P197-198 當(dāng)一個弧段的左弧段為來向弧段而右弧段為去向弧段，此弧段為需保留弧段，否則此弧段為需刪除弧段。第11章l 網(wǎng)絡(luò)分析是基于（ ）數(shù)據(jù)的。P201l 最佳路徑是指從始點到終點的最短距離或者（ ）的路線。P201l 最佳布局中心位置是指各中心所覆蓋范圍內(nèi)任一點到中心的距離最近或（ ）。P201l 網(wǎng)絡(luò)流量是指從網(wǎng)絡(luò)上從起點到終點的（ ）。P201l 路徑分析是GIS最基本功能，其核心是對（ ）和（ ）的求解。P203l 幾個名詞P2041. 靜態(tài)求最佳路徑由用戶確定權(quán)值關(guān)系后，即給定每