空间分析技术
中南大学测绘与国土信息工程系
空间分析的基本功能
? 空间查询与量算
? 空间变换
? 缓冲区分析
? 叠加分析
? 路径分析
? 空间插值
? 统计分类分析
主要内容
空间查询 与 量算
空间 变换
缓冲区 分析
叠加 分析
网络 分析
系统空间分析的层次机构
空间数据组织
空间分析的基本方法
应用模型 应用模型 应用模型 应用模型
应用 应用 应用 应用 应用 应用
空间查询与量算
空间查询举例
?如查询满足如下条件的城市,
– 在京沪线的东部
– 距离京沪线不超过 50km
– 城市人口大于 100万
– 城市选择区域是特定的多边形
空间查询的主要方式
基于空间关系的查询
基于空间关系和属性特征的查询
地址匹配查询
基于空间关系的查询主要包括
? 面面查询
? 面线查询
? 面点查询
? 线面查询
? 线线查询
? 线点查询
? 点面查询
? 点线查询
空间量算的内容
几何量算
形状量算
质心量算
距离量算
面状对象形状量算
空间一致性问题：即有孔多边
形与破碎多边形的处理
多边形的边界特征描述
面状对象形状量算 ——空间一致性问题
? 度量空间一致性常用的指标是欧拉函数：用来
计算多边形的破碎程度和孔的数目
? 欧拉数 =（ 孔数 ） - （ 碎片数 -1）
面状对象形状量算 ——边界特征问题
? 如果认为一个标准的圆目标既非紧凑型也非膨胀型
的, 则可定义其形状系数据 r 为
?
? 其中, P为目标物周长, A为目标物面积 。
? 如果
? r〈 1,目标物紧凑型；
? r =1目标物为一标准圆；
? r 〉 1,目标物为膨胀型 。
(面积相等的情况下, 周长比圆大 ）
A
P
r
?
?
?2
质心量测
质心是描述地理对象空间分布的一个重要
指标 。
质心描述的是分布中心而不是绝对几何中
心 。
质心应用
1） 商场选址应该位于具有最佳势能的定位点
处 。
2） 经济的增长极可能发生在高势能地区 。
质心量测通过对其坐标值加权平均求得,
其中, I为离散目标物, Wi为该目标权重,
Xi,Yi为其坐标 。
质心量测公式
?
?
?
i
i
i
ii
G
W
XW
X
?
?
?
i
i
i
ii
G
W
YW
Y
距离量算
? 耗费距离：如旅行所耗费的时间不只与欧氏距
离成正比，还与路况、运输工具有关
距离计算公式
? 非标准欧氏距离的一般公式,
kk
ji
k
ji yyxxd
/1])()[( ????
当 k=2时，就是欧氏距离计算公式；
当 k=1时，得到的距离为曼哈顿距离。
几种距离的图形表示
kkjikji yyxxd /1])()[( ????
jiji yyxxd ????
22 )()(
jijiij YYXXd ????
曼哈吨距离：,
欧氏距离,
非欧氏距离,
缓冲区分析
缓冲区的定义
? 缓冲区（ buffer）是地理空间目标的一种影响
范围或服务范围。从数学的角度看，缓冲区分
析的基本思想是给定一个空间对象或集合，确
定它们的邻域。邻域的大小由邻域半径 R决定。
? 对象 Oi的缓冲区定义为,
– Bi={x,d(x,oi)<=R}
? 对于集合 O={Oi:I =1,2,~,n},其半径 R的缓冲区
是各个对象缓冲区的并,
i
n
i
BB U
1?
?
点、线、多边形的缓冲区示意图
? 点、线、多边形的缓冲区
其它形态的缓冲区
缓冲区计算的基本方法
? 缓冲区计算的基本问题是双线问题，其
基本计算方法包括,
– 角分线法
– 凸角圆弧法
角分线法
缺点：凸角处等距遭到破坏,d=R/sin(B/2)
凸角圆弧法
? 凸角圆弧法是针对角分线法的缺点的补
充判别方案。 方法,
1、在轴线首尾点处，作轴线
的垂线并按双线和缓冲区半
径截出左、右边线起止点；
2、在轴线其它转折点处，首
先判断该点的凸凹性，在凸
侧用圆交弥合，在凹侧则用
前后两邻边平行线的交点生
成对应顶点。
凹凸性的判断方法
矢量代数叉积
S=AB × BC = (XB-XA)(YC-
YB)- (XC-XB)(YB-YA)
若 S>0,ABC呈逆时针方向，
顶点为凸；
若 S<0,ABC呈顺时针方向，
顶点为凹；
若 S=0,ABC三点共线。
缓冲区边线相交情况的处理
? 缓冲区边线自相交
的情况分为两种,
– 岛屿多边形
– 重叠多边形
岛屿多边形与重叠多边形的判断
? 首先定义轴线坐标点序
为其方向，缓冲区双线
分为左右边线，左右边
线的判断方法对称,
– 对于左边线，岛屿自相交
多边形呈逆时针方向，重
叠自相交多边形呈顺时针
方向；
– 对于右边线，岛屿自相交
多边形呈顺时针方向，重
叠自相交多边形呈逆时针
方向。
叠加分析
龚建雅,2001,地理信息系统基础
邬伦，地理信息系统 --原理、方法和应用
概 述
? 叠加分析是将有关主题层组成的数据层
面，进行叠加产生一个新数据层面的操
作，其结果综合了原来两层或多层要素
所具有的属性。叠加分析包括,
– 视觉信息叠加
– 点与多边形叠加
– 线与多边形叠加
– 多边形叠加
– 栅搁图层叠加
视觉信息叠加
? 视觉信息叠加是将不同层 面的信息内容叠加显
示在结果图件或屏幕上，以便研究者判断其相
互空间关系，获得更丰富的空间信息。
– 点状图，线状图和面状图之间的叠加显示；
– 面状图区域边界之间或一个面状图与其他专题区域
边界之间的叠加；
– 遥感影象与专题地图的叠加；
– 专题地图与数字高程模型（ DEM）叠加显示立体专
题图。
点与多边形的叠加
? 点与多边形的叠加可以分析每个多边形
内某类点状要素一共有多少, 或哪些点
落在哪些多边形内 。 这一功能常用于城
市中各种服务设施分布情况的分析 。
线与多边形的叠加
? 线与多边形的叠加是将一个线状要素层
或网络状要素层和多边形层叠合 。 如网
络层为道路网, 可以得到每个多边形内
的道路网密度, 内部的交通流量, 进入,
离开各个多边形的交通量, 相邻多边形
之间的相互交通量 。 如果网络层为河流,
可得到每个多边形内的地表水径流量 。
线与多边形的叠加一般以拓扑结构的矢
量模型比较方便 。
多边形的叠加
? 多边形的叠加是将两个或多个多边形图
层叠加到一起, 合成一个新的多边形层,
其结果是将原来多边形要素分割成新要
素, 新要素综合了原来两层或多层的属
性 。
多边形的叠加举例
多边形叠加分析示意图
? 最小公共单元
多边形叠加可能产生碎屑多边形
多边形叠加的叠加方式
栅格图层叠加
? 地图代数
– 基于常数对数据层面进行的代数运算；
– 基于数学变换对数据层面进行的数学变换（指
数、对数、三角变换等）；
– 多个数据层面的代数运算（加、减、乘、除、
乘方等）和逻辑运算（与、或、非、异或等）；
– 如, M=(0.19T + 0.17D)
? 栅格图层叠加的另一形式是二值逻辑叠加。
基于栅格格式的叠置分析中涉
及的空间逻辑运算
? 逻辑交
? 逻辑并
? 逻辑差的运算
欧氏空间的二值图象图层的定义
? 定义：若 x?A,有 x?B,则称 A为 B的子图
象或 B包含 A,记为 A?B。
? 性质,
– A?A
– A?B,B?C? A?C
– A?B,B?A?A=B
– 如果 A?不, A?B, 称 A为 B的真子图象
A?B。
A与 B的交定义及性质
? 定义,A?B=?x?x?A且 x?B?
? 性质,
– A?A=A
– A?? =?
– （ A?B） ? C= A?（ B ? C）
– 如果 A?B=?，称 A与 B不相交。
A与 B的并
? 定义,
– A?B=?x?x?A或 x?B?
? 性质,
– A?A=A
– A?? =A
– （ A?B） ? C= A?（ B? C）
A与 B的差
? 定义,
– A-B=?x?x?A或 x?B?
? 性质,
– A-A=?
– A-? =A
– （ A-B） - C= A-（ B? C）
布尔逻辑的几个基本定律
? 交换律,A?B=B?A
? A?B=B?A
? 分配律,A?（ B?C） =（ A?B） ?（ A?C）
? A?（ B?C） =（ A?B） ?（ A?C）
? 结合律,（ A?B） ?（ A?C） = A?（ B?C）
? （ A?B） ?（ A?C） =A?（ B?C）
? Demorgan 定律,A-（ B?C） =（ A-B） ?（ A-C）
? A-（ B?C） =（ A-B） ?（ A-C）
叠置分析举例
厚度大于 50cm的土壤与小麦地的交
厚度大于 50cm的土壤与小麦地的并
某县林地与钙地叠合图
不生长在钙地中的森林
网络分析
胡家骥,1987，运筹学，中南工业大学出版社
韩刚, 2002，,北京理工大学硕士学位论文
GIS的网络分析
? GIS的网络分析则是依据网络拓扑关系
（线性实体之间、线性实体与结点之间，
结点与结点之间的连接、连通关系），
通过考察网络元素的空间及属性数据，
以数学理论模型为基础，对网络的性能
特征进行多方面的分析计算。
网络分析的基础及 应用
? 网络分析的基础是图论和运筹学, 它通过研究
网络的状态以及模拟和分析资源在网络上的流
动和分配情况, 对网络结构及其资源等的油画
问题进行研究 。
– 最佳路径, 资源分配, 接点或弧段的游历以及最小
连通树, 最大 （ 小 ） 流等问题 。
? 应用：城市交通规划与管理, 地下管网 （ 如给
排水, 煤气 ） 的管理和维护, 以及电力, 通讯,
有线电视等部门, 其基础数据是有点和线组成
的网状数据 。
网络分析的基本类型 1
? 1,路径分析
? 路径分析是 GIS中的最基本的功能, 其核心是
对最佳路径的求解, 即在指定网络的两结点间
找一条阻抗强度最小的路径 。
? 2,资源分配
? 资源分配也称定位与分配问题, 它包括了目标
选址和将需求按最近 （ 加权距离 ） 原则寻找的
供应中心 （ 资源发散或汇集地 ） 两个问题 。
网络分析的基本类型 2
? 3,连通分析
? 从某一结点或边出发能够到达的全部结点或边,
这一类问题称为连通分量求解 。 另一类连通分
析问题是最少费用连通方案的求解, 即在耗费
最小的情况下使得全部结点相互连通 。
? 4,流分析
? 流：资源在结点间的传输 。
? 流分析：主要是按照某种优化标准 （ 时间最少,
费用最低, 路程最短或运送量最大等 ） 设计资
源的运送方案 。
主要网络分析功能
? 静态求最佳路径：在给顶每条链上的属性后, 求最佳路
径 。
? N条最佳路径分析：确定起点或终点, 求代价最小的 N条
路径, 因为在实践中最佳路径的选择知识理想情况, 由
于种种因素而要选择近似最优路径 。
? 最短路径或最低耗费路径：确定起点, 终点和要经过的
中间点, 中间连县, 求最短路径或最小耗费路径 。
? 动态最佳路径分析：实际网络中权值是随权值关系式变
化的, 可能还会临时出现一些障碍点, 需要动态的计算
最佳路径 。
网络数据结构
? 链：网络中流动的官衔, 如街道, 河流,
水管等, 其状态属性包括阻力和需求 。
? 结点：网络链中的结点, 如港口, 车站,
电站等, 其状态属性包括阻力和需求等 。
特殊结点,
网络结点
? 障碍：禁止网络中链上流动的点；
? 拐点：出现在网络链中的分割结点上, 状态属
性有阻力, 如拐弯的时间和限制 （ 如在 8,00
到 18,00不允许左拐 ）
? 中心：是接受或分配资源的位置, 如水库,
商业中心, 电站等, 其状态属性包括资源容量
（ 如中心到链的最大距离或时间限制 ） ；
? 站点：在路径选择中资源增减的结点, 如库房,
车站等, 其状态属性有资源需求, 如产品数量 。
网络分析的基本原理
? 在网络图中，如若 ?v1,v2,?, vn? 是
从 v1到 vn的最短路径，则 ?v1,v2,?,
vn-1?也必然是从 v1到 vn-1的最短路径。
? 一般方法
最短树枝法
计算最短路径的 Dijkstra算法（标号法）
最短树枝法 -1
1,任取一以 v0为根的外向树, 并计算各点与 v0的距离 li,
2,树枝外的连枝（ vi, vj）长度设为 dij
最短树枝法 -2
2,树枝外的连枝 （ vi, vj） 长度设为 dij。 若对于
所有的连枝 （ vi, vj） 的两端点 vi, vj满足不等
式,
lj ? li + dij
则这棵树便是所求；否则, 若对其中一对连枝
顶点 vi, vj有,lj > li + dij
则去掉以 vj为终点的那条树枝, 代以连枝 （ vi,
vj） ；并修改 vj点的 lj值 。
最短树枝法 -3
? 如此由起点 v0开始，按节点距离从小到大向外
探索修改，直到对树的所有点都进行比较。无
任何变化为止。这样得到的树即为所求。
计算最短路径的 Dijkstra算法（标号法） 1
? 用给节点标号来逐步形成起点到各点的最短
路径及其距离值
1,设起点为 v0,则 l0=0,在 v0点旁标, 表
示起点 v0到 v0的标号；
2,从 v0 出发, 可达 v1,v5 两点
l1= l0+d0,1=0+1=1
l5= l0+d0,2=0+2=2
min?l1,l5 ?= l1=1
在 v1点旁标 ①, 并将 （ v0, v1） 边加粗, 令已
标号的点 v0, v1属点集 S=? v0, v1?；
0
0
计算最短路径的 Dijkstra算法（标号法） -2
? 3,与点集 S相邻的点有 v2, v5,v6,即分
别从 v0 和 v1出发, 可达 v2, v5,v6
? l5= 2 ； l2= l1+d1,2=1+2=3 ； l6=
l1+d1,6=1+2=3； min?l2,l5, l6?= l5=2
? 在 v5点旁标 ②, 将 （ v0, v5） 边加粗, 令
已标号集 S=? v0, v1,v5?；
计算最短路径的 Dijkstra算法（标号法） -3
? 4,与 S=? v0, v1,v5?相邻的点有 v2, v6, v10
l2=3； l6= l1+d16=1+2=3,l10= l5+ d5,10=5;
min?l2,l6, l10?= l2= l6=3;
在 v2, v6点旁标 ③, ③, 将 （ v1, v6） 和
（ v1, v2） 边加粗, 令已标号集 S=? v0, v1,v2，
v5,v6 ?；
? 5,与 S=? v0, v1,v2,v5,v6 ?相邻的点有 v3,
v7, v11,v10
计算最短路径的 Dijkstra算法示意图
Dijkstra算法举例 -有向图和邻接矩阵
Dijkstra算法举例 -计算过程
转向限制对路径规划算法的影响
1,转向限制所带来的时间延迟
占运行时间的 17%~35%
[Nielsen O A.,1997]
2,交通网络的基本特征
[Zilaskopoulos A K.,1997]
3,应当特别强调带转向和禁行限
制的路径规划 [Pallottino S.,
1996]
ROAD A
ROAD B
ROAD C
ROAD D
经典的路径规划算法
? 经典路径规划算法 Dijkstra算法 [Dijkstra E
W.,1959]
– Bellman-Ford条件
If di+lij < dj then [ Parent(j) = i and dj = di + lij ]
? 标记算法：用来标记当前搜索节点状态的策略,
即通过设定已搜索节点为不同状态，以决定
下次对该节点所采取的动作。
转向限制对路径规划的影响
? 无转向限制 ? 带转向限制
涉及关系,
1,(dt)(>,<,=) (ds+l)?
2,使用两个节点，一条弧段
3,使用 Bellman-Ford条件简单
结果,Parent(t) = i
涉及关系,
1.(dt )(>,<,=) (ds+l)?
2.Turn(a,b)?
3.使用三个节点，两条弧段；
4.使用 Bellman-Ford条件困难
结果,Parent(t) = k
难以表达交通网络中转向限制
以往的解决方法
? 扩展子网 [Kirby&Potts,1969 ]
缺点,
(1)由于网络的扩展，需要增加计算时间和计算内存；
(2)需要扩展编码，改变网络的拓扑结构；
(3) 数据的维护与修改工作量也极大。
基于弧段的 Dijkstra算法
GNode PNode Node
i j k
PLink Link
a b
基于节点关系 基于弧段关系
基于弧段的 Dijkstra算法
? 优点,
1.三个节点关系转换为两条弧段关系。
2.能够自然的表达道路间的转向关系。
2.便于应用使用 Bellman-Ford条件。
3.具有较好的效率 O(nlogn)<O(n2)(基于节点
Dijkstra算法 )。
路径规划中的区域限制
? 一般有向图中的路径规划只考虑网络的拓扑性，
忽略其中的空间方向特征，在搜索过程缺乏方
向性，导致全向搜索，产生大量的冗余计算。
[陆峰,1999]。
? 在交通网络上的节点和弧段都具有确定的地理
空间位置和固定的位置关系，因此在给定两点
的路径规划中，实际上就定义了其搜索的大致
范围和方向。
椭圆区域限制
? 根据给定的起点和终点，确定一个椭圆限制区
域。 [Nordbeck & Rystedt,1969]
s,t分别表示路径搜索的起点和终点
优点：对搜索的区域进行了限制，减少了搜索规模。
缺点：引入了二次方的判断运算。
矩形区域限制
? 根据起点和终点确定一个矩形区域限制
[陆峰,1999]。
优点,1.对搜索区域进行限制
2.把二次方的运算转化为一次方运算
缺点,1.相对于椭圆限制，扩大了限制的区域
2.没有考虑两点间的方向性
方向矩形区域限制
? 根据给定起点和终点的位置关系和方向
关系确定带方向的矩形限制区域。
优点,1,对路径规划过程中的搜索进行了限制
2,充分利用了两点之间的方向性
3,对点的判断采用线性关系
实验系统
? 实验数据,5351个交叉路口点,7117条路段，并带有
43575条转向信息。
? 效率比较,
基于节点的 Dijkstra算法,O(n2),约 2分钟 ；
基于弧段的 Dijkstra 算法,O(nlogn),<0.2秒
谢谢
中南大学测绘与国土信息工程系
空间分析的基本功能
? 空间查询与量算
? 空间变换
? 缓冲区分析
? 叠加分析
? 路径分析
? 空间插值
? 统计分类分析
主要内容
空间查询 与 量算
空间 变换
缓冲区 分析
叠加 分析
网络 分析
系统空间分析的层次机构
空间数据组织
空间分析的基本方法
应用模型 应用模型 应用模型 应用模型
应用 应用 应用 应用 应用 应用
空间查询与量算
空间查询举例
?如查询满足如下条件的城市,
– 在京沪线的东部
– 距离京沪线不超过 50km
– 城市人口大于 100万
– 城市选择区域是特定的多边形
空间查询的主要方式
基于空间关系的查询
基于空间关系和属性特征的查询
地址匹配查询
基于空间关系的查询主要包括
? 面面查询
? 面线查询
? 面点查询
? 线面查询
? 线线查询
? 线点查询
? 点面查询
? 点线查询
空间量算的内容
几何量算
形状量算
质心量算
距离量算
面状对象形状量算
空间一致性问题：即有孔多边
形与破碎多边形的处理
多边形的边界特征描述
面状对象形状量算 ——空间一致性问题
? 度量空间一致性常用的指标是欧拉函数：用来
计算多边形的破碎程度和孔的数目
? 欧拉数 =（ 孔数 ） - （ 碎片数 -1）
面状对象形状量算 ——边界特征问题
? 如果认为一个标准的圆目标既非紧凑型也非膨胀型
的, 则可定义其形状系数据 r 为
?
? 其中, P为目标物周长, A为目标物面积 。
? 如果
? r〈 1,目标物紧凑型；
? r =1目标物为一标准圆；
? r 〉 1,目标物为膨胀型 。
(面积相等的情况下, 周长比圆大 ）
A
P
r
?
?
?2
质心量测
质心是描述地理对象空间分布的一个重要
指标 。
质心描述的是分布中心而不是绝对几何中
心 。
质心应用
1） 商场选址应该位于具有最佳势能的定位点
处 。
2） 经济的增长极可能发生在高势能地区 。
质心量测通过对其坐标值加权平均求得,
其中, I为离散目标物, Wi为该目标权重,
Xi,Yi为其坐标 。
质心量测公式
?
?
?
i
i
i
ii
G
W
XW
X
?
?
?
i
i
i
ii
G
W
YW
Y
距离量算
? 耗费距离：如旅行所耗费的时间不只与欧氏距
离成正比，还与路况、运输工具有关
距离计算公式
? 非标准欧氏距离的一般公式,
kk
ji
k
ji yyxxd
/1])()[( ????
当 k=2时，就是欧氏距离计算公式；
当 k=1时，得到的距离为曼哈顿距离。
几种距离的图形表示
kkjikji yyxxd /1])()[( ????
jiji yyxxd ????
22 )()(
jijiij YYXXd ????
曼哈吨距离：,
欧氏距离,
非欧氏距离,
缓冲区分析
缓冲区的定义
? 缓冲区（ buffer）是地理空间目标的一种影响
范围或服务范围。从数学的角度看，缓冲区分
析的基本思想是给定一个空间对象或集合，确
定它们的邻域。邻域的大小由邻域半径 R决定。
? 对象 Oi的缓冲区定义为,
– Bi={x,d(x,oi)<=R}
? 对于集合 O={Oi:I =1,2,~,n},其半径 R的缓冲区
是各个对象缓冲区的并,
i
n
i
BB U
1?
?
点、线、多边形的缓冲区示意图
? 点、线、多边形的缓冲区
其它形态的缓冲区
缓冲区计算的基本方法
? 缓冲区计算的基本问题是双线问题，其
基本计算方法包括,
– 角分线法
– 凸角圆弧法
角分线法
缺点：凸角处等距遭到破坏,d=R/sin(B/2)
凸角圆弧法
? 凸角圆弧法是针对角分线法的缺点的补
充判别方案。 方法,
1、在轴线首尾点处，作轴线
的垂线并按双线和缓冲区半
径截出左、右边线起止点；
2、在轴线其它转折点处，首
先判断该点的凸凹性，在凸
侧用圆交弥合，在凹侧则用
前后两邻边平行线的交点生
成对应顶点。
凹凸性的判断方法
矢量代数叉积
S=AB × BC = (XB-XA)(YC-
YB)- (XC-XB)(YB-YA)
若 S>0,ABC呈逆时针方向，
顶点为凸；
若 S<0,ABC呈顺时针方向，
顶点为凹；
若 S=0,ABC三点共线。
缓冲区边线相交情况的处理
? 缓冲区边线自相交
的情况分为两种,
– 岛屿多边形
– 重叠多边形
岛屿多边形与重叠多边形的判断
? 首先定义轴线坐标点序
为其方向，缓冲区双线
分为左右边线，左右边
线的判断方法对称,
– 对于左边线，岛屿自相交
多边形呈逆时针方向，重
叠自相交多边形呈顺时针
方向；
– 对于右边线，岛屿自相交
多边形呈顺时针方向，重
叠自相交多边形呈逆时针
方向。
叠加分析
龚建雅,2001,地理信息系统基础
邬伦，地理信息系统 --原理、方法和应用
概 述
? 叠加分析是将有关主题层组成的数据层
面，进行叠加产生一个新数据层面的操
作，其结果综合了原来两层或多层要素
所具有的属性。叠加分析包括,
– 视觉信息叠加
– 点与多边形叠加
– 线与多边形叠加
– 多边形叠加
– 栅搁图层叠加
视觉信息叠加
? 视觉信息叠加是将不同层 面的信息内容叠加显
示在结果图件或屏幕上，以便研究者判断其相
互空间关系，获得更丰富的空间信息。
– 点状图，线状图和面状图之间的叠加显示；
– 面状图区域边界之间或一个面状图与其他专题区域
边界之间的叠加；
– 遥感影象与专题地图的叠加；
– 专题地图与数字高程模型（ DEM）叠加显示立体专
题图。
点与多边形的叠加
? 点与多边形的叠加可以分析每个多边形
内某类点状要素一共有多少, 或哪些点
落在哪些多边形内 。 这一功能常用于城
市中各种服务设施分布情况的分析 。
线与多边形的叠加
? 线与多边形的叠加是将一个线状要素层
或网络状要素层和多边形层叠合 。 如网
络层为道路网, 可以得到每个多边形内
的道路网密度, 内部的交通流量, 进入,
离开各个多边形的交通量, 相邻多边形
之间的相互交通量 。 如果网络层为河流,
可得到每个多边形内的地表水径流量 。
线与多边形的叠加一般以拓扑结构的矢
量模型比较方便 。
多边形的叠加
? 多边形的叠加是将两个或多个多边形图
层叠加到一起, 合成一个新的多边形层,
其结果是将原来多边形要素分割成新要
素, 新要素综合了原来两层或多层的属
性 。
多边形的叠加举例
多边形叠加分析示意图
? 最小公共单元
多边形叠加可能产生碎屑多边形
多边形叠加的叠加方式
栅格图层叠加
? 地图代数
– 基于常数对数据层面进行的代数运算；
– 基于数学变换对数据层面进行的数学变换（指
数、对数、三角变换等）；
– 多个数据层面的代数运算（加、减、乘、除、
乘方等）和逻辑运算（与、或、非、异或等）；
– 如, M=(0.19T + 0.17D)
? 栅格图层叠加的另一形式是二值逻辑叠加。
基于栅格格式的叠置分析中涉
及的空间逻辑运算
? 逻辑交
? 逻辑并
? 逻辑差的运算
欧氏空间的二值图象图层的定义
? 定义：若 x?A,有 x?B,则称 A为 B的子图
象或 B包含 A,记为 A?B。
? 性质,
– A?A
– A?B,B?C? A?C
– A?B,B?A?A=B
– 如果 A?不, A?B, 称 A为 B的真子图象
A?B。
A与 B的交定义及性质
? 定义,A?B=?x?x?A且 x?B?
? 性质,
– A?A=A
– A?? =?
– （ A?B） ? C= A?（ B ? C）
– 如果 A?B=?，称 A与 B不相交。
A与 B的并
? 定义,
– A?B=?x?x?A或 x?B?
? 性质,
– A?A=A
– A?? =A
– （ A?B） ? C= A?（ B? C）
A与 B的差
? 定义,
– A-B=?x?x?A或 x?B?
? 性质,
– A-A=?
– A-? =A
– （ A-B） - C= A-（ B? C）
布尔逻辑的几个基本定律
? 交换律,A?B=B?A
? A?B=B?A
? 分配律,A?（ B?C） =（ A?B） ?（ A?C）
? A?（ B?C） =（ A?B） ?（ A?C）
? 结合律,（ A?B） ?（ A?C） = A?（ B?C）
? （ A?B） ?（ A?C） =A?（ B?C）
? Demorgan 定律,A-（ B?C） =（ A-B） ?（ A-C）
? A-（ B?C） =（ A-B） ?（ A-C）
叠置分析举例
厚度大于 50cm的土壤与小麦地的交
厚度大于 50cm的土壤与小麦地的并
某县林地与钙地叠合图
不生长在钙地中的森林
网络分析
胡家骥,1987，运筹学，中南工业大学出版社
韩刚, 2002，,北京理工大学硕士学位论文
GIS的网络分析
? GIS的网络分析则是依据网络拓扑关系
（线性实体之间、线性实体与结点之间，
结点与结点之间的连接、连通关系），
通过考察网络元素的空间及属性数据，
以数学理论模型为基础，对网络的性能
特征进行多方面的分析计算。
网络分析的基础及 应用
? 网络分析的基础是图论和运筹学, 它通过研究
网络的状态以及模拟和分析资源在网络上的流
动和分配情况, 对网络结构及其资源等的油画
问题进行研究 。
– 最佳路径, 资源分配, 接点或弧段的游历以及最小
连通树, 最大 （ 小 ） 流等问题 。
? 应用：城市交通规划与管理, 地下管网 （ 如给
排水, 煤气 ） 的管理和维护, 以及电力, 通讯,
有线电视等部门, 其基础数据是有点和线组成
的网状数据 。
网络分析的基本类型 1
? 1,路径分析
? 路径分析是 GIS中的最基本的功能, 其核心是
对最佳路径的求解, 即在指定网络的两结点间
找一条阻抗强度最小的路径 。
? 2,资源分配
? 资源分配也称定位与分配问题, 它包括了目标
选址和将需求按最近 （ 加权距离 ） 原则寻找的
供应中心 （ 资源发散或汇集地 ） 两个问题 。
网络分析的基本类型 2
? 3,连通分析
? 从某一结点或边出发能够到达的全部结点或边,
这一类问题称为连通分量求解 。 另一类连通分
析问题是最少费用连通方案的求解, 即在耗费
最小的情况下使得全部结点相互连通 。
? 4,流分析
? 流：资源在结点间的传输 。
? 流分析：主要是按照某种优化标准 （ 时间最少,
费用最低, 路程最短或运送量最大等 ） 设计资
源的运送方案 。
主要网络分析功能
? 静态求最佳路径：在给顶每条链上的属性后, 求最佳路
径 。
? N条最佳路径分析：确定起点或终点, 求代价最小的 N条
路径, 因为在实践中最佳路径的选择知识理想情况, 由
于种种因素而要选择近似最优路径 。
? 最短路径或最低耗费路径：确定起点, 终点和要经过的
中间点, 中间连县, 求最短路径或最小耗费路径 。
? 动态最佳路径分析：实际网络中权值是随权值关系式变
化的, 可能还会临时出现一些障碍点, 需要动态的计算
最佳路径 。
网络数据结构
? 链：网络中流动的官衔, 如街道, 河流,
水管等, 其状态属性包括阻力和需求 。
? 结点：网络链中的结点, 如港口, 车站,
电站等, 其状态属性包括阻力和需求等 。
特殊结点,
网络结点
? 障碍：禁止网络中链上流动的点；
? 拐点：出现在网络链中的分割结点上, 状态属
性有阻力, 如拐弯的时间和限制 （ 如在 8,00
到 18,00不允许左拐 ）
? 中心：是接受或分配资源的位置, 如水库,
商业中心, 电站等, 其状态属性包括资源容量
（ 如中心到链的最大距离或时间限制 ） ；
? 站点：在路径选择中资源增减的结点, 如库房,
车站等, 其状态属性有资源需求, 如产品数量 。
网络分析的基本原理
? 在网络图中，如若 ?v1,v2,?, vn? 是
从 v1到 vn的最短路径，则 ?v1,v2,?,
vn-1?也必然是从 v1到 vn-1的最短路径。
? 一般方法
最短树枝法
计算最短路径的 Dijkstra算法（标号法）
最短树枝法 -1
1,任取一以 v0为根的外向树, 并计算各点与 v0的距离 li,
2,树枝外的连枝（ vi, vj）长度设为 dij
最短树枝法 -2
2,树枝外的连枝 （ vi, vj） 长度设为 dij。 若对于
所有的连枝 （ vi, vj） 的两端点 vi, vj满足不等
式,
lj ? li + dij
则这棵树便是所求；否则, 若对其中一对连枝
顶点 vi, vj有,lj > li + dij
则去掉以 vj为终点的那条树枝, 代以连枝 （ vi,
vj） ；并修改 vj点的 lj值 。
最短树枝法 -3
? 如此由起点 v0开始，按节点距离从小到大向外
探索修改，直到对树的所有点都进行比较。无
任何变化为止。这样得到的树即为所求。
计算最短路径的 Dijkstra算法（标号法） 1
? 用给节点标号来逐步形成起点到各点的最短
路径及其距离值
1,设起点为 v0,则 l0=0,在 v0点旁标, 表
示起点 v0到 v0的标号；
2,从 v0 出发, 可达 v1,v5 两点
l1= l0+d0,1=0+1=1
l5= l0+d0,2=0+2=2
min?l1,l5 ?= l1=1
在 v1点旁标 ①, 并将 （ v0, v1） 边加粗, 令已
标号的点 v0, v1属点集 S=? v0, v1?；
0
0
计算最短路径的 Dijkstra算法（标号法） -2
? 3,与点集 S相邻的点有 v2, v5,v6,即分
别从 v0 和 v1出发, 可达 v2, v5,v6
? l5= 2 ； l2= l1+d1,2=1+2=3 ； l6=
l1+d1,6=1+2=3； min?l2,l5, l6?= l5=2
? 在 v5点旁标 ②, 将 （ v0, v5） 边加粗, 令
已标号集 S=? v0, v1,v5?；
计算最短路径的 Dijkstra算法（标号法） -3
? 4,与 S=? v0, v1,v5?相邻的点有 v2, v6, v10
l2=3； l6= l1+d16=1+2=3,l10= l5+ d5,10=5;
min?l2,l6, l10?= l2= l6=3;
在 v2, v6点旁标 ③, ③, 将 （ v1, v6） 和
（ v1, v2） 边加粗, 令已标号集 S=? v0, v1,v2，
v5,v6 ?；
? 5,与 S=? v0, v1,v2,v5,v6 ?相邻的点有 v3,
v7, v11,v10
计算最短路径的 Dijkstra算法示意图
Dijkstra算法举例 -有向图和邻接矩阵
Dijkstra算法举例 -计算过程
转向限制对路径规划算法的影响
1,转向限制所带来的时间延迟
占运行时间的 17%~35%
[Nielsen O A.,1997]
2,交通网络的基本特征
[Zilaskopoulos A K.,1997]
3,应当特别强调带转向和禁行限
制的路径规划 [Pallottino S.,
1996]
ROAD A
ROAD B
ROAD C
ROAD D
经典的路径规划算法
? 经典路径规划算法 Dijkstra算法 [Dijkstra E
W.,1959]
– Bellman-Ford条件
If di+lij < dj then [ Parent(j) = i and dj = di + lij ]
? 标记算法：用来标记当前搜索节点状态的策略,
即通过设定已搜索节点为不同状态，以决定
下次对该节点所采取的动作。
转向限制对路径规划的影响
? 无转向限制 ? 带转向限制
涉及关系,
1,(dt)(>,<,=) (ds+l)?
2,使用两个节点，一条弧段
3,使用 Bellman-Ford条件简单
结果,Parent(t) = i
涉及关系,
1.(dt )(>,<,=) (ds+l)?
2.Turn(a,b)?
3.使用三个节点，两条弧段；
4.使用 Bellman-Ford条件困难
结果,Parent(t) = k
难以表达交通网络中转向限制
以往的解决方法
? 扩展子网 [Kirby&Potts,1969 ]
缺点,
(1)由于网络的扩展，需要增加计算时间和计算内存；
(2)需要扩展编码，改变网络的拓扑结构；
(3) 数据的维护与修改工作量也极大。
基于弧段的 Dijkstra算法
GNode PNode Node
i j k
PLink Link
a b
基于节点关系 基于弧段关系
基于弧段的 Dijkstra算法
? 优点,
1.三个节点关系转换为两条弧段关系。
2.能够自然的表达道路间的转向关系。
2.便于应用使用 Bellman-Ford条件。
3.具有较好的效率 O(nlogn)<O(n2)(基于节点
Dijkstra算法 )。
路径规划中的区域限制
? 一般有向图中的路径规划只考虑网络的拓扑性，
忽略其中的空间方向特征，在搜索过程缺乏方
向性，导致全向搜索，产生大量的冗余计算。
[陆峰,1999]。
? 在交通网络上的节点和弧段都具有确定的地理
空间位置和固定的位置关系，因此在给定两点
的路径规划中，实际上就定义了其搜索的大致
范围和方向。
椭圆区域限制
? 根据给定的起点和终点，确定一个椭圆限制区
域。 [Nordbeck & Rystedt,1969]
s,t分别表示路径搜索的起点和终点
优点：对搜索的区域进行了限制，减少了搜索规模。
缺点：引入了二次方的判断运算。
矩形区域限制
? 根据起点和终点确定一个矩形区域限制
[陆峰,1999]。
优点,1.对搜索区域进行限制
2.把二次方的运算转化为一次方运算
缺点,1.相对于椭圆限制，扩大了限制的区域
2.没有考虑两点间的方向性
方向矩形区域限制
? 根据给定起点和终点的位置关系和方向
关系确定带方向的矩形限制区域。
优点,1,对路径规划过程中的搜索进行了限制
2,充分利用了两点之间的方向性
3,对点的判断采用线性关系
实验系统
? 实验数据,5351个交叉路口点,7117条路段，并带有
43575条转向信息。
? 效率比较,
基于节点的 Dijkstra算法,O(n2),约 2分钟 ；
基于弧段的 Dijkstra 算法,O(nlogn),<0.2秒
谢谢
