摘要
提出了基于法线方向的点包容检测算法。过待定点作一射线,此射线可能与多边形的某几条边有交点,从待定点向这条边的两端点作两个向量,求这两向量的法线方向。对法线方向进行计数,若法线方向为正向,将计数器加1;若法线方向为反向,将计数器减1。当法线方向的正反次数相同时,待定点在多边形外,否则在多边形内。此算法避免了某些算法的错误,计算量小,复杂度为O(n),简单易行。通过软件实验验证可知,算法简单有效、稳定可靠,对简单多边形、自相交多边形及带孔多边形等多类情况同样适用。
An algorithm of point in polygon testing based on normal direction is presented. A ray having several crossing points with the edges of polygon is drawn through a fixed point, two vectors are given from undetermined point to the endpoints of edge, then their normal directions is calculated. By using the normal direction as a reference for point in polygon test, the sum of normal directions of points and those edges is calculated. If the numbers of positive normals and negative normals are the same, the point is outside the polygon, otherwise, the point is inside the polygon. In the testing, the presented method can decrease computing time and can aviod some mistakes of other algorithm, its complexity is o（n）. Experimental result show this algorithm is suitable for some other cases including self-intersection polygon.
出处
《光学精密工程》
EI
CAS
CSCD
北大核心
2008年第6期1122-1126,共5页
Optics and Precision Engineering
基金
国家自然科学基金资助项目(No.69775022)
湖北省教育厅科研基金资助项目(No.G200514001)
关键词
计算机应用
点包容检测
多边形
法线方向
computer application
point in polygon testing
polygon
normal direction
