算法系列之九：计算几何与图形学有关的几种常用算法（二）
发表于2016-07-01
3.6 用矢量的叉积判断直线段是否有交
矢量叉积计算的另一个常用用途是直线段求交。求交算法是计算机图形学的核心算法，也是体现速度和稳定性的重要标志，高效并且稳定的求交算法是任何一个CAD软件都必需要重点关注的。求交包含两层概念，一个是判断是否相交，另一个是求出交点。直线（段）的求交算法相对来说是比较简单的，首先来看看如何判断两直线段是否相交。
常规的代数计算通常分三步，首先根据线段还原出两条线段所在直线的方程，然后联立方程组求出交点，最后再判断交点是否在线段区间上。常规的代数方法非常繁琐，每次都要解方程组求交点，特别是交点不在线段区间的情况，计算交点就是做无用功。计算几何方法判断直线段是否有交点通常分两个步骤完成，这两个步骤分别是快速排斥试验和跨立试验。假设要判断线段P1P2和线段Q1Q2是否有交点，则：
（1）、快速排斥试验
设以线段 P1P2 为对角线的矩形为R1， 设以线段 Q1Q2 为对角线的矩形为R2，如果R1和R2不相交，则两线段不会有交点；
（2）、跨立试验。
如果两线段相交，则两线段必然相互跨立对方，所谓跨立，指的是一条线段的两端点分别位于另一线段所在直线的两边。判断是否跨立，还是要用到矢量叉积的几何意义。以图3为例，若P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即：
( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0
上式可改写成：
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0
当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明线段P1P2和Q1Q2共线（但是不一定有交点）。同理判断Q1Q2跨立P1P2的依据是：
( Q1 - P1 ) × ( P2 - P1 ) * ( Q2 - P1 ) × ( P2 - P1 ) < 0
具体情况如下图所示：
图3 直线段跨立试验示意图
根据矢量叉积的几何意义，跨立试验只能证明线段的两端点位于另一个线段所在直线的两边，但是不能保证是在另一直线段的两端，因此，跨立试验只是证明两条线段有交点的必要条件，必需和快速排斥试验一起才能组成直线段相交的充分必要条件。根据以上分析，两条线段有交点的完整判断依据就是：1)以两条线段为对角线的两个矩形有交集；2)两条线段相互跨立。
判断直线段跨立用计算叉积算法的CrossProduct()函数即可，还需要一个判断两个矩形是否有交的算法。矩形求交也是最简单的求交算法之一，原理就是根据两个矩形的最大、最小坐标判断。图4展示了两个矩形没有交集的各种情况：
图4 矩形没有交集的几种情况
图5展示了两个矩形有交集的各种情况：
图5 矩形有交集的几种情况
从图4和图5可以分析出来两个矩形有交集的几何坐标规律，就是在x坐标方向和y坐标方向分别满足最大值最小值法则，简单解释这个法则就是每个矩形在每个方向上的坐标最大值都要大于另一个矩形在这个坐标方向上的坐标最小值，否则在这个方向上就不能保证一定有位置重叠。由以上分析，判断两个矩形是否相交的算法就可以如下实现：
1 2 3 4 5 6 7 | bool IsRectIntersect(const Rect& rc1, const Rect& rc2){ return ( (std::max(rc1.p1.x, rc1.p2.x) >= std::min(rc2.p1.x, rc2.p2.x)) && (std::max(rc2.p1.x, rc2.p2.x) >= std::min(rc1.p1.x, rc1.p2.x)) && (std::max(rc1.p1.y, rc1.p2.y) >= std::min(rc2.p1.y, rc2.p2.y)) && (std::max(rc2.p1.y, rc2.p2.y) >= std::min(rc1.p1.y, rc1.p2.y)) ); } |
完成了排斥试验和跨立试验的算法，最后判断直线段是否有交点的算法就水到渠成了：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | bool IsLineSegmentIntersect(const LineSeg& ls1, const LineSeg& ls2){ if(IsLineSegmentExclusive(ls1, ls2)) //排斥实验 { return false; } //( P1 - Q1 ) ×'a1?( Q2 - Q1 ) double p1xq = CrossProduct(ls1.ps.x - ls2.ps.x, ls1.ps.y - ls2.ps.y, ls2.pe.x - ls2.ps.x, ls2.pe.y - ls2.ps.y); //( P2 - Q1 ) ×'a1?( Q2 - Q1 ) double p2xq = CrossProduct(ls1.pe.x - ls2.ps.x, ls1.pe.y - ls2.ps.y, ls2.pe.x - ls2.ps.x, ls2.pe.y - ls2.ps.y); //( Q1 - P1 ) ×'a1?( P2 - P1 ) double q1xp = CrossProduct(ls2.ps.x - ls1.ps.x, ls2.ps.y - ls1.ps.y, ls1.pe.x - ls1.ps.x, ls1.pe.y - ls1.ps.y); //( Q2 - P1 ) ×'a1?( P2 - P1 ) double q2xp = CrossProduct(ls2.pe.x - ls1.ps.x, ls2.pe.y - ls1.ps.y, ls1.pe.x - ls1.ps.x, ls1.pe.y - ls1.ps.y); //跨立实验 return ( (p1xq * p2xq <= 0.0) && (q1xp * q2xp <= 0.0) );} |
IsLineSegmentExclusive()函数就是调用IsRectIntersect()函数根据结果做排斥判断，此处不再列出代码。
3.7 点和多边形关系的算法实现
好了，现在我们已经了解了矢量叉积的意义，以及判断直线段是否有交点的算法，现在回过头看看文章开始部分的讨论的问题：如何判断一个点是否在多边形内部？根据射线法的描述，其核心是求解从P点发出的射线与多边形的边是否有交点。注意，这里说的是射线，而我们前面讨论的都是线段，好像不适用吧？没错，确实是不适用，但是我要介绍一种用计算机解决问题时常用的建模思想，应用了这种思想之后，我们前面讨论的方法就适用了。什么思想呢？就是根据问题域的规模和性质抽象和简化模型的思想，这可不是故弄玄虚，说说具体的思路吧。
计算机是不能表示无穷大和无穷小，计算机处理的每一个数都有确定的值，而且必须有确定的值。我们面临的问题域是整个实数空间的坐标系，在每个维度上都是从负无穷到正无穷，比如射线，就是从坐标系中一个明确的点到无穷远处的连线。这就有点为难计算机了，为此我们需要简化问题的规模。假设问题中多边形的每个点的坐标都不会超过(-10000.0, +10000.0)区间（比如我们常见的图形输出设备都有大小的限制），我们就可以将问题域简化为(-10000.0, +10000.0)区间内的一小块区域，对于这块区域来说，>= 10000.0就意味着无穷远。你肯定已经明白了，数学模型经过简化后，算法中提到的射线就可以理解为从模型边界到内部点P之间的线段，前面讨论的关于线段的算法就可以使用了。
射线法的基本原理是判断由P点发出的射线与多边形的交点个数，交点个数是奇数表示P点在多边形内（在多边形的边上也视为在多边形内部的特殊情况），正常情况下经过点P的射线应该如图6（a）所示那样，但是也可能碰到多种非正常情况，比如刚好经过多边形一个定点的情况，如图6 （b），这会被误认为和两条边都有交点，还可能与某一条边共线如图6 （c）和（d），共线就有无穷多的交点，导致判断规则失效。还要考虑凹多边形的情况，如图6（e）。
图6 射线法可能遇到的各种交点情况
针对这些特殊情况，在对多边形的每条边进行判断时，要考虑以下这些特殊情况，假设当前处理的边是P1P2，则有以下原则：
1）、如果点P在边P1P2上，则直接判定点P在多边形内；
2）、如果从P发出的射线正好穿过P1或者P2，那么这个交点会被算作2次（因为在处理以P1或P2为端点的其它边时可能已经计算过这个点了），对这种情况的处理原则是：如果P的y坐标与P1、P2中较小的y坐标相同，则忽略这个交点；
3）、如果从P发出的射线与P1P2平行，则忽略这条边；
对于第三个原则，需要判断两条直线是否平行，通常的方法是计算两条直线的斜率，但是本算法因为只涉及到直线段（射线也被模型简化为长线段了），就简化了很多，判断直线是否水平，只要比较一下线段起始点的y坐标是否相等就行了，而判断直线是否垂直，也只要比较一下线段起始点的x坐标是否相等就行了。
应用以上原则后，扫描线法判断点是否在多边形内的算法流程就完整了，图7就是算法的流程图：
最终扫描线法判断点是否在多边形内的算法实现如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | bool IsPointInPolygon(const Polygon& py, const Point& pt){ assert(py.IsValid()); /*只考虑正常的多边形，边数>=3*/ int count = 0; LineSeg ll = LineSeg(pt, Point(-INFINITE, pt.y)); /*射线L*/ for(int i = 0; i < py.GetPolyCount(); i++) { /*当前点和下一个点组成线段P1P2*/ LineSeg pp = LineSeg(py.pts[i], py.pts[(i + 1) % py.GetPolyCount()]); if(IsPointOnLineSegment(pp, pt)) { return true; } if(!pp.IsHorizontal()) { if((IsSameFloatValue(pp.ps.y, pt.y)) && (pp.ps.y > pp.pe.y)) { count++; } else if((IsSameFloatValue(pp.pe.y, pt.y)) && (pp.pe.y > pp.ps.y)) { count++; } else { if(IsLineSegmentIntersect(pp, ll)) { count++; } } } } return ((count % 2) == 1);} |
在图形学领域实施的真正工程代码，通常还会增加一个多边形的外包矩形快速判断，对点根本就不在多边形周围的情况做快速排除，提高算法效率。这又涉及到求多边形外包矩形的算法，这个算法也很简单，就是遍历多边形的所有节点，找出各个坐标方向上的最大最小值。以下就是求多边形外包矩形的算法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | void GetPolygonEnvelopRect(const Polygon& py, Rect& rc){ assert(py.IsValid()); /*只考虑正常的多边形，边数>=3*/ double minx = py.pts[0].x; double maxx = py.pts[0].x; double miny = py.pts[0].y; double maxy = py.pts[0].y; for(int i = 1; i < py.GetPolyCount(); i++) { if(py.pts[i].x < minx) minx = py.pts[i].x; if(py.pts[i].x > maxx) maxx = py.pts[i].x; if(py.pts[i].y < miny) miny = py.pts[i].y; if(py.pts[i].y > maxy) maxy = py.pts[i].y; } rc = Rect(minx, miny, maxx, maxy);} |
除了扫描线法，还可以通过多边形边的法矢量方向、多边形面积以及角度和等方法判断点与多边形的关系。但是这些算法要么只支持凸多边形，要么需要复杂的三角函数运算（多边形边数小于44时，可采用近似公式计算夹角和，避免三角函数运算），使用的范围有限，只有扫描线法被广泛应用。
至此，本文的内容已经完结，以上通过对点与矩形、点与圆、点与直线以及点与多边形位置关系判断算法的讲解，向大家展示了几种常见的计算几何算法实现，用简短而易懂的代码剖析了这些算法的实质。下一篇将介绍计算机图形学中最基本的直线生成算法。
参考资料：
【1】计算几何：算法设计与分析 周培德 清华大学出版社 2005年
【2】计算几何：算法与应用 德贝尔赫（邓俊辉译） 清华大学出版社 2005年
【3】算法导论 Thomas H.Cormen等（潘金贵等译） 机械工业出版社 2006年
【4】计算机图形学 孙家广、杨常贵 清华大学出版社 1995年
腾讯GAD游戏程序交流群：484290331