GIS算法中的计算几何基础

维数扩展的9交集模型

概述

关系运算是指用于检验2个几何对象的特定的拓扑空间关系的逻辑方法。两个几何对象拓扑空间关键关系最基本的比较方法就是成对比较2个几何对象的内部、边界和外部的交集。并基于交集矩阵产生的实体来对两个几何对象空间关系分类

普通拓扑学很好的定义了内部、边界和外部的概念。这些概念适用于二维空间中二维对象的空间关系的定义，这些概念要适用于二维空间中的一维和零维对象时，需要组合拓扑学方法。

模型介绍

对于几何体$a$, 假设$Ia、Ba、Ea$分别表示$a$的内部、边界、外部。则$Ia、Ba、Ea$任意2个的交集就生成一个混合维数的几何体几何$x$。

例如，2个多边形的边界可以有一个点和一条线组成。假设$dimx$返回$x$中的几何体的最大维数为（-1,0,1,2）-1表示$dim\phi$,维数扩展的9交集模型DE-9IM,

空间关系的描述可以归纳为：两个几何体，以表示2个几何体DE-9IM结果合理值集合的模式矩阵形式输入。只要2个几何体的空间关系符合模式矩阵表示的合理值中的一个，则返回TURE。

模式矩阵有9中模式-值集合构成，一种集合对应矩阵一个单元，可能的模式值$p$为$\left\{ T, F, *, 0, 1,2 \right\}$,对于任何单元的所属何种交集$x$含义如下
$p$=T$\Rightarrow$dim$x$ $\in \left\{0,1,2\right\}$
$p$=F$\Rightarrow$dim$x$=-1
$p$=* $\Rightarrow$dim$x$ $\in \left\{-1,0,1,2\right\}$
$p$=0$\Rightarrow$dim$x$=0
$p$=1$\Rightarrow$dim$x$=1
$p$=2$\Rightarrow$dim$x$=2

空间关系的判定

由于模式矩阵的空间关系的确定使得用户可以检测大部分的空间关系，并能对特殊的空间关系进行检测，可仍然存在缺点，模式矩阵只是抽象画的语言而非人性化的语言，为了满足人性化的语言表示。定义了一系列用于DE-9IM的空间关系，分别为相离、相接、相交、真包含、重叠。

设
$P$表示零维的几何点，包括点和多点
$L$表示一维几何体
$A$表示二维几何体，包括面和多面

相离[disjoint]

设2个几何体（闭合）$a和b$
a.disjointb $\Leftrightarrow$ $a \cap b = \emptyset$
在DE-9IM表示
a.disjointb $\Leftrightarrow$ $Ia \cap Ib =\emptyset$ $\cap$ $Ia \cap Bb \neq \emptyset$ $\cap$ $Ba \cap Ib = \emptyset$ $\cap$ $Ba \cap Bb \neq \emptyset$ $\Leftrightarrow$ a.relateb, "FFFF***"

相接[touches]

不适用于点和点的关系
a.Touchesb $\Leftrightarrow$ $Ia \cap Ib =\emptyset$ $\cap$ $a \cap b \neq \emptyset$
在DE-9IM表示
a.Touchesb $\Leftrightarrow$ $Ia \cap Ib =\emptyset$ $\cap$ $Ba \cap Ib \neq \emptyset$ $\cup$ $Ia \cap Bb \neq \emptyset$ $\cup$ $Ba \cap Bb \neq \emptyset$ $\Leftrightarrow$ a.Realteb, "FT*******" $\cup$ a.Realteb, "F**T*****" $\cup$ a.Realteb, "F***T****"

相交[crosses]

a.Crossesb $\Leftrightarrow$ dim$Ia \cap Ib$ < maxdim$Ia$, dim$Ib$ $\cap$ $a \cap b \neq a$ $\cap$ $a \cap b \neq b$

真包含[withins]

a.withinb $\Leftrightarrow$ $a \cap b = a \cap Ia \cap Ib \neq \emptyset$

重叠[overlaps]

a.overlapsb $\Leftrightarrow$ dimIa=dimIb=dimIa $\cap$ Ib $\cap$ $a \cap b \neq a$ $\cap$ $a \cap b \neq b$

包含[contains]

a.containsb $\Leftrightarrow$ b.withinsa

相交[Intersects]

a.intersectsb $\Leftrightarrow$ !a.Disjointb

矢量的概念

如果一条线段的端点是由次序之分，我们吧这种线段称为有向线段，如果有向线段$p_1,p_2$的起点$p_1$在坐标原点。我们可以吧它称为矢量$p_2$

加减法

设二维向量P=$x_1,y_1$, Q=$x_2,y_2$;
则矢量的加法定义为 P + Q = $x_1 + x_2, y_1 + y_2$
则矢量的减法定义为 P - Q = $x_1 - x_2, y_1 - y_2$

叉积

计算机矢量叉积是与直线和线段相关算法的核心部分，设二维向量P=$x_1,y_1$, Q=$x_2,y_2$;
则矢量叉积定义为有0,0,P,Q,PQ所组成的平行四边形的面积。即 P Q = $x_1y_2 - x_2y_1$

叉积的一个非常重要的性质是可以通过它的符号判断2个矢量之间的顺逆时针关系
若 P $\times$ Q > 0 ,则P在Q的顺时针方向
若 P $\times$ Q < 0 ,则P在Q的逆时针方向
若 P $\times$ Q = 0 ,则P和Q共线

折线段的拐向判断

对于有公共端点的线段$p_0p_1$和$p_1p_2$ 则计算$p_2-p_0 \times p_1-p_0$的符号可以判断线段的拐点
若 $p_2-p_0 \times p_1-p_0$ > 0 则$p_1$点拐向右侧有得到$p_1p_2$
若 $p_2-p_0 \times p_1-p_0$ < 0 则$p_1$点拐向左侧有得到$p_1p_2$
若 $p_2-p_0 \times p_1-p_0$ = 0 三点共线

判断点是否在线段上

设点为Q, 线段为$P_1P_2$,判断点Q在线段$P_1P_2$的依据是$Q - P_1 \times Q - P_2$ = 0 Q 在以$P_1$、$P_2$为顶点的对角矩形内，后者保证$Q$不在线段$P_1P_2$的延长线或者反向延长线上
特别主要注意的是，需要考虑水平和垂直线段2钟特殊情况

判断两线段是否相交

算法一

1. 快速排斥实验

设以线段$P_1P_2$为对角线的矩形R,设以线段$Q_1Q_2$为对角线的矩形为T,如果R和T不想交，则2个线段不相交
2. 跨立实验
如果两线段相交，则两线段必然相互跨立对方。若$P_1P_2$跨立$Q_1Q_2$,则
$P_1- Q_1$和$P_2 - Q1$位于$Q_2 - Q_1$的两侧，即$P_1- Q_1$ $\times$ $Q_2 - Q_1$ $\times$ $P_2- Q_1$ $\times$ $Q_2- Q_1$ < 0

算法二

定义A,B,C,D为二维空间的点，则有向线段AB和CD的参数方程为
AB = A + rB - A
CD = C + sD - C

如果AB和CD相交，则

A + rB - A = C + sD - C $\Rightarrow$

$$\begin{equation}\left\{\begin{array}{c}Ax + rBx - Ax = Cx + sDx - Cx \\Ay + rBy - Ay = Cy + sDy - Cy\end{array}\right.\end{equation}$$
如果 r > 1 ,则P位于有向线段AB的延长线上
如果 r < 0 ,则P位于有向线段AB的反向延长线上
如果 s > 1, 则P位于有向线段CD的延长线上
如果 s < 0, 则P位于有向线段CD的反向延长线上
如果 $0 \leq r \leq 1$ 并且$0 \leq s \leq 1$ 则交点存在，且交点为与线段AB和CD之间

判断矩形是否包含点

只需要判断该点的横坐标和纵坐标是否夹在左右边和上下边之间

判断线段、折线、多边形是否在矩形中

因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了

判断矩形是否在矩形中

只要比较左右边界和上下边界就可以了

判断圆是否在矩形中

很容易证明，圆在矩形中的充分必要条件是，原型在矩形中且圆的半径小于或者等于圆心到矩形四边的距离的最小值

判断点是否在多边形内

射线法

这个方法计算从$P$开始的射线穿过多变形边界的次数，多边形的边界将多边形分为内部和外部，如果是偶数，则点在多变形外部，否则点在多边形的内部。
进一步： 一个标准的约定是在左边界或者下边界的点认为是在内部，在右边界或者上边界的点是在多边形外部。

算法

通常取X轴正方向为射线方向，奇数次相交，则在形内；偶数次相交，则在形外

转角法

计算多边形绕点有多少次，当多边形没有环绕点时，那么点在多边形的外部。

判断线段是否在多边形内

线段在多边形内的一个必要条件是线段的2个端点都在多边形内，但由于多边形可能为凹；所以这不能作为判断的充分条件，如果线段和多边形的边的左右2侧分属多个多边形的内外不同部分。所有线段一定会有一部分在多边形的外部，如下图，于是我们得到线段在多边形内部的第二个必要条件：线段和多边形的所有边都不内交

判断折线是否在多边形内

参考判断线段是否在多边形内

判断多边形是否在多边形内

只要判断多边形的每个边是否都在多边形内，参考判断线段是否在多边形内

判断圆是否在多边形内

只要计算圆心到多边形的每条边的最短距离，如果该距离大于或者等于圆半径则该圆在多边形内

判断点是否在圆内

计算圆心到该点的距离和圆半径的距离关系

判断线段、折线、矩形、多边形是否在圆内

因为圆是凸集，所以只需要判断每个顶点是否在圆内即可

判断圆是否在圆内

设2圆为$O_1,O_2半径分别为r_1,r_2,要判断O_2在O_1内,先比较r_1和r_2的大小，如果r_1<r_2,则O_2不可能在O_1,如果2圆心的距离大于r_1-r_2;则O_2不在O_1内，反之在$

计算两条共线的线段的交点

对于两条共线的线段，它们之间的位置关系有4种

• 没有交点
• 有一个交点但是没有2条线段没有重合的位置
• 有一个交点 但是2个条有重合的位置
• 有2个交点 短线段和长线段重合

中心点的计算

多边形的中心点（又叫质心或者重心）可以讲多边形分割为三角形，邱三角形的中心点，然后将三角形的中心加权求和取得，三角形的中心点$c_x,c_y$是三角形三个角点坐标的平均
$$\begin{cases}c_x = x_1 + x_2 + x_3 /3 \\c_y = y_1 + y_2 + y_3 /3\end{cases}$$
权重的选取可以依据每个三角形的面积占多边形面积的比例

过点做垂线

选取一点C，选择一条线段AB，求取过点C垂直与AB的垂线段CP,P点位于直线AB上