九交模型

九交模型

• DE-9IM(Dimensionally Extended nine-Intersection Model)
• 是OGC定义的一套模型，用于判断几何图形的拓扑关系

包围盒

• 包围盒(Bounding box、最小外接矩形)，是比较判断空间关系的重要元素，也是PostGIS中判断空间关系函数的原理。
  • 即判断两个几何的空间关系，可以简化为判断他俩的bb的关系
    • 因为bb由两个点确定，所以可以简化为判断他俩的一组点的关系
  • box2d("public"."geometry")

作用

• 在计算机中表示平面几何间的拓扑关系，从而通过已知的九交模型查询符合条件的几何图形
  • 通过表示两个几何图形的内部、边界、外部间的相交情况，来表示任意两个几何图形的间的拓扑关系。

三要素

• 内部（interior)
• 边界（boundary）
• 外部（exterior）

	内部	边界	外部
点	点本身	空集	点以外的其他部分
线	线本身	两个端点	线以外的其他部分
面	面本身	面的边界	面以外的其他部分

九交矩阵

• 将两个图形的相交关系用一个3*3的交集矩阵表示
  • 矩阵中是两个图形交集的维数(Dimension，dim)
• 维数
  • 点的维数是0
  • 线的维数是1
  • 面的维数是2
  • -1：不相交，即F
• 交集矩阵的定义域
  • [0,1,2,F]
• 为了简化判断关系，提高查询效率
  • 用T表示有相交关系，替代0、1、2
  • 用T(True)和F(False)表示相交关系的决定性因素，用*表示不重要的关系
• 特点
  • 对称矩阵：矩阵行列互换，矩阵不变
  • 转置矩阵：例如：A包含B，B在A内部，则这两种拓扑关系的九交矩阵一定相同
  • 理论上有4^9种基础的交集矩阵，有更少数量的简化的交集矩阵

a\b	Interior	Boundary	Exterior
Interior	dim(I(a) ∩ I(b))	dim(I(a) ∩ B(b))	dim(I(a) ∩ E(b))
Boundary	dim(B(a) ∩ I(b))	dim(B(a) ∩ B(b))	dim(B(a) ∩ E(b))
Exterior	dim(E(a) ∩ I(b))	dim(E(a) ∩ B(b))	dim(E(a) ∩ E(b))

拓扑关系

• 相交(Intersect)
  • 交叠(Overlap)
    • 交叠(Overlap)
    • 跨越(Crosses)
  • 包含(Contain)
    • 包含(Contain)
    • 覆盖(Covers)
  • 相等(Equal)
  • 在内部(Within)
    • 在内部(Within)
    • 被覆盖(Covered)
• 相离(Disjoin)
  • 相离(Disjoin)
  • 相接(Touch)

解算九交模型编码值(两个圆)

相离disjoin

基础

$$\begin{bmatrix} F&F&2\\F&F&1\\2&1&2 \end{bmatrix}$$

相接touch

基础

$$\begin{bmatrix} F&F&2\\F&0&1\\2&1&F \end{bmatrix}$$

简化

A.touches(B) =

$$\begin{bmatrix} F&*&*\\*&T&*\\*&*&* \end{bmatrix}$$

交叠overlap

基础

$$\begin{bmatrix} 2&1&2\\1&0&1\\2&1&2 \end{bmatrix}$$

覆盖covers

基础

$$\begin{bmatrix} 2&1&2\\F&0&1\\F&F&2 \end{bmatrix}$$

相等equal

基础

$$\begin{bmatrix} 2&F&F\\F&1&F\\F&F&2 \end{bmatrix}$$

包含contain

基础

$$\begin{bmatrix} 2&1&2\\F&F&1\\F&F&2 \end{bmatrix}$$

在内部with

基础

$$\begin{bmatrix} 2&F&F\\1&F&F\\2&1&2 \end{bmatrix}$$

被覆盖covered

基础

$$\begin{bmatrix} 2&F&F\\1&0&F\\2&1&2 \end{bmatrix}$$

跨越crosses

基础

$$\begin{bmatrix} 1&F&2\\0&F&1\\1&0&2 \end{bmatrix}$$

模板，复制用

$$\begin{bmatrix} *&*&*\\*&*&*\\*&*&* \end{bmatrix}$$

解算九交模型编码值(两个矩形)

相离disjoin

相接touch

交叠overlap

覆盖covers

相等equal

包含contain

PostGIS中的实现

函数

• 相交(Intersect)：FUNCTION "public"."_st_intersects"("geom1" "public"."geometry", "geom2" "public"."geometry")
• st_relate：FUNCTION "public"."st_relate"("geom1" "public"."geometry", "geom2" "public"."geometry")
  • 两参函数：计算两图形的九交模型编码值
  • 三参函数：若两图形的九交模型编码值等于第三个参数的值，则返回true

积累

1

基础

$$\begin{bmatrix} 1&F&F\\0&0&F\\2&1&2 \end{bmatrix}$$

简化

• A线，B面

  $$\begin{bmatrix} *&*&F\\*&T&*\\*&*&* \end{bmatrix}$$

• A包含于B
• A相接于B

-- 建表
DROP TABLE IF EXISTS lakes,docks;
CREATE TABLE lakes ( id serial primary key, geom geometry );
CREATE TABLE docks ( id serial primary key, good boolean, geom geometry );
 
INSERT INTO lakes ( geom )
  VALUES ( 'POLYGON ((100 200, 140 230, 180 310, 280 310, 390 270, 400 210, 320 140, 215 141, 150 170, 100 200))');
 
INSERT INTO docks ( geom, good )
  VALUES
        ('LINESTRING (170 290, 205 272)',true),
        ('LINESTRING (120 215, 176 197)',true),
        ('LINESTRING (290 260, 340 250)',false),
        ('LINESTRING (350 300, 400 320)',false),
        ('LINESTRING (370 230, 420 240)',false),
        ('LINESTRING (370 180, 390 160)',false);

-- 求九交模型编码
select ST_Relate('LINESTRING (170 290, 205 272)','POLYGON ((100 200, 140 230, 180 310, 280 310, 390 270, 400 210, 320 140, 215 141, 150 170, 100 200))');

-- 根据基础九交模型编码，进行查询
SELECT docks.*
FROM docks JOIN lakes ON ST_Intersects(docks.geom, lakes.geom)
WHERE ST_Relate(docks.geom, lakes.geom, '1FF00F212');

-- 根据简化九交模型编码，进行查询
SELECT docks.*
FROM docks JOIN lakes ON ST_Intersects(docks.geom, lakes.geom)
WHERE ST_Relate(docks.geom, lakes.geom, 'TFFTTFTTT');

-- 根据简化九交模型编码，进行查询
SELECT docks.*
FROM docks JOIN lakes ON ST_Intersects(docks.geom, lakes.geom)
WHERE ST_Relate(docks.geom, lakes.geom, '**F*T****');

-- 验证查询结果
SELECT docks.*
FROM docks JOIN lakes ON ST_Intersects(docks.geom, lakes.geom)
WHERE good=true;

2

基础

$$\begin{bmatrix} 1&0&1\\0&F&0\\2&1&2 \end{bmatrix}$$

参考文章

• 参考文章