2024年考研地理信息系統(tǒng)備考復(fù)習(xí)提綱

2024年考研地理信息系統(tǒng)備考復(fù)習(xí)提綱（經(jīng)典）

1地理信息的概念

定義：是指與研究對象的空間地理分布有關(guān)的信息，它表示地理系統(tǒng)

諸要素的數(shù)量、質(zhì)量、分布特征，相互聯(lián)系和變更規(guī)律的圖、文、聲、

像等的總稱。

特性：

1）地域性：地理信息屬于空間信息，位置的識別與數(shù)據(jù)相聯(lián)系，它

的這種定位特征是通過公共的地理基礎(chǔ)來表白的。這是地理信息區(qū)別

于其它類型信息的最顯著標(biāo)記；

2）多維結(jié)構(gòu)：在二維空間編碼基礎(chǔ)上，實現(xiàn)多專題的第三維信息結(jié)

構(gòu)的組合，為地理系統(tǒng)多檔次的分析和信息的傳輸與篩選提供方便。

3）時序特征：時空的動態(tài)變更引起地理信息的屬性數(shù)據(jù)或空間數(shù)據(jù)

的變更。

可以按時間尺度將地理信息劃分為超短期的（如臺風(fēng)、地震）、

短期的（如江河洪水、秋季低溫）中期的（如土地利用、作物估產(chǎn)）

長期的（如城市化、水土流失）超長期的（如地殼變動、氣候變更）

實時的GIS系統(tǒng)要求能及時采集和更新地理信息，使得地理信息具有

現(xiàn)勢性。

2地理信息系統(tǒng)的概念

GIS是由計算機(jī)硬件、軟件和不同的方法組成的系統(tǒng)，該系統(tǒng)設(shè)計用

來支持空間數(shù)據(jù)的采集、管理、處理、分析、建模和顯示，以便解決

復(fù)雜的規(guī)劃和管理問題。

3GIS的構(gòu)成

應(yīng)用人員，GIS服務(wù)的對象，分為一般用戶和從事建立、維護(hù)、管理

和更新的高級用戶

軟系統(tǒng)件，支持?jǐn)?shù)據(jù)采集、存儲、加工、答復(fù)用戶問題的計算機(jī)程序

系統(tǒng)

硬件系統(tǒng)，各種設(shè)備-物質(zhì)基礎(chǔ)

數(shù)據(jù)，系統(tǒng)分析與處理的對象、構(gòu)成系統(tǒng)的應(yīng)用基礎(chǔ)

應(yīng)用模型，解決某一專門應(yīng)用的應(yīng)用模型，是GIS技術(shù)發(fā)生社會經(jīng)濟(jì)

效益的關(guān)鍵所在

4地理信息的基本功能和應(yīng)用領(lǐng)域

a.數(shù)據(jù)采集與輸入b.數(shù)據(jù)編纂與更新c.數(shù)據(jù)存儲與管理d.數(shù)據(jù)顯

示與輸出

e空間查問與分析el空間查問e2疊加分析e3緩沖區(qū)分析e4網(wǎng)絡(luò)

分析e5地形分析

第二章

I地理實體的三個基本特征

a屬性特征一一用以描述事物或現(xiàn)象的特性，即用來說明“是什么”,

如事物或現(xiàn)象的類別、等級、數(shù)量、名稱等

b空間特征一一用以描述事物或現(xiàn)象的地理位置以及空間相互關(guān)系，

故又稱幾何特征和拓?fù)?/p>

特征，如中國與印度之間邊界界樁的經(jīng)緯度，中國與印度之間的鄰接

關(guān)系

C時間特征一一用以描述事物或現(xiàn)象隨時間的變更，如學(xué)生人數(shù)的逐

年變更。

2地理實體的數(shù)據(jù)類型

屬性數(shù)據(jù)一一描述空間對象的屬性特征的數(shù)據(jù)，也稱非幾何數(shù)據(jù)。即

說明“是什么”，如類型、等級、名稱、狀態(tài)等描述時間特征的數(shù)據(jù)

也可以歸為這一類。

幾何數(shù)據(jù)一一描述空間對象的空間特征的數(shù)據(jù)，也稱位置數(shù)據(jù)、定位

數(shù)據(jù)。即說明“在哪里”，一般用經(jīng)緯度或X、Y坐標(biāo)來表示。

關(guān)系數(shù)據(jù)一一描述空間對象之間的空間關(guān)系的數(shù)據(jù)，一般通過拓?fù)潢P(guān)

系表白。如空間數(shù)據(jù)的相鄰、包含等，主要是指拓?fù)潢P(guān)系。拓?fù)潢P(guān)系

是一種對空間關(guān)系進(jìn)行明確定義的數(shù)學(xué)方法

3空間數(shù)據(jù)結(jié)構(gòu)的概念

是指空間數(shù)據(jù)適合于計算機(jī)存儲、管理、處理的邏輯結(jié)構(gòu)，也就是指

空間數(shù)據(jù)以什么形式在計算機(jī)中存儲和處理?？臻g數(shù)據(jù)結(jié)構(gòu)分為基于

矢量的數(shù)據(jù)結(jié)構(gòu)和基于柵格的數(shù)據(jù)結(jié)構(gòu)兩種基本類型。

3.1矢量、柵格數(shù)據(jù)結(jié)構(gòu)的概念

矢量數(shù)據(jù)結(jié)構(gòu)一一通過記錄空間對象的坐標(biāo)及其空間關(guān)系來表白地

理實體的一種數(shù)據(jù)結(jié)構(gòu)。

A.點實體：記錄點坐標(biāo)和屬性代碼；

B.線實體：記錄兩個或一系列采樣點的坐標(biāo)，并加屬性代碼；

C.面實體：記錄邊界上一系列采樣點的坐標(biāo)，由于多邊形封閉，邊

界為閉合環(huán)，加面域?qū)傩源a。

柵格數(shù)據(jù)結(jié)構(gòu)一一是指將地表區(qū)域劃分為大小均勻緊密相鄰的網(wǎng)格

陣列，每個網(wǎng)格作為一個象元或象素由行、列定義，并包含一個代碼

表示該象素的屬性類型或量值。

A.點實體：由單個像元來表白

B.線實體：由在一定方向上連接成串的相鄰像元的集合來表白。

C.面實體：由聚集在一起的相鄰像元的集合來表白。

4拓?fù)潢P(guān)系的概念，類型

拓?fù)潢P(guān)系：指圖形堅持連續(xù)狀態(tài)下變形，但圖形關(guān)系不變的性質(zhì)。

類型：

最基本拓?fù)潢P(guān)系拓?fù)潢P(guān)聯(lián)：指存在于空間圖形中的不同拓?fù)湓?/p>

之間的關(guān)系

結(jié)點與弧段：如結(jié)b與弧3,2,5,多邊形與弧段：面C與弧4,5,3。

拓?fù)溧徑樱褐复嬖谟诳臻g圖形中的相同拓?fù)湓刂g的關(guān)系。多邊形

之間，結(jié)點之間鄰接矩陣，1——鄰結(jié)；0——不鄰結(jié)

其它拓?fù)潢P(guān)系拓?fù)浒褐复嬖谟诳臻g圖形中的面與其它元素之間

的關(guān)系，如面狀實體包含哪些點、線狀實體

檔次關(guān)系：指存在于空間圖形中的相同拓?fù)湓刂g的等級關(guān)系，如

連云港市各個區(qū)

拓?fù)溥B通：拓?fù)湓刂g的通達(dá)關(guān)系，如點連通度，面連通度

5拓?fù)潢P(guān)系的意義

A.拓?fù)潢P(guān)系能清楚地反映實體之間的邏輯結(jié)構(gòu)關(guān)系。不需要利用坐

標(biāo)或距離就可以確定一個地理實體相對于另一個地理實體的空間位

置關(guān)系，并且這種拓?fù)鋽?shù)據(jù)較之幾何數(shù)據(jù)具有更大的穩(wěn)定性，即它不

隨地圖投影而變更

B.有助于空間要素的查問，利用拓?fù)潢P(guān)系可以解決許多實際問題

C.根據(jù)拓?fù)潢P(guān)系可重建地理實體。

6柵格坐標(biāo)系統(tǒng)確實定

柵格坐標(biāo)系統(tǒng)確實定

由于柵格編碼一般用于區(qū)域性GIS,原點的選擇常具有局部性質(zhì)。但

為了便于區(qū)域的拼接，柵格系統(tǒng)的起始坐標(biāo)應(yīng)與國家基本比例尺地形

圖公里網(wǎng)的交點相一致，并分別采取公里網(wǎng)的縱橫坐標(biāo)軸作為柵格系

統(tǒng)的坐標(biāo)軸。

6.1柵格單元尺寸的原則方法

柵格單元的尺寸

1）原則：應(yīng)能有效地迫近空間對象的分布特征，又減少數(shù)據(jù)的冗

余度。柵格太大，忽略較小圖斑，信息被喪失；柵格太小，會增

加存儲數(shù)據(jù)量

2）方法：用保障最小多邊形的精度標(biāo)準(zhǔn)來確定尺寸經(jīng)驗公式：

〃=%（min1）1/2

〃為柵格單元邊長，Ai為區(qū)域所有多邊形的面積

7柵格單元代碼確實定

柵格代碼（屬性值）確實定

1、中心點法：取位于柵格中心的屬性值為該柵格的屬性值。

2、面積占優(yōu)法：柵格單元屬性值為面積最大者。

3、重要性法：取重要的屬性值為柵格屬性值。

4、長度占優(yōu)法：每個柵格單元的值由該柵格中線段最長的實體的屬

性來確定。

8柵格數(shù)據(jù)結(jié)構(gòu)的特點

?用離散的量化柵格值表示空間對象（通常是規(guī)則

格網(wǎng)）

?位置隱含，屬性明顯

?數(shù)據(jù)結(jié)構(gòu)簡單，易于遙感數(shù)據(jù)結(jié)合，但數(shù)據(jù)量大

?存在幾何和屬性偏差

?面向位置的數(shù)據(jù)結(jié)構(gòu)，難以建立空間對象之間的關(guān)系

?比例尺大小為柵格（像元）的大小與地表相應(yīng)單元的大小之

比。

9矢量與柵格數(shù)據(jù)結(jié)構(gòu)的比擬

優(yōu)點缺點

?便于面向現(xiàn)象（土壤類型等）的數(shù)

據(jù)表

示，不僅能表達(dá)屬性，而且能方?數(shù)瞬音構(gòu)復(fù)雜

矢便的?多邊形疊置分析及模擬比較困

記錄每個目標(biāo)的具體屬性信息難

?數(shù)據(jù)結(jié)構(gòu)緊湊，冗余度低

量?不能做增強(qiáng)處理

?有利于網(wǎng)絡(luò)、檢索分析?軟硬件技術(shù)要求高

?圖形顯示質(zhì)量好，位置精度高

?能完整地描述空間關(guān)系

。數(shù)據(jù)結(jié)構(gòu)簡單，易數(shù)據(jù)交換

現(xiàn)象識別效果不如矢量方法

糊iu?空間分析和地理現(xiàn)象模擬比較容?

易?圖形數(shù)據(jù)量大

有利牙與RS數(shù)據(jù)的匹配應(yīng)用和?投影轉(zhuǎn)換困難

格分析—圖的質(zhì)量*例氏_

輸出方法快速，成本比較低廉

第三章

1GIS數(shù)據(jù)源有哪些

a地圖數(shù)據(jù)存儲介質(zhì)、現(xiàn)勢性、投影轉(zhuǎn)換

b遙感、航空影象和數(shù)據(jù)分辨率、變形規(guī)律、糾正、解譯特征

c實測數(shù)據(jù)

d數(shù)字?jǐn)?shù)據(jù)格式、精度

e統(tǒng)計數(shù)據(jù)、文本數(shù)據(jù)

f多媒體，輔助GIS空間分析和查問

2GIS數(shù)據(jù)質(zhì)量的概念

GIS的數(shù)據(jù)質(zhì)量，是指GIS中空間數(shù)據(jù)（幾何數(shù)據(jù)和屬性數(shù)據(jù)）的可靠

性，通常用空間數(shù)據(jù)的誤差來度量。誤差是指數(shù)據(jù)與真值的偏離。

3地理控制基礎(chǔ)的內(nèi)容

地理控制基礎(chǔ)是地理信息數(shù)據(jù)表示格式與標(biāo)準(zhǔn)的重要組成部分

內(nèi)容：1統(tǒng)一的地圖投影系統(tǒng)2統(tǒng)一的地理格網(wǎng)坐標(biāo)系統(tǒng)（地理參照

系）3統(tǒng)一的地理編碼系統(tǒng)

4GIS中地圖投影的設(shè)計與配置一般原則

a與相應(yīng)比例尺的國家基本圖投影系統(tǒng)一致。

B系統(tǒng)一般只考慮至多采取兩種投影系統(tǒng)，一種應(yīng)用于大比例尺的數(shù)

據(jù)處理與輸出、輸入，另一種服務(wù)于小比例尺。

C所用投影以等角投影為宜。

d所用投影應(yīng)能與網(wǎng)格坐標(biāo)系統(tǒng)相適應(yīng)，即所采取的網(wǎng)格系統(tǒng)在投影

帶中應(yīng)堅持完整。

5連接地理實體與計算機(jī)中表示形式為編碼；標(biāo)識碼是聯(lián)系實體的幾

何信息和屬性信息的關(guān)鍵字；實體幾何數(shù)據(jù)與屬性數(shù)據(jù)的連接紐帶一

一公共標(biāo)識符（關(guān)鍵字）

6代碼的功能

a鑒別代碼代表對象的名稱，是鑒別對象的惟一標(biāo)識。

b分類當(dāng)按對象的屬性分類并分別賦予不同的類別代碼時，代碼又

可作為區(qū)分分類對象類別的標(biāo)識。

c排序當(dāng)按對象發(fā)生的時間、所占的空間或其他方面的順序關(guān)系排

列并分別賦予不同的代碼時，代碼又可作為區(qū)別對象排序的標(biāo)識。

7地理目標(biāo)數(shù)據(jù)分層的目的

是為了便于空間數(shù)據(jù)的

管理一一對所有地理目標(biāo)的管理就簡化為對各數(shù)據(jù)層的管理。

查問一一對地理目標(biāo)數(shù)據(jù)進(jìn)行查問，只需要對某一層地理目標(biāo)數(shù)據(jù)進(jìn)

行查問即可，因而可加快查問速度。

顯示一一不需要分層后的地理目標(biāo)數(shù)據(jù)由于任意選擇需要顯示的圖

層，因而增加了圖形顯示的靈活性

分析一一對不同數(shù)據(jù)層進(jìn)行疊加，可進(jìn)行各種目的的空間分析

8GIS數(shù)據(jù)質(zhì)量的基本內(nèi)容

a位置精度：如數(shù)學(xué)基礎(chǔ)、平面精度、高程精度等，用以描述幾何數(shù)

據(jù)的質(zhì)量。

b屬性精度：如要素分類的正確性、屬性編碼的正確性、注記的正確

性等，用以反映屬性數(shù)據(jù)的質(zhì)量。

c邏輯一致性：如多邊形的閉合精度、結(jié)點匹配精度、拓?fù)潢P(guān)系的正

確性等。

d完備性：如數(shù)據(jù)分類的完備性、實體類型的完備性、屬性數(shù)據(jù)的完

備性、注記的完整性等

e現(xiàn)勢性：如數(shù)據(jù)的采集時間、數(shù)據(jù)的更新時間等

9GIS數(shù)據(jù)質(zhì)量誤差發(fā)生的原因

a空間現(xiàn)象自身存在的不穩(wěn)定性

b空間現(xiàn)象的表白(如由橢球體到平面必定發(fā)生誤差)

c空間數(shù)據(jù)處理中的誤差

d空間數(shù)據(jù)使用中的誤差

10空間數(shù)據(jù)誤差的類型

GIS空間數(shù)據(jù)的誤差可分為源誤差和處理誤差

(1)源誤差，是指數(shù)據(jù)采集和錄入中發(fā)生的誤差，包含:

A遙感數(shù)據(jù)：攝影平臺、傳感器的結(jié)構(gòu)及穩(wěn)定性、分辯率等

b丈量數(shù)據(jù)：人差（讀數(shù)誤差等）、儀差（儀器不完善等）、環(huán)境（干擾

等）

c屬性數(shù)據(jù)：數(shù)據(jù)的錄入、數(shù)據(jù)庫的操作等

dGPS數(shù)據(jù)：信號的精度、接收機(jī)精度、定位方法、處理算法等

e地圖：控制點精度，編繪、清繪、制圖綜合等的精度

f地圖數(shù)字化精度：紙張變形、數(shù)字化儀精度、操作員的技能等

⑵處理誤差，是指GIS對空間數(shù)據(jù)進(jìn)行處理時發(fā)生的誤差，如：

1幾何糾正；2坐標(biāo)變換；3幾何數(shù)據(jù)的編纂；4屬性數(shù)據(jù)的編纂；5

空間分析（如多邊形疊置等）；6圖形化簡（如數(shù)據(jù)壓縮）；7數(shù)據(jù)格式

轉(zhuǎn)換；8計算機(jī)截斷誤差；9空間內(nèi)插；

10矢量柵格數(shù)據(jù)的相互轉(zhuǎn)換。

11空間數(shù)據(jù)標(biāo)準(zhǔn)的概念

是指空間數(shù)據(jù)的名稱、代碼、分類編碼、數(shù)據(jù)類型、精度、單位、格

式等的標(biāo)準(zhǔn)形式。每個地理信息系統(tǒng)都必需具有相應(yīng)的空間數(shù)據(jù)標(biāo)準(zhǔn)

12空間數(shù)據(jù)交換標(biāo)準(zhǔn)的方式

由于空間數(shù)據(jù)模型的不同，空間數(shù)據(jù)的定義、表白和存儲方式也不同，

因而數(shù)據(jù)交換也需要統(tǒng)一的標(biāo)準(zhǔn)。

1外部數(shù)據(jù)交換標(biāo)準(zhǔn)

這類標(biāo)準(zhǔn)通常是ASCII碼文件，用戶可以通過閱讀說明書來直接讀寫

這種外部數(shù)據(jù)格式。GIS的外部數(shù)據(jù)交換格式通常包含：矢量數(shù)據(jù)交

換格式；柵格數(shù)據(jù)交換格式；數(shù)字高程模型交換格式。

特點：自動化水平不高，速度較慢等，但它可解決不同GIS之間的數(shù)

據(jù)轉(zhuǎn)換問題。它仍然是實現(xiàn)數(shù)據(jù)共享的主流方式。

2空間數(shù)據(jù)互操作協(xié)議

制定一套各方都能接受的標(biāo)準(zhǔn)空間數(shù)據(jù)把持函數(shù)，通過調(diào)用這些函數(shù)

以互相操作對方的數(shù)據(jù)。

特點：比外部數(shù)據(jù)交換標(biāo)準(zhǔn)方便，但由于各種軟件存儲和處理空間數(shù)

據(jù)的方式不同，空間數(shù)據(jù)的互操作函數(shù)又不可能很龐大，因此往往不

能解決所有問題。

3空間數(shù)據(jù)共享平臺

服務(wù)器存放空間數(shù)據(jù)，采取客戶機(jī)/服務(wù)器體系結(jié)構(gòu)，各種GIS通過

一個公共的平臺在服務(wù)器存取所有數(shù)據(jù)，以防止數(shù)據(jù)的不一致性。

特點：思路較好，但現(xiàn)有的GIS軟件各有自己的底層，要統(tǒng)一平臺目

前難以實現(xiàn)

4統(tǒng)一數(shù)據(jù)庫接口

在對空間數(shù)據(jù)模型有共同理解的基礎(chǔ)上，各系統(tǒng)開發(fā)專門的雙向轉(zhuǎn)換

程序，將本系統(tǒng)的內(nèi)部數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換成統(tǒng)一數(shù)據(jù)庫的接口。

特點：這種方式的前提，首先要求對現(xiàn)實世界進(jìn)行統(tǒng)一的面向?qū)ο蟮?/p>

數(shù)據(jù)理解，這不易實現(xiàn)的。目前：外部數(shù)據(jù)交換標(biāo)準(zhǔn)仍是實現(xiàn)數(shù)據(jù)共

享的主流方式

13空間元數(shù)據(jù)的定義，主要作用

空間元數(shù)據(jù)（GeospatialMetadata）：地理的數(shù)據(jù)和信息資源的描述

性信息。是通過對地理空間數(shù)據(jù)的內(nèi)容、質(zhì)量、條件和其他特征進(jìn)

行描述與說明，以便人們有效地定位、評價、比擬、獲取和使用與地

理相關(guān)數(shù)據(jù)的數(shù)據(jù)。

作用：（1）確定一套地理空間數(shù)據(jù)的存在性及其位置和其對于某種應(yīng)

用的適宜性，確定空間數(shù)據(jù)的存儲方法、表白方法和使用方法。

2）用來組織和管理空間信息，并挖掘空間信息資源

3）輔助數(shù)據(jù)使用者查問所需空間信息

4）用來建立空間信息的數(shù)據(jù)目錄和數(shù)據(jù)交換中心

5）提供數(shù)據(jù)轉(zhuǎn)換方面的信息

14GIS空間數(shù)據(jù)互操作的含義和其對于GIS的必要性

指異構(gòu)環(huán)境下兩個或兩個以上的實體可以互相通信和協(xié)作，以完成

某一特定任務(wù)，這些實體包含程序、對象、系統(tǒng)運(yùn)行環(huán)境等。

必要性：1)解決基礎(chǔ)數(shù)據(jù)的共享問題的需要2)GIS應(yīng)用趨向多學(xué)科

綜合和集成化3)GIS走向社會化的需要4)是InternetGIS開展的

需要

15OPENGIS的概念

OGIS,也叫開放式地理數(shù)據(jù)交換規(guī)程，它是由開放地理信息系統(tǒng)協(xié)會

(OpenGISConsortium)制定的一系列開放標(biāo)準(zhǔn)和接口。OpenGIS標(biāo)

準(zhǔn)是OGC標(biāo)準(zhǔn)的最高檔次，是利用軟件統(tǒng)一地表示地理數(shù)據(jù)和地理處

理的標(biāo)準(zhǔn)系統(tǒng)。

第四章

1矢量圖形數(shù)據(jù)的編纂(重要)

2空間索引的概念

空間索引一一是指依據(jù)空間對象的位置和形狀或空間對象之間的某

種空間關(guān)系，按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)。它包含空間對象的

概要信息，通過篩選作用，大量與特定空間操作無關(guān)的空間對象被排

除，從而提高空間操作的速度和效率。

3仿射變換

仿射變換的特性：實質(zhì)是兩坐標(biāo)系間的旋轉(zhuǎn)變換。1直線變換后仍為

直線；2平行線變換后仍為平行線；3不同方向上的長度比發(fā)生變更

4投影變換的方法

1解析變換法：找出兩投影間坐標(biāo)變換的解析計算公式的兩種方法：

A.反解變換法先解出原地圖投影點的地理0,幾，對于x,y的解

析關(guān)系式，將其代入新圖的投影公式中求得其坐標(biāo)。B.正解變換法

直接求出兩種投影點的直角坐標(biāo)關(guān)系式。

2數(shù)值變換法原投影點的坐標(biāo)解析式不知道，或不易求出兩投影之

間坐標(biāo)的直接關(guān)系，利用若干同名數(shù)字化點（對同一點在兩種投影中

均已知其坐標(biāo)的點），采取插值法、有限差分法或多項式迫近的方法,

即用數(shù)值變換法來建立兩投影間的變換關(guān)系式。

3數(shù)值解析變換法當(dāng)已知新投影的公式，但不知原投影的公式時,

可先通過數(shù)值變換求出原投影點的地理坐標(biāo)小，入，然后代入新投影

公式中，求出新投影點的坐標(biāo)。

5數(shù)據(jù)壓縮的概念

是指從所取得的數(shù)據(jù)集合中抽出一個子集，使得該子集在規(guī)定的精度

范圍內(nèi)較好地迫近原集合，且盡可能降低其數(shù)據(jù)量的數(shù)據(jù)處理過程。

5.1矢量數(shù)據(jù)壓縮的方法

一、矢量數(shù)據(jù)的壓縮

0道格拉斯---普苣法①加/淞一R弱感感鼠斑

基本步驟：

①對曲線的離散點列P(■叼,無)，PgJ]),一羔W，

品)，設(shè)其

兩個端點為A=P(x“o)和B=￡心啟，并連接線段

AB

②在AB范圍內(nèi)的點列中尋4戈與AB距離最大距離的點

C,判斷C

二點距離—是否小于閾值€,若成立，則刪除AB范圍

內(nèi)的

所有其它點；否則連接AC、CB,去掉線段AB

到AC的距離是否小于J若成立，以線段AC代替5

段AC,

否則連接AD和DC,再用同樣的方法處理AD、DC、

CB,直

句所有的點都滿足都符合上述要求為止。

?垂距法

基本步驟：

每次順序取曲線上的三個點，計算中間點與其它兩點連線的垂線距離d,并與限

差D比較。若d<D,則中間點去掉；若痣。,則中間點保留.然后順序取下三個

點繼續(xù)處理，直到這條線結(jié)束。

?光欄法

基本步喋：定義一個扇形區(qū)域，通過判斷曲線上的點在扇形外還是在扇形內(nèi)，確

定保留還是舍去。設(shè)曲線上的點列為{4},i=l,2,....n,光欄匚

經(jīng)為d,可根據(jù)壓縮量的大小自己定義，則光欄法的實施步驟可描述為

5.2柵格數(shù)據(jù)的壓縮概念、方法（重要）

概念：是指為了刪除冗余數(shù)據(jù)，減少數(shù)據(jù)存儲量，節(jié)省存儲空間，加

快后繼處理速度，對柵格數(shù)據(jù)所做得處理方法。

1游程編碼壓縮方法

是指將原始柵格陣列的行或列中屬性值相同的連續(xù)若干個柵格單元

進(jìn)行合并，并映射成一個游程，以減少數(shù)據(jù)存儲冗余度的編碼壓縮

方法。

每個游程的數(shù)據(jù)結(jié)構(gòu)為（A,P）整數(shù)對。

其中4代表屬性值或?qū)傩灾档闹羔?，P代表連續(xù)相同屬性值的柵格

個數(shù)

（游程編碼壓縮方法是一種無損失的壓縮編碼結(jié)構(gòu)）

行號二元綱摩列

1(9.4),(0.4>

2(9.3),(0.5〉

3(0.1>,(9.2),(0.1>,(7.2>,(0.2>

4C0.4),(7.2>,(0.2>

5(0.4>,(7.4)

6(0.4>,<7.4>

7(0.4),<7.4>

8(0.4),(7.4)

2鏈?zhǔn)骄幋a壓縮

用從某一起點開始沿8個方向前進(jìn)的單位矢量鏈來表示線狀地物或

多邊形的邊界，從而到達(dá)壓縮數(shù)據(jù)量的方法。

建立步驟：1）首先定義一個3義3窗口，對中間柵格的走向的8種可

能進(jìn)行編碼。2）記下地物屬性碼和起點行、列后，進(jìn)行追蹤，得到

矢量鏈。如下列圖所示：

3塊狀編碼壓縮

是游程長度編碼擴(kuò)展到二維的情況，采取方形區(qū)域作為記錄單元，每

個記錄單元包含相鄰的若干柵格，數(shù)據(jù)結(jié)構(gòu)由初始位置（行、列號）

和半徑，再加上記錄單元的代碼組成。數(shù)據(jù)對格式（初始行、歹L半

徑，屬性值）

(1,1,2,9),(1,3,1,9),

12345678

99990000(1,4,1,9),(1,5,2,0),

19990000

99900000■(1,7,2,0),(2,3,1,9),

00

099077002999000(2,4,1,0),(3,1,1,0),

7

00007700309907002,1,9),(3,3,1,9),

0000777740000(3,4,1,0),(3,5,2,7),

500007777

00007777(3,7,2,0),(4,1,1,0),

6

0000777700007777(4,2,1,0),(4,3,1,0),

00007777700007777(4,4,1,0),(5,1,4,0),

800007777(5,5,4,7)

4四叉樹編碼壓縮方法

是指將柵格或圖像沿中央位置等分成四部分，如果某一子區(qū)的所有網(wǎng)

格都具有同樣的屬性值，則這個子區(qū)就不再繼續(xù)分割；否則，就要把

這個子區(qū)再等分成四個區(qū)域，直到每個子區(qū)都含有相同的屬性值為

止，據(jù)此再進(jìn)行編碼的方法。

一種可變分率的非均勻網(wǎng)格系統(tǒng)，是最有效的柵格數(shù)據(jù)壓縮編碼方法

之一。

1、肺思息

篇以然冠朧腔問畫（做棚鬻補(bǔ)上）按齡轆斷觸分

■相嘯性蹦髀-琳分,帔獺二、柵格數(shù)據(jù)的壓縮

麟翩-膽般馳闞一畋林。四叉樹編碼壓縮方法

3、四叉樹建立的方法——自上而下的方法

對一個由QKQ（n=2xk1k>1）的柵格方陣組成的區(qū)域P,

它的四個子象限（&,%Pc，PR分別為：

P,?fPC,414七十".

P.HW,n.1…an'

P^{Ki,n.；+l4（n,子+1QG）1..

22n.i<?|?.?xi*

再下I層的子象限介別為，"

p“sn,-i-?*

其中4、b、c.西別表示西北、東北、西南、東南四個子象限.

根據(jù)表達(dá)式可求得任一層的某個子象限在全區(qū)的行列位置，并對這個位置范圍內(nèi)的網(wǎng)格值進(jìn)行檢測.

若數(shù)值單調(diào)，就不再細(xì)分，由此可以完成整個區(qū)域四叉樹的建立.

但該法分割需要大量的運(yùn)算，因為大量數(shù)據(jù)需要重復(fù)檢查才能確定劃分.當(dāng)QKQ的矩陣比較大，且區(qū)

域內(nèi)容要素又比較復(fù)雜時，建立這種四叉樹的速度比較慢.

0四叉確碼壓縮方法

。四叉樹端掘縮方法

3、四叉樹建立的方法一自下而上的方法

對柵格數(shù)據(jù)按如下的順序進(jìn)行檢測.如果每相鄰四個網(wǎng)格值相同則進(jìn)行合并，逐次往上

2、四叉樹㈱形標(biāo)：遞歸合并，直到符合四叉相的原則為止.這種方法重復(fù)計算較少，運(yùn)算速度較快.

用一啦糠魂慚源分舞臬,

根:整個困

高般分曦，幾次分割

It：磷酚酬塊

敗:還黝割的塊

每個樹叉均箱個分叉網(wǎng)四叉機(jī)

根軸

NWNESESW

°一幅點\%

占<S

,一花點面而向x堿?

4、四叉樹編碼方式——常規(guī)四叉樹

四叉樹編四壓縮方法

常規(guī)四又樹除了記錄葉結(jié)點之外，還要記錄中間結(jié)點。?

結(jié)點之間借助指針聯(lián)系，每個結(jié)點需要用六個量表達(dá)：7、把一幅加X印的圖像壓縮成線性四叉樹的遺呈

四個葉結(jié)點指針，一個父結(jié)點指計和一個結(jié)點的屬性值.

這些指針不僅增加了數(shù)據(jù)貯存量，而且增加了操作的復(fù)雜性。1）按Morton碼把圖象讀入一維數(shù)組。

常規(guī)四叉樹主要在數(shù)據(jù)索引和圖幅索引等方面應(yīng)用。2）相鄰的四個象元比較，一致的合并，只記錄第一個象元的Morton碼,

循環(huán)比較所形成的大塊，相同的再合并，直到不能合并為止。

3）進(jìn)一步用游程長度編碼壓縮。壓縮時只記錄第一個象元的Morton碼.

4、四叉樹編碼方式一線性四叉樹

用地址碼〔定位碼、Morton碼）記錄口梯點的位置、深度（幾次分割）和屬性。

優(yōu)點：0四叉樹編碼壓編方法

1）存貯量小，只對口移吉點編碼，節(jié)省了大量中間結(jié)點的存儲，地址碼隱含著

結(jié)點的分割路徑和分割次數(shù)。7、相一幅/X》的圖像壓縮成線性四叉樹的進(jìn)士

2）線性四叉樹可直接尋址，通過其坐標(biāo)值直接計算其Morton碼，而不用建立AAAA

四叉樹。014

3）定位碼容易存儲和執(zhí)行實現(xiàn)集合相加等組合操作。ABBB

右酬隨腿過程為：2367

AABB

1）按Morto硼入一峨且891213

AABB

Morton碼：0123456789101112131415

10111415

象元值：AAABABBBAAAABBBB

2）四相鄰象元合并，只記錄第一個象元的Morton碼

01234567812

AAABAABBAB

3）由于不跳一步合并,則用流程卡像編碼壓縮

0346812

ABABAB

3）依次檢查每四個相鄰的對應(yīng)的屬性值，相同合并（不同碼位去掉），不

同則存盤，直到?jīng)]有能夠合并的子塊為止。

?四叉胸碼壓縮方法

6、~H2制的Morton碼---MD

四進(jìn)制Morton碼直觀上切合四叉樹分割，

但許多語言不支持四進(jìn)制變量，需用十

進(jìn)制表示Morton碼.

一種按位操作的方法：

設(shè)四叉樹中十進(jìn)制表示的行號,列號在計算機(jī)內(nèi)部的二進(jìn)制數(shù)分別為：

口=金…刀1），一場）

則加方=@加*di蒞茨5），將轉(zhuǎn)換為十進(jìn)制即可

如行為2、列為3的柵格的Mp步堪：

（1）行、列號為二進(jìn)制四=10，=11

⑵，行J列交叉1101=13

⑶再化為十淵h

實質(zhì)上是按左上、右上、左下、右下的咂序，從零開始對每個柵格進(jìn)行自然編碼。

5空間數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換

5.1點對象的柵格化

矢量熱掇是以蚯睚標(biāo)祿達(dá)的，而柵格嬲幃和耦象睚標(biāo)，Wil?掃描法

的雕元肺列號.矢鼬臃雕需輔矢例標(biāo)鞋為行列號

如下圖，按掃描線的順序，計算多邊形與掃描線的相交區(qū)間，再用相應(yīng)的屬性值填充這

些區(qū)間，即完成了多邊形的柵格化。這種算法的缺點是計算量較大。

?邊填充法

其基本思想是：對于卷一條掃描線和每條多邊形邊上的交點，將該掃描線上交點右方

的所有象索取原屬性值之補(bǔ)。對多邊形的每條邊作此處理，多邊形的方向任意。下圖是

一個簡單的例子.

本算法的優(yōu)點是算法簡單，缺點是對于復(fù)雜圖形，每一象素可能被訪問名次,增加了運(yùn)

算量。

蚪個內(nèi)部解薪,向勒個方向給喇微利崎姒的靛舌榜域歌

上嫄是，不作肺現(xiàn),上當(dāng)怖踹薪,上曲嘛,無府殿匕

膜靴較麻，而且可能赧颼礴㈱鼾能融（如右下勖毗翻跳不

般胎所會修出基

6空間數(shù)據(jù)插值的概念

空間數(shù)據(jù)插值，是指通過已知點或分區(qū)的數(shù)據(jù)，推求任意點或分區(qū)數(shù)

據(jù)的方法

7泰森多邊形

泰森多邊形法的基本原理是，未知點的最佳值由最鄰近的觀測值發(fā)

生。

(1)每個泰森多邊形內(nèi)僅含有一個控制點數(shù)據(jù)

(2)泰森多邊形內(nèi)的點到相應(yīng)控制點的距離最近

(3)位于泰森多邊形邊上的點到其兩邊控制點的距離相等

(4)在判斷一個控制點與其它哪些控制點相鄰時，可直接根據(jù)泰森

多邊形得出結(jié)論，即若泰森多邊形是n多邊形，則n個離散點相鄰。

8趨勢面分析的基本特點？？？？

1插值結(jié)果是一個平滑外表(線)，這個外表(線)是由采樣點值擬合的

多項式數(shù)學(xué)方程生成的。

2其起伏變更平緩，代表研究區(qū)域范圍內(nèi)外表逐漸變更的總體趨勢，

很少能與實際的已知樣點完全重合，屬非精確插值方法。

3該插值方法受生成的預(yù)測外表容易受那些離群點(極高或低樣點)

的影響，而且多項式越復(fù)雜，其物理意義就越難描述。

第五章

1空間數(shù)據(jù)庫的概念

以特定的信息結(jié)構(gòu)和數(shù)據(jù)模型表白、存儲和管理從地理空間中獲取的

某類空間信息，以滿足不同用戶對空間信息需求的數(shù)據(jù)庫。

2空間數(shù)據(jù)庫的特征

A空間數(shù)據(jù)庫具有一般數(shù)據(jù)庫所共有的特征

1數(shù)據(jù)集中控制在文件管理方法中，文件是分散的，文件之間一般

是沒有聯(lián)系的，不能依照統(tǒng)一的方法來控制、維護(hù)和管理。而數(shù)據(jù)庫

則很好地克服了這一缺點，可以集中控制、維護(hù)和管理有關(guān)數(shù)據(jù)。

2數(shù)據(jù)獨立數(shù)據(jù)庫中的數(shù)據(jù)獨立于應(yīng)用程序，包含數(shù)據(jù)的物理獨

立性和邏輯獨立性。這給數(shù)據(jù)庫的使用、調(diào)整、優(yōu)化和進(jìn)一步擴(kuò)充提

供了方便，提高了數(shù)據(jù)庫應(yīng)用系統(tǒng)的穩(wěn)定性。

3數(shù)據(jù)共享數(shù)據(jù)庫中的數(shù)據(jù)可以供多個用戶使用，每個用戶只與

數(shù)據(jù)庫中的一部分?jǐn)?shù)據(jù)發(fā)生聯(lián)系。用戶數(shù)據(jù)可以重疊，用戶可以同時

存取數(shù)據(jù)而互不影響，大大提高了數(shù)據(jù)庫的使用效率。

4較小的數(shù)據(jù)冗余數(shù)據(jù)庫中的數(shù)據(jù)不是面向應(yīng)用，而是面向系統(tǒng),

數(shù)據(jù)是依照一定的數(shù)據(jù)模型組織、描述和存儲，并進(jìn)行集中管理，具

有較小的冗余度，也提高了數(shù)據(jù)的一致性。

5統(tǒng)一的數(shù)據(jù)維護(hù)功能多用戶共享數(shù)據(jù)資源時，嚴(yán)格檢查用戶使用

數(shù)據(jù)，規(guī)定用戶的訪問和存取權(quán)限，確保數(shù)據(jù)的保險性、一致性和并

發(fā)控制。

B空間數(shù)據(jù)庫有別于一般數(shù)據(jù)庫的特征

(1)空間特征：空間特征是空間數(shù)據(jù)庫的最主要特征，它描述的是

空間物體的位置、形態(tài)和空間關(guān)系

(2)抽象特征：空間數(shù)據(jù)描述的是真實世界所具有的綜合特征，非

常復(fù)雜，必需經(jīng)過抽象處理。在不同的抽象中，同一地物可能會有不

同的語義特征。

(3)空間關(guān)系特征：空間數(shù)據(jù)除了空間坐標(biāo)隱含了空間分布關(guān)系外,

空間數(shù)據(jù)中也記錄了拓?fù)鋽?shù)據(jù)結(jié)構(gòu)表白的多種空間關(guān)系。這種拓?fù)鋽?shù)

據(jù)結(jié)構(gòu)一方面方便了空間數(shù)據(jù)的查問和空間分析，另一方面也給空間

數(shù)據(jù)的一致性和完整性維護(hù)增加了復(fù)雜水平。

(4)多尺度與多態(tài)性：不同觀察尺度具有不同的比例尺和精度，同

一地物在不同情況下會有形態(tài)差別。

(5)非結(jié)構(gòu)化：在關(guān)系數(shù)據(jù)庫管理系統(tǒng)中，數(shù)據(jù)記錄是結(jié)構(gòu)化的，

記錄是定長的，數(shù)據(jù)項不容許有嵌套?？臻g數(shù)據(jù)不滿足結(jié)構(gòu)化要求，

記錄數(shù)據(jù)項是變長的，不滿足關(guān)系數(shù)據(jù)模型的范式要求。

(6)分類編碼特征：在GIS數(shù)據(jù)庫系統(tǒng)中，每一個空間對象都有一

個標(biāo)識碼和分類碼。

(7)海量數(shù)據(jù)特征：空間數(shù)據(jù)量是巨大的，通常稱為海量數(shù)據(jù)，其

數(shù)據(jù)量比一般通用數(shù)據(jù)庫要大得多。一個城市的數(shù)據(jù)量要到達(dá)TB級。

3GIS空間數(shù)據(jù)管理模式

(1)基于文件管理的方式

(2)文件與關(guān)系數(shù)據(jù)庫混合管理系統(tǒng)

(3)全關(guān)系型空間數(shù)據(jù)庫管理系統(tǒng)

(4)對象一關(guān)系數(shù)據(jù)庫管理系統(tǒng)

(5)面向?qū)ο驡IS數(shù)據(jù)庫管理系統(tǒng)

4Gls數(shù)據(jù)模型的概念，三要素，建立的目的

數(shù)據(jù)模型是指數(shù)據(jù)庫系統(tǒng)中關(guān)于數(shù)據(jù)內(nèi)容和數(shù)據(jù)間聯(lián)系的邏輯組織

形式，它以抽象的形式描述和反映地理實體構(gòu)成及其相互關(guān)系。

三要素：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和數(shù)據(jù)的約束條件

建立數(shù)據(jù)模型的目的是：用最佳的方式表白實體對象及其相互關(guān)系，

并能以最佳的方式為用戶提供訪問數(shù)據(jù)庫的邏輯接口

5檔次、網(wǎng)狀、關(guān)系數(shù)據(jù)模型的優(yōu)缺點(以下為關(guān)系數(shù)據(jù)模型)

優(yōu)點：結(jié)構(gòu)簡單靈活；容易維護(hù)和理解，數(shù)據(jù)的修改和更新方便。

一般DBMS管理屬性數(shù)據(jù)方便可靠，管理圖形數(shù)據(jù)有局限：

1無法用遞歸和嵌套的方式來描述復(fù)雜的檔次和網(wǎng)狀結(jié)構(gòu)，模擬和操

作復(fù)雜地理對象的能力較弱;

1對復(fù)雜結(jié)構(gòu)地理對象的描述，需對實體進(jìn)行不自然的分解，導(dǎo)致存

儲模式、查問途徑及操作等方面均顯得語義不甚合理；

3概念模式和存儲模式的相互獨立性，導(dǎo)致關(guān)系之間的聯(lián)系需要執(zhí)行

聯(lián)接操作，系統(tǒng)開銷較大，運(yùn)行效率不夠高；

4難于存儲和維護(hù)變長的空間數(shù)據(jù)及其拓?fù)潢P(guān)系；

5不能支持GIS需要的一些復(fù)雜圖形功能及包含、疊加等操作。

6數(shù)據(jù)庫結(jié)構(gòu)設(shè)計

數(shù)據(jù)庫設(shè)計，就是把現(xiàn)實世界中一定范圍內(nèi)存在著的應(yīng)用處理和數(shù)據(jù)

抽象成一個數(shù)據(jù)庫的具體結(jié)構(gòu)的過程。

空間數(shù)據(jù)庫的設(shè)計，是指在現(xiàn)在數(shù)據(jù)庫管理系統(tǒng)的基礎(chǔ)上建立空間數(shù)

據(jù)庫的整個過程。主要包含需求分析、結(jié)構(gòu)設(shè)計和數(shù)據(jù)層設(shè)計三部分。

7空間數(shù)據(jù)庫的維護(hù)（重組織，重構(gòu)造的概念）

1、空間數(shù)據(jù)庫的重組織指在不改變空間數(shù)據(jù)庫原來的邏輯結(jié)構(gòu)和

物理結(jié)構(gòu)的前提下，改變數(shù)據(jù)的存儲位置，將數(shù)據(jù)予以重新組織和存

放。

2、空間數(shù)據(jù)庫的重構(gòu)造指局部改變空間數(shù)據(jù)庫的邏輯結(jié)構(gòu)和物理

結(jié)構(gòu)。數(shù)據(jù)庫重構(gòu)通過改寫其概念模式（邏輯模式）的內(nèi)模式（存儲模

式）進(jìn)行。

第六章

1空間分析的定義

是集空問數(shù)據(jù)分析和空間模擬于一體的技術(shù)，通過地理計算和空間表

白挖掘潛在空間信息，以解決實際問題的過程。

2空間查問的定義

是指基于給定的屬性和空間約束條件從地理數(shù)據(jù)庫中查找指定地理

對象及其屬性的過程

3數(shù)字地面模型（DTM）和高程模型（DEM）o

數(shù)字地面模型：是指地表形態(tài)屬性信息的數(shù)字表白，是帶有空間位置

特征和地形屬性特征的數(shù)字描述。

數(shù)字高程模型：是一定區(qū)域范圍內(nèi)地面高度連續(xù)變更的數(shù)字化表示方

法，通常是指依照一定的格網(wǎng)間隔采集地面高程所建立的規(guī)則格網(wǎng)高

程模型。

4TIN的概念、特點

TIN：利用區(qū)域有限個點集將區(qū)域劃分為互不交叉、互不重疊且相連

的三角面網(wǎng)絡(luò)來模擬地形外表的數(shù)據(jù)模型。

特點：①TIN模型具有可變分辨率；

②因能顧及各種地形特征點、線，故能以較少的采樣點高精度的迫

近復(fù)雜的地形外表

③TIN模型可減少規(guī)則格網(wǎng)法帶來的數(shù)據(jù)冗余，同時在計算坡度等

效率方面優(yōu)于純粹基于等高線的方法；

④TIN數(shù)據(jù)結(jié)構(gòu)、存儲管理與把持較為復(fù)雜，數(shù)據(jù)共享不便，大規(guī)

模DEM生產(chǎn)管理較少采取，一般用于大比例尺地形測圖

5空間疊置分析、緩沖區(qū)分析、網(wǎng)絡(luò)分析的概念

空間疊置分析又稱疊加分析，是指在統(tǒng)一的空間參照系統(tǒng)條件下，將

同一地區(qū)的兩組或兩組以上的圖層要素進(jìn)行疊置，發(fā)生新的數(shù)據(jù)層的

分析方法。

緩沖區(qū)分析是指根據(jù)分析對象的點、線、面實體，自動建立它們周圍

一定距離的帶狀區(qū)域，用以識別這些實體對鄰近對象的輻射范圍或影

響度，以便為某項分析或決策提供依據(jù)。

GIS的網(wǎng)絡(luò)分析是通過研究網(wǎng)絡(luò)的狀態(tài)以及模擬和分析資源在網(wǎng)絡(luò)上

的流動和分配情況，對網(wǎng)絡(luò)結(jié)構(gòu)及其資源的優(yōu)化問題進(jìn)行研究的一種

空間分析方法。（網(wǎng)絡(luò)分析的基礎(chǔ)是圖論和運(yùn)籌學(xué)）

6狄克拉斯算法（重要）

三、網(wǎng)絡(luò)分析

1.最短路徑問題

?最短路徑的算法一Q曲蛔漠法

1959年由&/座域提出的標(biāo)號法被認(rèn)為是目前公認(rèn)的最好的求解算法

該算法的優(yōu)點是：

?？梢郧蟪銎瘘c到終點的最短路徑及其長度,而且可以求出起點到其它任何一個

頂點的最短路徑及其長度.

?不但適用于求解有向圖上的最短路徑問題，而且同樣也適用于求解無向圖上的

最短路徑問題。

基本思想：

首先從起點匕開始,給每個頂點標(biāo)一個數(shù)(稱為標(biāo)號)，

T標(biāo)號—表示從起點匕到該點的最短路徑的上界，稱為臨時標(biāo)號：

尸標(biāo)號——表示從匕到錢點的最短路經(jīng)，稱為固定標(biāo)號.

已經(jīng)得到產(chǎn)標(biāo)號的頂點不再改變，凡是沒有標(biāo)上尸標(biāo)號的頂點,標(biāo)上T標(biāo)號.

算法的每一步就是把某一頂點的T標(biāo)號改為變?yōu)槭瑯?biāo)號.那么,最多經(jīng)過上1

步，就可以求得從起點匕,到終點公的最短路徑.

?距離矩陣的計算

為了求出最短路徑,需先計算兩點間的距離，

并形成距離矩陣.若兩點間沒有路，則距離為8

?最短路徑搜索的依據(jù)

最短路徑搜索的基本依據(jù)是，若從點$到點E有一條最短路徑,

則該路徑上的任何點到S的距離都是最短的.

為了進(jìn)行最短路徑搜索.令以屠，匕)表示點匕到后的距離.ABCDE

次均表示匕量起始點s的最短距離.A,040012

Bco07oo4

?最短路徑搜索的步驟

Ccc0002oo

(1)對起始點S作標(biāo)記，且對所有頂點令打孱)=0,乳掩=8.

D300902

(2)對所有未作標(biāo)記的點按以下公式計算距離，

E51650

乳妗=min{/切,以衛(wèi),6+次為}

其中匕是己確定作標(biāo)記的點。取具有最小值的翼均，并對屏作標(biāo)記,令演屏)=/6.

若最小值的Kg)為8,則說明s到所有未標(biāo)記的點都沒有路，算法終止：否則繼續(xù).

(3)如果￡等于E「則已找到S到￡的最短路徑，算法終止；否則轉(zhuǎn)(2).

需搜索Ai燈的最短路徑

。對n作尸標(biāo)記，E、)=o,其它結(jié)點作批號，式外=+8,y為夙

?因為-4已經(jīng)得到尸標(biāo)號,而與上關(guān)聯(lián)弧段的結(jié)點有夕、E、D.

且它們都是r標(biāo)號，所以要修改它們的r標(biāo)號

武瑪=城以公⑤旗44或乩朗=min[+8,0+4]=4

式功=順[匹配B4)+或乩為]=min[+8,02]=2

式Q)=煥[/外我4)+或乩則=min[+,0+1]=1

在所有的r標(biāo)號中.世必=1最小，于是令/0=1

?因為。已經(jīng)得到尸標(biāo)號,而與A關(guān)聯(lián)弧段的結(jié)點有E、C,

且它們都是r標(biāo)號，所以要修改它們的7標(biāo)號

式為=