GIS算法：3_拓扑空间关系计算模型DE-9IM

DE-9IM全称为Dimensionally Extended nine-Intersection Model，是一种判断对象之间空间关系的拓扑模型，java的拓扑套件jts和python的shapely在空间关系计算上，都使用了这种模型，它把复杂的空间运算降维成逻辑运算，用以提升程序的计算性能。

在DE-9IM中，几何对象被分成三个部分，内部（interior）、边界（boundary）和外部（exterior）。

模型对这三个部分的规定为：一个点的boundary为空；未封闭的线的boundary是它的两个端点；封闭线的boundary是空；多边形的boundary是它的环状边界；interior是边界被移除后剩下的部分。exterior是不在boundary和interior中点构成的部分。

Subtypes	Dim	Interior (I)	boundary (B)
Point, MultiPoint	0	Point, Points	Empty
LineString, Line	1	Points that are left when the boundary points are removed.	Two end points.
LinearRing	1	All points along the geometry.	Empty.
MultilineString	1	Points that are left when the boundary points are removed.	Those points that are in the boundaries of an odd number of its elements (curves).
Polygon	2	Points within the rings.	Set of rings.
MultiPolygon	2	Points within the rings.	Set of rings of its elements (polygons).
NOTICE: exterior points (E) are points p not in the interior or boundary, so not need extra interpretation, E(p)=not(I(p) or B(p)).

 

 

 

几何对象a与b的关系即可用一个3×3的数组表示：

其中dim()是相交部分的维度，点是0，线是1，面是2，如果不相交是-1。

用一个直观的例子来看：

 

 

从左到右和从上到下读取，DE-9IM(a,b)字符串代码为212101212，其中0、1、2都是相交，用T替换，这个字符串可以更新为TTTTTTTTT，-1是不相交，可以替换成F，这里没有。

可以看出，字符串前8个里，只有一个T就可以判断面a和b是相交的。所以，DE-9IM(a,b)函数，不需要把9个值都计算出来，就可以判断两者之间的关系，对于数组中不需要计算的值，用*号替代。

DE-9IM模型对空间关系都有定义。

 

 

 

我们只要能计算出3×3的Boolean数组，就能判断两个几何对象的关系。

在JTS或shapely程序中，为了提升计算性能，一般还会先进行MBR判断，再进行DE-9IM判断。

以最常见的a.interserts(b)为例，判别a是否与b相交。

1.判断a的MBR（最小外包矩形）是否与b的MBR相交，不相交，返回false。

2.判断a是否是矩形，如果是，判断a是否与b相交，不相交，返回false。

3.判断b是否是矩形，如果是，判断b是否与a相交，不相交，返回false。

4.采用DE-9IM模型进行相交判断，只要不是Disjoint，就是相交。

5.判断disJoint，既是经典的数学问题，点是否落在多边形内。

更具体的运算逻辑，可以查看JTS或shapely源码。

 

 

DE-9IM模型的原理是这样的，但是我们不需要自己写算法，只需要了解原理，最终的计算，还是会交给JTS或shapely。