判断点与指定多边形区域的关系的改进算法-论文.pdf

《判断点与指定多边形区域的关系的改进算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ISSN1009—3O44E—mail：kfyj@dnzs．net．caComputerKnowledgeandTechnology电脑知识与技术http：／／www．dnzs．net．cnVo1．10，No．22，August2014Tel：+86—551—6569096365690964判断点与指定多边形区域的关系的改进算法杨雅军，段明义(中州大学信息工程学院，河南郑州450044)摘要：介绍了判断点与多边形关系的多种方法，详细给出射线法，并对该方法进行优化，并给出了算法。在实验过程中该算法排除了一些点的判断，只需执行少量的射线法函数，实验结果表明，该算法简便、可靠、执行速度快。关

2、键词：点；多变形；关系；射线法；改进算法中图分类号：TP391文献标识码：A文章编号：10O9—3044(2014)22—5362—03TheImprovedAlgorithmforDeterminingPositionRelationbetweenPointandPolygonYANGYa-jan，DUANMing—yi(CoUegeofInformationEngineering，ZhongzhouUniversiW，Zhengzhou450044，China)Abstract：ThispaperintroducedavarietyofmethodstOjudgetherelati

3、onshipbetweenpointandpolygon，aswellasdetailedde—scriptionsoftheraymethod，andtooptimizethemethodandgivethealgorithm．Inthecourseoftheexperiment，thealgo—rithmexcludessomepointjudgment，onlyafewradi~methodfunction，theexperimentalresultshowthatthealgorithmissire—pie，reliable，fastexecution．Keywords：poi

4、nt；polygon；relation；raymehod；improvedalgorithm1概述在计算机图形学、计算机辅助设计、卫星定位系统、地理信息系统等进行图像处理时，经常需要判断一个点P与多边形s的关系，判断点P是否位于多边形区域内。解决该问题的方法有很多，有周角法、标号法、符号法、弧长法和射线法等，周角法又称转角法，是通过把点P与多边形s上任一点Q相连，当点Q沿多边形各边绕点P转一圈后，求出连线PQ所划过的累加夹角代数和a，若a=2p，则点P在多边形内，若a=p，则点P在多边形边界上，若a=O，则点P在多边形外部，否则点P是多边形的顶点；标号法是通过以点P为原点，划分四个象限

5、，判断多边形各边与各个象限的关系，从而确定点与多边形的位置关系；符号法是通过拟定多边形的解析方程f(x，y)=O，把点P的坐标数据代入方程，由f(x，y)的符号判断点的位置；弧长法要求多边形是有向多边形，一般规定沿多边形的正向，以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，并计算其中单位圆上弧长的代数和，若代数和为0，则点在多边形外部，若代数和为2叮r则点在多边形内部，若代数和为盯，则点在多边形上。这些算法中，大多算法复杂，要处理的特殊情况也很多，计算量大，影响了检测速度。射线法是从点P向某一个方向(如X轴正向)引射线，计算和多边形s交点的个数，如果个数是偶数或者o．~tJ点

6、在多边形外，如果是奇数，则在多边形内[7】。在判断点与多边形关系的算法中，用的最多也比较好用的是射线法。2算法描述射线法判断点P与多边形的关系的基本思想是从P向x轴正向引射线，计算P和多边形各边交点的个数和，如果偶数或者0则点P在多边形外，如果是奇数，则点P在多边形内，如下图1所示：一_卅(b)叶趟一(d)图1射线法图示收稿日期：2014—06—25作者简介：杨雅军(1980一)，女，河南睢县人，讲师，硕士研究生，主要研究方向为计算机应用；段明3(．(1978一)，男，河南郑州人，讲师，硕士研究生，主要研究方向为计算机应用。本栏目责任编辑：梁书第1O卷第22期(2014年8,51)Co

7、mputerKnowledgeandTechnology电脑知识与技术在图1(a)、(b)中，P点引出的射线与多边形有偶数个交点，点P在多边形外，(c)、(d)qh，P点引出的射线与多边形有奇数个交点，P在多边形内。这个是最基本的判别情况，比较简单，但还有一些复杂的情况需要特殊处理：1)点P在多边形顶点或边上，如图2所示。这种情况要快速地判断这个点是否在边上。P_．(a)(b)(c)图2点P在多边形顶点或边上2)当射线经过顶点时，判断也会出现异