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

1、第1章l 算法設(shè)計(jì)的原則：P1（）、（）、（）l 算法的復(fù)雜性：P2（）復(fù)雜性和（）復(fù)雜性l 時(shí)間復(fù)雜性定義：P2利用某算法處理一個(gè)問(wèn)題規(guī)模n的輸入所需要的時(shí)間l 空間復(fù)雜性定義：P8算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間的大小第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 順逆時(shí)針關(guān)系：P22 P×Q>0，P在Q的（ ）方向，反之，P在Q的（ ）方向，若為0，則（ ），可能（ ）也可能（ ）l 折線段的拐向判斷：P23 若大于0，則拐向（ ），反之拐向（ ），等于零，三點(diǎn)共線。l 快速排斥試驗(yàn)P23-24圖l

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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