判断点与指定多边形区域的关系的改进算法

摘要：介绍了判断点与多边形关系的多种方法，详细给出射线法，并对该方法进行优化，并给出了算法。在实验过程中该算法排除了一些点的判断，只需执行少量的射线法函数，实验结果表明，该算法简便、可靠、执行速度快。

关键词：点；多变形；关系；射线法；改进算法

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2014）22-5362-03

1 概述

在计算机图形学、计算机辅助设计、卫星定位系统、地理信息系统等进行图像处理时，经常需要判断一个点P与多边形S的关系，判断点P是否位于多边形区域内。解决该问题的方法有很多，有周角法、标号法、符号法、弧长法和射线法等[1-4]，周角法又称转角法，是通过把点P与多边形S上任一点Q相连，当点Q沿多边形各边绕点P转一圈后，求出连线PQ所划过的累加夹角代数和a，若a=2p，则点P在多边形内，若a=p，则点P在多边形边界上，若a=0，则点P在多边形外部，否则点P是多边形的顶点；标号法是通过以点P为原点，划分四个象限，判断多边形各边与各个象限的关系，从而确定点与多边形的位置关系；符号法是通过拟定多边形的解析方程f（x，y）=0，把点P的坐标数据代入方程，由f（x，y）的符号判断点的位置[5]；弧长法要求多边形是有向多边形，一般规定沿多边形的正向，以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，并计算其中单位圆上弧长的代数和，若代数和为0，则点在多边形外部，若代数和为2π则点在多边形内部，若代数和为π，则点在多边形上[6]。这些算法中，大多算法复杂，要处理的特殊情况也很多，计算量大，影响了检测速度。射线法是从点P向某一个方向（如x轴正向）引射线，计算和多边形S交点的个数，如果个数是偶数或者0则点在多边形外，如果是奇数，则在多边形内[7]。在判断点与多边形关系的算法中，用的最多也比较好用的是射线法。

2 算法描述

射线法判断点P与多边形的关系的基本思想是从P向X轴正向引射线，计算P和多边形各边交点的个数和，如果偶数或者0则点P在多边形外，如果是奇数，则点P在多边形内，如下图1所示：

4 结论

本文描述了点与多边形关系的判断方法，并详细给出了射线法求解，针对多种特殊情况分析出改进的射线法，使算法更简便，提高了运算效率，为更复杂的多边形关系的求解打下了良好的基础。

参考文献：

[1] 唐泽圣，周嘉玉，李新友.计算机图形学[M].北京：清华大学出版社，2002.

[2] 周培德.计算几何―算法设计与分析[M].北京：清华大学出版社，2008.

[3] Donald Hearn，Pauline Baker M. 计算机图形学[M].蔡士杰，吴春，孙正兴，译.北京：电子工业出版社，2002.

[4] 燕昊.一种判断点在多边形内的新方法[J].河南科学，2010，28（11）：1469-1472.

[5] 骆雯，孙延明，陈振威，陈锦昌.判断点与封闭多边形相对关系的改进算法[J].机械，1999，26（3）：25-27.

[6] 孙家广，胡事民.计算机图形学基础教程[M].北京：清华大学出版社，2005.

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

[8] 苗春葆.点与多边形关系的射线法[J].电脑编程技巧与维护，2008（3）：56-58.