平面内判断点与封闭区域关系的快速算法  

A Fast Algorithm for Judging the Relationship Between Points and Closed Area in a Plane

作　　者：王群 王恒升[2] WANG Qun;WANG Heng-sheng(Modern Engineering Training Center,Hunan University,Changsha 410082,China;College of Mechanical and Electrical Engineering,Central South University,Changsha 410083,China)

机构地区：[1]湖南大学现代工程训练中心,湖南长沙410082 [2]中南大学机电工程学院,湖南长沙410083

出　　处：《数学的实践与认识》2021年第6期137-143,共7页Mathematics in Practice and Theory

基　　金：国家“973”基础研究项目(2013CB035504)。

摘　　要：在诸多研究领域中,判断点是否在封闭多边形区域内是一个非常基本而重要的问题.在分析解决这一问题的常用方法的基础上,以矢量叉积结果的正负号为研究对象,分类讨论特殊情形,提出完整判断点与封闭多边形(包括曲线边)区域关系的算法,然后用LabVIEW编程对算法进行验证并对算法所执行的时间进行测试分析.测试结果显示多边形的凸点数及凹点数的多少对算法运行速度影响不大,由此表明该算法适用于多凸点、多凹点、曲线边等各种复杂情形,且运行快速(顶点数从几十至几千,在PC机常规配置下运行时间都在200ms以下),实现程序鲁棒性强.A very natural and important problem in many research fields is to determine whether a certain point is in the closed polygon area.On the basis of analyzing the common methods to solve this problem,taking the sign of the result of cross product of vector as the research object,discussing the special cases by classification,putting forward the algorithm of the relationship between the complete judgment point and the area of closed polygon(including curve edge).Then used Lab VIEW to verify the algorithm and test the execution time of the algorithm.The test results show that the number of convex and concave points of the polygon has little effect on the speed of the algorithm,which shows that the algorithm is suitable for various complex cases such as multi-convex points,multi-concave points,curve edges and so on,and runs fast(the number of vertices is from tens to thousands,and the running time is less than 200 ms under the general configuration of PC),and the program is robust.

关 键 词：曲线边多边形 矢量叉积 内外点判断 

分 类 号：O186.11[理学—数学]