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

在诸多研究领域中,判断点是否在封闭多边形区域内是一个非常基本而重要的问题.在分析解决这一问题的常用方法的基础上,以矢量叉积结果的正负号为研究对象,分类讨论特殊情形,提出完整判断点与封闭多边形(包括曲线边)区域关系的算法,然后用LabVIEW编程对算法进行验证并对算法所执行的时间进行测试分析.测试结果显示多边形的凸点数及...

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

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.