基于斜率的多边形内外点快速判别算法

洪志强

(江苏科技大学计算机科学与工程学院，江苏 镇江 212003)

0 引言

点与多边形的位置关系的判别，是计算机图形学中的一个基本问题，这在计算机图形处理、模式识别、CAD及可视化领域中有着广泛的应用。在三维渲染的光线跟踪等算法中更是有着举足轻重的作用，该算法的优劣，直接关系到算法的效率及应用可行性。由于这是一个基本的图形算法，近年来也鲜见有人发文章对此进行深入研究[1]，因此，目前大部分工程中所使用的还是相对传统的算法。传统的点与多边形的位置关系判别法主要有射线法[2]、角度和法[3]、重心坐标法[4-5]等及其一些改进算法[6-12]。这些方法虽也可行，但其运算复杂度和计算量却仍然很大，实际应用过程中耗时太多，导致一些以此为基础的复杂算法难以投入应用。像射线法[1]，该方法需要从待测点水平引出一条射线，然后依次对多边形各边进行求交运算，而一次求交运算就包含多次乘除法运算，可见其运算量多大，况且还有奇异点的特殊情况需要单独处理，因此，这种算法确实难以满足要求。而角度和法[2]需要计算各边到待测点的内角，这其中除了有复杂的三角函数运算之外，还有多次近似计算，其算法复杂程度和运算精度都有问题，还有重心坐标法，此法还引入了矩阵运算[4]，或是多变量的方程求解运算[5]，其运算复杂程度也是难以满足需求。而基于这些算法之上的改进算法[6]及其在应用过程中与其它算法结合的算法[13-14]，计算量仍然很大。

本文提出一种基于斜率的快速判别法。该算法在运算过种中只需计算该点与多边形各顶点的连线的斜率，然后依次与多边形各顶点的两条邻边的斜率进行比较，即可得到判定结果。该算法的核心思想是将问题最简化，最终判定的只是点与角的位置关系，整个判定过程算法简单，没有复杂的点乘、叉乘三角函数等运算，而仅只有平均n/2次除法及一些简单的逻辑判断，从而有效降低了运算复杂度，获得了很高的运算效率。

1 基本约定与算法思想

1.1 正方向的约定

在图形处理运算中，多边形通常被表示为一连串的顶点序列，这些序列的先后关系即为顺序，一个简单的多边形顶点序列通常有两种，即顺时针和逆时针，这两种顺序绘制出来分别为多边形的正面和反面，这里约定采用逆时针顺序为多边形的正方向，即正面朝上，如图1所示。

图1 方向约定

1.2 坐标系统

在笛卡尔坐标中，平面的中心为坐标原点，坐标轴的箭头所指方向为该轴的正方向，而在屏幕坐标中，屏幕的左上角为坐标原点，水平向右方向为x轴正方向，垂直向下方向为y轴的正方向。如图2所示。

图2 坐标系统图

在实际绘图中常用屏幕坐标系，因此本文也使用屏幕坐标系。

1.3 斜率

任取直线l上不同的两点分别记为P1(x1，y1)，P2(x2，y2)，应用斜率公式:

即可求得直线l的斜率。在三角形中，计算各边的斜率只需取各边的相应顶点，代入公式即可求得。注意，对于垂直的边，因x1=x2，有分母dx=0，所以为避免被0除的错误，这里以一个很小的数来代替，如dx=1e－6。

显然，由斜率公式可得，当分子或分母同为正或同为负时，斜率保持不变，这种性质在图形中的表示如图3所示。

图3 方向不同但斜率相同的两直线

1.4 斜率变化空间

在以逆时针为序的屏幕坐标空间中，为计算各种方向的直线的斜率，可以如下操作:

任取直线一两点，分别计为点A和点B，计算其斜率。然后固定其中一点如点A不动，以该点为圆心，逆时针旋转该直线，由B点的不同值即可计算出不同倾斜角度的直线的斜率在屏幕坐标空间中的变化范围，显然，水平轴逆时针旋转从0到360度时其直线斜率变化曲线如同正切曲线，如图4(b)所示。显然，在图4(a)中逆时针旋转的直线，斜率范围在区间(a)或(b)时其变化率为(0，+∞)，斜率范围在区间(c)或(d)时，其变化率为(－∞，0)。

图4 斜率的变化范围

1.5 点与角的位置关系

在图5中，∠AOB与点 P的关系为点 P位于∠AOB内，而∠AOB与点 P'的关系为点 P'不在∠AOB内。显然，点P是否在∠AOB内根据其点P与点O的连线的直线的斜率与∠AOB的两边的斜率相比较而得知。虽然∠A'OB'内点不在∠AOB内，但斜率相同，此处无需判别点是处在∠AOB内还是∠A'OB'内，而是将区域(c)和区域(d)都看作∠AOB的内点有效区，而区域(a)和区域(b)看作∠AOB的内点无效区，因此，这里只需看点 P是在(a)、(b)、(c)、(d)中的哪个区，即可判别出点P是否在∠AOB内点有效区。

图5 角与点的位置关系

1.6 同斜率点的排除

由上面所得，每个角即有两个内点有效区，而其中一个是真内点，另一个是其对顶角的内点，如何排除其对顶角的内点，可以如图6(a)所示。

图6 同斜率点非内点区域的排除

∠AOB有两个内点无效区(斜线)，点 P为∠AOB的内点，而点P'为∠A'OB'的内点，点P与点P'所在区域均为∠AOB的内点有效区，边AO与OB为∠AOB的邻边，∠AOB与∠OBA为邻角。显然，∠OBA也有两个内点无效区(格子)，点P在∠OBA的内点有效区，点P″也在∠OBA的内点有效区，这里，点P'虽处于∠AOB的内点有效区，但是处于∠OBA的内点无效区。显然，点P'所在区域不同时处于∠AOB与∠OBA的内点区域，应该排除。这里，只有点P才是∠AOB与∠OBA的真正内点。

由上扩展到三角形3个角的情况，如图6(b)所示，所有不同时处于所有角的内点区域的点P'、P″、P‴都会被排除，因此，只有点P所在才域的点才是三角形的真正内点。同理，即可快速判断出多边形内点。

2 算法描述

算法主要分为4个步骤:

(1)预处理。

本文提出的算法只适用于有序的逆时针顺序凸多边形。若顺序相反，可反转顶点次序再作判断。若为凹多边形，则需先对多边形在凹点处进行分解，使之成为多个凸多边形序列，再依次作判断。

(2)计算出多边形的各边斜率，若需多次使用，只需首次计算一次，然留结果供后续使用而无需重复计算。

(3)记待测点为P(xp，yp)，依取第i个多边形顶点A(xa，ya)，计算由该两点组成的直线的斜率，记为spa。

(4)取第i个顶点的前向边与后向边斜率分别记为 se1、se2，对 se1、se2进行比较，可以分两大类:se1＜ se2和se1＞se2，具体比较如下:

①se1＜se2。

如图7所示，当se1＜0，se2＜0时，该角的内点无效区域为(s)、(s1)和(s2)，显然，当(s)和(s1)+(s2)为同斜率区域时，只需判断区域(s1)+s(2)即可。如图7所示，区域(s1)的斜率＞se2，(s2)的斜率＜se1，因此，只需判是否满足条件 spa＜se1或spa＞se2即可。

图7 各种斜率情况下的内点无效区域

同理，当se1＜0、se2＞0和se1＞0、se2＞0时分别如图7(b)和(c)所示，也只需判断是否满足条件spa＜se1或 spa＞se2即可。

②se1＞se2。

如图7所示，当se1＜0、se2＜0时，该角的内点无效区域为(s)和(s1)，显然，只需判别是否满足条件spa＜se1并且 spa＞se2即可。

同理，当se1＜0、se2＞0和se1＞0、se2＞0时分别如图7(b)和(c)所示，也只需判断是否满足条件spa＜se1并且 spa＞ se2即可。

当然，当se1=se2时，该多边形为退化多边形，即可认为是少一条同斜率的边的多边形，因此可以不作第三种情况考虑。

判别过程中，对于任何不满足判别要求的点即可判为外点。

(5)对于满足所有顶点的判别要求的内点，为多边形的真正内点，输出真值，算法结束。

综上，可用简洁的判别函数描述如下:

若对所有顶点进行判别通过，即为真正内点，输出即可。由此可见，该判别算法的简洁高效。

3 算法测试

3.1 自测试

测试程序使用 C++Builder2010编译，在1.7 GHZ的Intel i7740QM CPU上单线程进行测试，每秒可以进行千万次左右的四边形内点判别算法。

图8 对随机生成的三角形和多边形进行内点测试

如图8所示，对随机生成的凸多边形进行10000次随机取点测试，图蓝(深)色点为外点，黄(浅)色点为内点，无论是从速度上还是准确性上都取得了非常好的效果。

3.2 对比测试

分别使用内角和法、射线法和斜率判别法进行多边形内点测试。测试首先生成100万个随机点，然后使用3种算法对随机生成的三角形进行内外点测试，并记录下每次使用时间。循环测试100次，分别计算各种算法的平均使用时间，测试的结果对比如表1所示。

表1 主要算法速度测试对比

4 结束语

作为图形学中的一个基础的并且广泛使用的算法，对此算法进行的点滴改进，都对许多以此为基础的复杂算法有着深远的影响。虽然本文所提出的算法需要一些前提条件，但在图形学中，这些条件一般都不难具备。为了获得更高的运算效率，少量的额外运算开销也是值得的，另外，在3D图形处理中也经常需要进行位置关系判别，若能将此算法加以扩展乃至应用，那将是一件很有意义的事情。因此，合理使用此算法，即可有效提升现有的图形算法效率，为实际工程应用提供更多可能。

[1]王润科，张颜丽.判断点与多边形位置关系的算法综述[J].甘肃联合大学学报，2006，20(6):32-35，41.

[2]Taloy G.Point in polygon test[J].Survey Review，1994，32(254):479-484.

[3]Badouel Didier.An Efficient Ray-Polygon Intersection[M].AP Professional，1990.

[4]Eric Lengyel.Mathematics for 3D Game Programming and Computer Graphics(3rd Edition)[M].USA:Course Technology PTR，2012:141-143.

[5]Matt Pharr，Greg Humphreys.Physically Based Rending(2nd Edition)[M].USA:Morgan Kaufmann，2010:140-142.

[6]Yang Sheng，Yong Jun-Hai，Sun Jiaguang.A point-in-polygon method based on a quasi-closest point[J].Computers＆ Geosciences，2010，36(2):205-213.

[7]董秀山，刘润涛.判断点与简单多边形位置关系的新算法[J].计算机工程与应用，2009，45(2):185-186，196.

[8]周欣，张树有，潘志庚.基于链码和特征形的多边形内外点判断算法[J].计算机辅助设计与图形学报，2006，18(9):1317-1321.

[9]李基拓，陆国栋，冯星.基于单调性与相关边的多边形内外点判断算法[J].中国图像图形学报，2002，6(7):596-600.

[10]陈瑞卿，周健，虞烈.一种判断点与多边形关系的快速算法[J].西安交通大学学报，2007，41(1):59-63.

[11]王晨，池建斌，冯桂珍.一种判定点和多边形包含关系的有效算法[J].计算机应用与软件，2005，22(4):110-112.

[12]李雪，石广田.一种三角形内外点的快速判定方法[J].现代电子技术，2008，267(4):110-112.

[13]Li Jing，Wang Wencheng，Wu Enhua.Point-in-polygon tests by convex decomposition[J].Computers ＆ Graphics，2007，31(4):636-648.

[14]Alireza Zareia，Mohammad Ghodsi.Query point visibility computation in polygons with holes[J].Computational Geometry，2008，39(2):78-90.