第2章 GIS算法的几何基础.ppt

第二章 GIS算法的几何基础 2.1 维数扩展的9交集模型 2.2 矢量的概念 2.3 折线段的拐向判断 2.4 判断点是否在线段上 2.5 判断两线段是否相交 2.6 判断线段和直线是否相交 2.7 判断矩形是否包含点 2.8 判断线段、折线、多边形是否在矩形中 2.9 判断矩形是否在矩形中 2.10 判断圆是否在矩形中 2.11 判断点是否在多边形内 2.12 判断线段是否在多边形内 第二章 GIS算法的几何基础 2.13 判断折线是否在多边形内 2.14 判断多边形是否在多边形内 2.15 判断矩形是否在多边形内 2.16 判断圆是否在多边形内?? 2.17 判断点是否在圆内?? 2.18 判断线段、折线、矩形、多边形是否在圆内 2.19 判断圆是否在圆内 2.20 计算两条共线的线段的交点 2.21 计算线段或直线与线段的交点 2.22 求线段或直线与圆的交点 2.1 维数扩展的9交集模型 关系运算——检验两个几何对象的特定的拓扑空间关系的逻辑方法 拓扑空间关系基本的比较方法——成对比较两个几何对象的内部、边界和外部的交集。（空间关系分类） 4交集模型 9交集模型 维数拓展的9交集模型 2.1 维数扩展的9交集模型 9交集模型介绍 设有现实世界中的两个简单实体A、B,B(A)、B(B)表示A、 B的边界,I(A)、I(B)表示A、B的内部,E(A)、E(B)表示A、B外部。Egenhofer(1993)构造出一个由边界、内部、外部的点集组成的9—交空间关系模型(9IM)如下: （1） 维数扩展的9交集模型 9交模型一共可以表达512种可能的空间关系，但是在实际上，有些关系并不存在。 相对于4交集模型，通过引进点集的余（外部），9-交空间关系模型增强了面/线、线/线空间关系的唯一性。但它仅仅用“空”与“非空”来区分两个目标的边界、内部、余，对面/面、点/点、点/线、点/面的空间关系描述并无多大改进。为此，该方法仍有一定的局限性。 在地理信息系统中，数据可以划分为几何数据与属性数据两大类型。由于几何数据具有可量测性，为此地理信息系统所涉及的客观世界是一个度量空间，而且每个度量空间又是一个拓扑空间。（关系确定，不能模糊表示） 2.1 维数扩展的9交集模型 运用维数扩展法,将9IM进行扩展,利用点、线、面的边 界、内部、外部之间的交集的维数来作为空间关系描述的框架。 对于几何实体的边界,它是比其更低一维的几何实体的集合。为此, 点的边界为空集;线的边界为线的两个端点,当线为闭曲线时,线的 边界为空;面的边界由构成面的所有线构成。若设P为一个集合,定 义集合的求维函数DIM如下: 2.1 维数扩展的9交集模型 利用维数扩展法,式(1)可扩展为 （2） 2.1 维数扩展的9交集模型 根据DE-9IM,对于集合拓扑空间X,当需要进行关系判别时,可对矩阵的9元取值进行分析、比较。令C为各单元交的集合,其取值P可能为｛T,F,*,0,1,2｝。各个取值的具体含义为： 1)P=T DIM(C)∈｛0,1,2｝,即交集C包含有点、线、面; 2)P=F DIM(C)=-1,即交集C为空; 3)P=* DIM(C)∈｛-1,0,1,2｝,即两目标交集既有点、线、面,又含有某些部分的交为空的情形,该情况在关系判别时,一般不予以考虑; 4)P=0 DIM(C)=0; 5)P=1 DIM(C)=1; 6)P=2 DIM(C)=2。 2.1 维数扩展的9交集模型 式(2)中各元素通过取值｛T,F,*,0,1,2｝,可产生的 情形为 ,关系非常复杂,通过对大量的空间关 系进行归纳和分类,得出5种基本的空间关系:相离关系(Disjoint)、相接关系(Touch)、相交关系(Cross)、真包含关系(Within)、叠置关系(Overlap),并将这5种关系定义为空间关系的最小集,其特征为: 1) 相互之间不能进行转化; 2) 能覆盖所有的空间关系模式; 3) 能应用于同维与不同维的几何目标; 4) 每一种关系对应于唯一的DE-9IM矩阵; 5) 任何其它的DE-9IM关系可以通过用这5种基本关系进行表达。　　 另外,为了用户的使用方便,还定义几个基本的空