偶然看到一个问题：电脑如何判断一个点是否位于一个三角形的内部？

这个问题说难不难，随手在纸上画个三角形，再在三角形内画一个黑点，随便找一个小学生都能分辨清楚，这个黑点在三角形的里边。但怎么让电脑“理解”点位于三角形内部这个概念呢？计算机算法肯定是有现成的,在网上找了一些方法,比如:射线法,角度和法,向量外积法,二分法,面积法……等等.这些算法大多有适用范围,有的还需要排除”特异”情况.而且这些算法只能在二维情况下使用.无法扩展到三维情况,即:空间点和立体的位置关系的判断,还需另找方法.

通用性,普适性是数学的意义之一,应该可以找到一个更通用的算法来解决这个问题.既然要同时解决二维(点和图形的位置关系)和三维(点和立体的位置关系)情况,甚至更高维度也适用的算法,线性代数几乎是唯一的工具.

线性代数组织几何元素的方式与常见的欧氏几何不同,因为线性代数处理的是任意有限维的线性空间,而欧氏几何连四维空间都无法处理,这就是为啥线性代数冠名”代数”的原因之一.在线性代数中,描述类似体或面这类几何元素主要依靠”凸包”这个概念.这里不具体讨论凸包是啥,但接下来的算法利用凸包完成.

由于不讨论凸包是啥而是直接使用它,所以首先讨论几个性质,帮助大家理解凸包:

[1]线性空间里的复杂体可以分割成凸包之和.比如:在二维空间里,我们找不到”凹三角形”,三角形肯定是”凸”的.用线条绘制的任何平面图形,总可以分割成若干个三角形.三角形其实就是二维空间里的凸包.

[2]根据凸包的性质,在n维空间中的凸包点数不多于n+1个.那么在二维空间中,凸包最多由三个点定义,这其实就是三角形(当三点不共线时).另外,两不重合点所定义的线段和一个单点也是二维空间下的凸包.

[3]凸包跟点的关系可以引出”仿射坐标”的概念,而仿射坐标又与齐次坐标关系密切.事实上,齐次坐标直接来自于凸包的定义.在N维空间中某向量(其几何意义就是一个点)在以某凸包为基的仿射坐标是一个(N+1)维的向量,且坐标值之和=1,也就是说,二维空间下的某向量(x,y)的仿射坐标类似于(a,b,c)且有a+b+c=1

上面说了那么多,都是理论上的,枯燥无味,下面将进入直观的释例(释例,即:用于解释的例子,这不是错字,我不接受发文助手的修订,哈哈哈),该例子以一个凸六边形为例子,之所以选择凸多边形是因为相对于凹多边形,凸多边形在分割三角形时更简单易懂.

释例配图

如上图示,六边形的6个顶点(N1至N6)散布在坐标系中,同时给出了5个判定点(E1至E5),这个6边形很容易就被分割成了4个三角形,分别是: (N1,N2,N3),(N1,N3,N4),(N1,N4,N5),(N1,N5,N6).这4个三角形就是二维空间里的4个凸包,这样,就可以利用E点在凸包下的仿射坐标判断E点的位置了,具体是:

以凸包的三个点为基,可以求得E点在这个基下的仿射坐标,然后对E的仿射坐标做如下判断：

[1]若E的仿射坐标值的元素中有负数,则说明E点不在该三角形(凸包)内。类似上图中的：(N1,N2,N3) -- E3,E4的关系

[2]若E的仿射坐标值中没有负数,但有1个元素是0,则说明E点在三角形的边上。类似上图中的：(N1,N3,N4) -- E2,E3的关系

[3]若E的仿射坐标值中没有负数,但有2个元素是0,则说明E点在三角形的顶点上。类似上图中的：(N1,N2,N3) -- N3(E5)的关系

[4]若求得的E的仿射坐标值中没有负数,也没有元素是0,则说明E点在三角形的内部。类似上图中的：(N1,N2,N3) -- E1的关系

这4种关系,可以进一步合并成两种:位于凸包内部或位于凸包边界上的点视为点在凸包内,而其它情况则视为点在凸包外.

接下来我们就利用上图的数据具体演示如何通过线性代数计算判断出点和凸包之间的位置关系,首先给出所有点的坐标,如下:

[1]判断E1是否位于多边形内

这其实就是判断E1是否位于三角形(N1,N2,N3)内,算法如下:

首先组建矩阵,左侧是定义三角形(凸包)的三个向量,以它们为基,右边增广E1向量,即:

然后将上面的矩阵下面增加一行,填充1,这样就完成了坐标的齐次化,就是:

对齐次化的坐标矩阵使用"高斯-诺尔当"消元法,得到"最简阶梯型矩阵",这其实就是中学生解N元一次方程组的方法,消元之后得到:

那么,消元之后的矩阵的最右边一列,就是点E1在基{N1,N2,N3}下的仿射坐标.

显然,这里三个坐标之和:

坐标求和得1可以验证手工计算的错误,若在手工消元过程中发生错误,则可在这里察觉到.当然,利用电脑消元是不会出错的.

求得了E1的仿射坐标,就可以判断E1与三角形(N1,N2,N3)的位置关系:显然,所有三个仿射坐标值都是正数,这说明E1点位于三角形(N1,N2,N3)内部.而这个三角形是六边形的一部分,这等同于E1位于六边形内部.

[2]判断E4是否位于多边形内

首先判断E4是否位于三角形(N1,N2,N3)内,算法与[1]类似,有:

这里E4的仿射坐标中出现了一个负数,这说明E4不在三角形(N1,N2,N3)内部.

于是继续判断E4是否位于三角形(N1,N3,N4)内,若仍在外部,就接着判断三角形(N1,N4,N5),三角形(N1,N5,N6),事实上,E4与这些三角形的仿射坐标是:

E4对于每一个三角形的仿射坐标都有负数坐标值,这说明E4都在它们的外部.

于是,E4位于由六边形分割而来的所有四个三角形的外部,这等同于E4位于六边形外部.

[3]观察E2,E3,E5的仿射坐标样式

由于我们是反着做题,每个E点与六边形的关系事实上我们是已经知道的,这里我们观察压线和重点情况下,点的仿射坐标会呈现出什么样子.

这里我们选择三角形(N1,N3,N4),因为E2,E3,E5都与这个三角形有关系,通过计算,我们得到:

(1)观察E2:E2的仿射坐标中没有负数,这说明它位于三角形内,但它的坐标中有一个0,这说明有基中的向量N4与E2无关,于是剩下N1和N3,这说明E2实际上位于由N1和N3组成的凸包上,也就是位于线段(N1,N2)上.

(2)观察E3:E3的仿射坐标与E2类似,E3实际上位于线段N3-N4上.也许你已经有了一个更大胆的推测:E3实际上位于线段(N3,N4)的中点处.因为除了0之外的另两个仿射坐标值都是.恭喜你,你的推测是正确的.仿射坐标有现实的物理和几何意义,坐标值可以确定点分别位线段两个端点的比例(当基为两个向量时),坐标值还相当于三角形的重心位置(当基为三个向量时).

(3)最后观察E5,E5的坐标值中有2个是0,只剩下1个非0值,而这个值必然等于1(想想,为啥?),这就代表,E5点和N3点重合.

[4]总结所有E点与六边形(N1,N2,N3,N4,N5,N6)的关系,如下:

E1 - 位于多边形内

E2 - 位于多边形内(且位于某条划分三角形的边界线上)

E3 - 位于多边形内(且位于多边形的一条边上,且在该边的中点处)

E4 - 位于多边形外

E5 - 位于多边形内(且位于多边形的一个顶点处)

可见,通过计算仿射坐标的方法,我们不仅可以判断一个点是否位于一个多边形内,甚至还能够得出这个点是否位于边界,或者位于边界上的特殊点(比如:中点,端点,三等分点)位上.

更宝贵的是,释例虽然是以二维情况为例解释仿射坐标算法,但对于三维空间(点和四面体的位置关系)甚至几何无法处理的四维,五维甚至更高的有限维度空间中的点与体之间的关系也是适用的.因为这个算法里只涉及到:(1)定义多边形(多面体)的点,(2)待判断的点,(3)"高斯-诺尔当"消元法,(4)判断数字的符号.四种基本的数学算法.以及分割体为凸包之和的逻辑算法.而且矩阵运算特别适合并行处理,给定的体被分割成N个凸包,这N个凸包同时与待判定点组合成N个矩阵,同时交付给CPU并行处理,现代典型的桌面级CPU或者显卡处理矩阵运算很容易突破几十亿次/秒的处理速度,这将会很快得到运算结果.

仿射坐标算法虽然针对某一特定环境不如专用算法高效,但这个算法通用性强,突破了几何维度限制,也没有"特例".是一种普适的用于判定给定点是否位于给定的多边形(多面体,甚至更高维度体)内部的有效的算法.

最后给出一个思考题:

已知三维空间内定义了一个四面体(N1,N2,N3,N4),另有几个待判定点以该四面体为基,算得了以下仿射坐标 :

[1] E1 (a,b,c,d)

[2] E2 (e,f,g,0)

[3] E3 (h,j,0,0)

[4] E4 (k,0,0,0)

[5] E5 (l,m,n,-p)

以上每个坐标字母都代表一个正数,且每一个仿射坐标之和都等于1.

你能判断出,每个E点具体位于该四面体的哪个位置吗?

==[答案]==

E1 - 位于四面体内

E2 - 位于四面体的一个面,即三角形(N1,N2,N3)上

E3 - 位于四面体的一个棱边,即线段(N1,N2)上

E4 - 位于四面体的一个顶点,即点N1处

E5 - 位于四面体外