学 GIS 空间数据库的时候, 拓扑方面内容笔记
拓扑的定义
拓扑是研究几何图形或空间在连续改变形状后还能保持不变的一些性质的一个学科. 它只考虑物体间的位置关系而不考虑它们的形状和大小.
"拓扑" 就是把实体抽象成与其大小, 形状无关的 "点", 而把连接实体的线路抽象成 "线", 进而以图的形式来表示这些点与线之间关系的方法, 其目的在于研究这些点, 线之间的相连关系. 表示点和线之间关系的图被称为拓扑结构图. 拓扑结构与几何结构属于两个不同的数学概念. 在几何结构中, 我们要考察的是点, 线, 面之间的位置关系, 或者说几何结构强调的是点与线所构成的形状及大小. 如梯形, 正方形, 平行四边形及圆都属于不同的几何结构, 但从拓扑结构的角度去看, 由于点, 线间的连接关系相同, 从而具有相同的拓扑结构即环型结构. 也就是说, 不同的几何结构可能具有相同的拓扑结构.
如三角形变成四边形, 原型, 环形, 角度, 长度, 面积, 形状等等都很可能发生变化. 此时, 不必考虑它们的形状和大小(如长度, 面积, 形状等等这些), 只考虑物体间的位置, 结构关系, 只专注于在连续改变形状后还能保持不变的一些性质(如他们都是一个圈), 这就是拓扑学.
拓扑学历史
拓扑英文名是 Topology, 直译是地志学, 最早指研究地形, 地貌相类似的有关学科.
几何拓扑学是十九世纪形成的一门数学分支, 它属于几何学的范畴. 有关拓扑学的一些内容早在十八世纪就出现了. 那时候发现的一些孤立的问题, 在后来的拓扑学的形成中占着重要的地位.
1679 年德国数学家莱布尼茨提出的名词 拓扑学, 起初叫形势分析学, 他在 17 世纪提出 "位置的几何学"(geometria situs)和 "位相分析"(analysis situs)的说法.
1736 年欧拉在解决了七桥问题, 给当时数学界引起很多思考;
1750 年欧拉在发表了多面体公式;
1833 年高斯在电动力学中用线积分定义了空间中两条封闭曲线的环绕数.
1847 年 J.B. 利斯廷根据希腊文τπο和λγο("位置" 和 "研究"), 提出 Topology 这一数学名词, 即拓扑学. Topology, 直译是地志学, 最早指研究地形, 地貌相类似的有关学科.
1851 年左右, 即 19 世纪中期, 德国数学家黎曼在复变函数的研究中提出了黎曼面的几何概念, 并且强调为了研究函数, 研究积分, 就必须研究形势分析学, 从此数学界开始了现代拓扑学的系统研究.
不同学科对拓扑的定义不尽相同
集合拓扑: 拓扑是集合上定义的一种结构.
点集拓扑学
点集拓扑学(Point Set Topology), 有时也被称为一般拓扑学(General Topology), 是数学的拓扑学的一个分支.
它研究拓扑空间以及定义在其上的数学结构的基本性质. 这一分支起源于以下几个领域: 对实数轴上点集的细致研究, 流形的概念, 度量空间的概念, 以及早期的泛函分析.
点集拓扑学定义
拓扑是一个包含一个集合 X 连同和 X 的子集族Σ(称为开集系)的二元组(X,Σ), 它满足如下三个公理:
开集的并集是开集.
有限个开集的交集是开集.
X 和空集是开集.
设 T 为非空集 X 的子集族. 若 T 满足以下条件:
X 与空集都属于 T;
T 中任意两个成员的交属于 T;
T 中任意多个成员的并属于 T; 则 T 称为 X 上的一个拓扑. 具有拓扑 T 的集合 X 称为拓扑空间, 记为(X,T).
也等价于:
X 和空集都属于 T;
T 中任意多个成员的并集仍在 T 中;
T 中有限多个成员的交集仍在 T 中.
此时称称 T 中的成员为这个拓扑空间的开集. 最普通的例子便是实数集上的距离拓扑, 这与我们通常对实数的认识相同. 最简单 (粗) 的拓扑为平凡拓扑, 它只包含 T 本身和空集, 最复杂 (细) 的拓扑的构成开集为 T 的所有子集.
同一个集合 X, 若指定不同的拓扑, 则构造出不同的拓扑空间. 凡属于 X 的子集称为 X 的一个关于 T 的开子集, 即开集. 开子集关于全集的补集, 称为闭子集, 即闭集. 一个集合是不是开 / 闭子集, 取决于拓扑的指定. 由定义, X 本身和空集是既开又闭的子集.
本质上, 拓扑就是要给一个集合指定一个几何结构, 然后这个集合就成了一个我们可以研究的空间. 比如, 有了拓扑和开集的定义后, 我们就可以摆脱大一数学分析的ε-δ来给出更一般的连续性定义: 设 A 和 B 是两个拓扑空间, A 到 B 的映射 f 称为连续的, 若任何 B 的开集在 f 下的原象是 A 的开集. 这样我们对于函数的研究将不再局限于实数, 而是搬到更一般的拓扑空间内了.
平面拓扑关系
对于一般的拓扑关系, 一图概括如下
Egenhofer 和 Franzosa 在 1991 年共同撰写的论文 Point-Set Topological Spatial Relations, 为空间拓扑 (九交模型) 奠定了重要基础.
依据集合论, 作者对于点集拓扑空间定义了以下基本概念, 以描述空间对象:
Interior(内部) : 对于 , interior 指的是所有包含 的开放集合的并集. 对于空间对象, 可以认为是空间对象的内部.
Closure(闭包) : 对于 , closure 指的是所有包含 的闭集合的交集. 对于空间对象, 可以认为是空间对象整体.
Boundary(边界) : 对于 , boundary 指的是 Y 的闭包与 Y 的补集的闭包的交集, 即 . 对于空间对象, 可以认为是空间对象的边界.
简而言之, 一个空间对象可定义为由内部 + 边界构成.
根据以上三条定义可知以下两命题:
. 即: 内部和边界的交集为空.
. 即: 内部和边界的并集为整个对象.
九交模型
在一个平面 R2 上, 两个对象 A 和 B 之间的二元拓扑关系要基于以下的相交情况: A 的内部 (A°), 边界(αA) 和外部 (A-) 与 B 的内部 (B°), 边界(αB) 和外部 (B-) 之间的交.
考虑取值有空 (0) 和非空 (1), 可以确定有 256 种二元拓扑关系. 对于嵌在 R2 中的二维区域, 有八个关系是可实现的, 并且它们彼此互斥且完全覆盖. 这些关系为: 相离(disjoint), 相接(meet), 交叠(overlap), 相等(equal), 包含(contain), 在内部(inside), 覆盖(cover) 和被覆盖(covered by).
九交模型
三维空间拓扑关系
点 - 点空间关系 2 种: 相离, 相等;
点 - 线空间关系 3 种: 相离, 相接, 包含于;
点 - 面空间关系 3 种: 相离, 相接, 包含于;
点 - 体空间关系 3 种: 相离, 相接, 包含于;
线 - 线空间关系 7 种: 相离, 相交, 交叠, 相等, 相接, 包含于, 包含;
线 - 面空间关系 5 种: 相离, 相接, 进入, 穿越, 包含于;
线 - 体空间关系 5 种: 相离, 相接, 进入, 穿越, 包含于;
面 - 面空间关系 10 种: 相离, 相接, 交叠, 相等, 包含于, 包含, 覆盖, 被覆盖, 穿越, 被穿越;
面 - 体空间关系 8 种: 相离, 相接, 交叠, 进入, 包含于, 包含, 穿越, 被穿越;
体 - 体空间关系 8 种: 相离, 相接, 进入, 相等, 包含于, 包含, 穿越, 被穿越.
基本空间拓扑关系的计算
点与直线的关系计算
直线方程:
- Ax+By+C=0
- A=y1-y2,
- B=x1-x2,
- C=y2x1-y1x2
令 S=Axi+Byi+C
当 S<0 点在顺时针方向上;
当 S=0 点在直线上;
当 S<0 点在逆指针方向上.
两条直线关系的计算
直线方程:
- Ax+By+C=0
- Ex+Fy+G=0
当 FA-EB=0 时, 两条直线的交点不存在; 否则, 交点坐标为:
- xi=(GB-FC)/(FA-EB)
- yi=(CE-AG)/(FA-EB)
空间目标之间的拓扑关系推理
两条线的直线段之间基本空间拓扑关系的推理
点与其他类型空间目标之间的拓扑关系决策树
线与面之间的全域空间拓扑关系决策树
面与面之间的全域空间拓扑关系基本类型的决策树
空间度量关系
度量关系是在欧氏空间 (Euclidean Space)(Blumenthal,1970) 和度量空间 (Metric Space)(Dhage,1992) 上进行的操作, 它是一切空间数据定量化的基础. 它包含长度, 周长, 面积, 距离等定量的度量关系, 其中最主要的度量空间关系是空间对象之间的距离关系.
欧几里德距离定义如下(Kolountzakis and Kutulakos,1992):
曼哈顿距离是两点在南北方向上的距离加在东西方向上的距离(Wu et al.,1987), 即:
点与点之间距离 & 点与线之间距离: dPL(P,L)=min{d1,d2,...dn}
线与线之间的距离: d(L1,L2)=min{d(P1,P2)|P1∈L1,P2 ∈L2}
点与面之间的距离:
"中心距离" 是点 P 与面 A 中几何中心或者重心之间的距离,
"最小距离" 是指点 P 与面 A 中所有点之间距离的最小值,
"最大距离" 是指点 P 与面 A 中所有点之间距离的最大值.
面与面之间的距离
"中心距离" 是指两个面状物体的质心之间的距离;
"最小距离" 是指面 A1 中的点 P1 与 A2 中的点 P2 之间的距离的最小值;
"最大距离" 是指面 A1 中的点 P1 与 A2 中的点 P2 之间的距离的最大值.
空间顺序关系及描述方法
锥形模型
每区域赋予东, 南, 西和北, 为得到更精确的方向关系可对其再进行细分得 8 或 16 方向.
最小外接矩形模型
该模型通过延伸目标的 MBR 的边, 将空间划分为 9 个区域, 分别表示为北, 东北, 东, 东南, 南, 西南, 西, 西北和目标 MBR 所在的中心方向.
Freksa-Zimmermann 模型
以直线段为参考的定性空间方向模型: 以直线为空间参考目标, 把二维空间分解为 15 个方向区域.
以点为参考目标的基本空间方向
点 A 与点 B 的空间方向关系可以用向量 AB 与正北方向的夹角 (顺时针) 来描述.
(a) 点 A 与点 B 之间的空间方向关系.
(b)点 A 与直线 BC 之间的空间方向关系, 以角平分线 L 的方位表示.
(c) 用两条直线的中点代表代表其方位.
以直线为参考目标的基本空间方向
(a) 直线 AB 和直线 CD 的方向可用向量 EF(E 和 F 分别为两直线的中点)来描述.
(b)直线 AB 和点 C 的方向关系.
(c) 划分直线段 AB 的方向片, 点 C 相对直线 AB 的关系可描述为点 C 在直线 AB 的哪个方向片中.
(d)直线 AB 和直线 CD 的方向可用向量 EF(E 和 F 分别为两直线的中点)来描述, 或用向量 ED 和向量 EC 来定义.
点与线或面之间的空间方向关系
(a) 方向线 PS 和 PE 定义了点 A 与线 L 之间的全域空间方向关系, 点 A 与 P1,P2,P3(中点)的连线定义了点 A 与不同直线段的局域空间方向关系.
(b)方向线 PS 和 PE 重和, 说明点 A 被线 L 包围, 这是全域空间方向关系, 点 A 与 P1,P2,P3,P4(中点)的连线定义了点 A 与不同直线段的局域空间方向关系.
(c)方向线 PS 和 PE 定义了点 A 与面 B 之间的全域空间方向关系, 用方向线 P1,P2 把面域 B 分为 3 部分, 每部分可以用该锥形的角平分线描述方向关系, 这 3 部分的面积与面积 B 的总面积之比分别为 B1,B2,B3. 也可以用该锥形的每个角平分线在面内的长度与角平分线在面内的总长度之比 L1,L2,L3 来表示.
(d)方向线 PS 和 PE 重和, 说明点 A 被面 B 包围, 这是全域空间方向关系, 面域不同和点 A 之间的局域空间方向关系描述方法与 (c) 同.
线与点, 线或面之间的空间方向计算与描述
(a) 线 ABCD 与点 E 之间的全域空间方向关系为 "相同", 直线段 AB 与点 E 之间的局域空间方向关系为 "西".
(b) 反映线与线之间的全域空间方向关系, 直线段 AB 与线 L2 的每条直线段和线的任意子集之间都有局域空间方向关系.
(c) 线与面的全域空间方向关系和局域空间方向关系均可象 (b) 一样计算和描述.
面与点, 线, 面之间的空间方向关系计算与描述
(a) 面 P 与点 C 之间的全域空间方向关系为 "相同", 面 P 的直线 AB 与点 C 之间的局域空间方向关系为 "北".
(b) 面 P 与直线 EFG 之间的全域空间方向关系和局域空间方向关系如图所示, 前者为 "东","相同" 和 "南", 而后者为 "东".
(c) 把区域栅格化, 判断子区域与源目标的全域空间方向关系和局域空间方向关系.
来源: http://www.bubuko.com/infodetail-3325652.html