空间拓扑关系描述:9交叉模型(DE-9IM)
空间关系描述是GIS系统的基本功能之一。我在学校学习到的空间关系分为三种：方位关系、距离关系、拓扑关系。今天我要分享的拓扑关系的标准化描述：9交叉模型。科班出身的GISer可能都知道9交模型是Egenhofer在《point set topological spatial relations》中提出的，不过，我今天不打算综述空间关系有关的理论发展，而是结合geos,分享9交模型的原理以及常见的拓扑关系描述符。
1）9交叉模型的定义
已知两个几何对象A，B(geos中称Geometry)，如何描述A与B的拓扑关系?就交叉模型给出的解决方案是通过描述A与B的内部(Interior , I)，边界(Boundary , B)，外部(Exterior , E)之间的关系来表达A与B的拓扑关系，内部(I)、边界(B)、外部(E)三者的关系构成了一个3×3的交集矩阵：
image.png
2)维度 Dimension
dim是dimension的缩写，指的是维度。在计算几何中，维度是几何要素的重要信息之一，通过维度，可以进行一些判断。比如，高维度的要素(比如线)，是不可能within在低维度的要素中的(比如点)。再比如，两个要素的交集的维度不会超过两者维度中最小者。在geos中(以及其他类似系统)：
- 多边形的维度是2，含组合多边形，带洞多边形等。
- 折线的维度为1，含多线。
- 点的维度为0，含多点。
- 空集(无交集)维度为F。
讲到这里，我们有必要了解不同类型的几何对象的内部，边界，外部各指的是什么。
3）内部，边界，外部的定义
对于多边形，内部是多边形的外环和内环围起来的面部分，边界由内环和外环构成，外部是除内部和边界以外的空间其他所有部分。
image
对于线要素，边界是线首尾节点(中间节点不算)，内部是线上除了首尾节点之外的部分。外部是空间除了内部与边界的部分。
image
点要素的内部是点本身，其边界是空集，外部是除了点本身外的空间其他部分。当然，对于点与其他要素的拓扑关系，我们通常习惯用“点在对象上”、“点不在对象上”进行描述，而且，在空间关系的计算上，也会按照这样的思路设计算法。我的意思是，对于点的拓扑关系处理一般先判断“点是否在对象上”然后填充9交叉模型矩阵的，而不是像多边形之间的关系判断。
image
4）9交叉模型的布尔形式
9交叉模型交集矩阵的定义域为{F,0,1,2}，那么一共可能有4^9种可能的拓扑关系。简单的考虑到外部与外部的交集的维度一定是2 ，那么可能的拓扑关系仍有8^9种，考虑很多种关系是矛盾的，剩下的组合仍然很多。这与我们希望直观，简单的表达拓扑关系的目标相差甚远。实际上，常见的拓扑关系描述符大概10种左右。为了方便描述这些关系，可以对矩阵的定义域做补充：
- 0,1,2表示非空，用T进行表示；
- 空集仍然用F表示；
- 引入*表示是什么都可以，geos中为“DONTCARE”
我们常用的拓扑关系描述符，就是采用上述6种类型描述出来的。
5）常用拓扑关系描述
Intersects
相交是指两对象的内部或边界存在交集，对应下面四种Intersection Matrix
image.png
就是说 对应Interior,Boundary的2×2的部分任意一个单元是T就可以了，其他的都“DONTCARE”。注意，这些矩阵都是对称的。
Disjoint
相离就是不相交，因此对应于相交的“Interior,Bountry 任意存在交集”，相离的定义是Interior,Boundary均不存在交集。
image.png
，这个矩阵也是对称的。
Contains
A.Contains(B)表示B完全在A内部。即A,B的interior相交并且 B的Interior与Boundary均不与A的exterior相交。
image.png
Within
Within 与Contains互为转置。A.Contains(B) = B.Within(A)。为什么叫互为转置呢，这是因为within的相交矩阵是Contains矩阵的转置就好了。
image.png
Equal
Equal表示的是A和B的形状完全相同(但是，不是说他们所有的坐标都是完全一样的！A或者B都可能有冗余的坐标，比如多点共线)。Equal的交集矩阵是内部相交，但任意一方的内部与边界均不与对方的外界相交
image.png
Overlap
叠置判断对A与B的维度有要求，要求A与B的维度相同，并且要求A与B的内部的交集的维度与AB的维度相同。因为多边形(面)之间的交集，点之间的交集均与他们的维度相同，线之间的交集可能会是点，线两种情况，所以特别将线与面、点之间的矩阵进行了区分,要求线的内部交集为线。
面、点的交集矩阵：
image.png
线的交集矩阵:
image.png
Touch
Touch表示的是两个几何要素之间的临接关系。touch关系的要点是：
两个元素的内部(interior)不能有交集,但是内部与边界，边界与边界可以有交集。
参与的两种元素不能同时为点类型。(点没有边界，内部与内部不相交变成相离了)
image.png
三个矩阵中，前两个互为转置关系，最后一个是对称矩阵。所以说这个关系也是对称的。
**Cross **
穿越的定义是A与B的内部有交集，但交集的维度要比A与B最大的维度要小。按照这个标准，点点与面面不可能存在cross关系，因为他们内部的交集的维度与他们的维度是相同的。同样，对于线线的交集要区别对待，指定其内部的交集为0(而不是1)。
非线线交集矩阵：
image.png
线线交集矩阵：
image.png
6)对拓扑关系的分析：从矩阵的角度
从上述9交叉模型矩阵的表达上，我们已经能够分析出很多有趣的信息了。
1.如果交集矩阵是对称的，那么对应的拓扑关系满足交换律的。A.Relation(B)=B.Relation(A)
可以交换的拓扑关系有(对应矩阵对称)：
Intersects,Disjoint,Equal,Overlap,Touch,Cross(线线)
不可以交换的拓扑关系有：
Contains,Within,Cross(非线线)
2.如果两个关系矩阵互为转置，那么这两个关系可以调换位置A.Relation1(B)=B.Relation2(A)。满足条件的关系有
Contains,Within
3.如果两个矩阵互补，那么两种关系也是互斥关系。满足条件的有
Intersects,Disjoint
4.拓扑关系之间的关系
上述8种关系并全不是互斥的，元素A,B可以同时满足多种拓扑关系。这些拓扑关系的“关系”更适合使用文氏图来描述：
image
