• Optics and Precision Engineering
  • Vol. 16, Issue 6, 1122 (2008)
SUN Xian-bin1,2,*, YIN Jie1, LI De-hua2, and XIAO Ben-lin1
Author Affiliations
  • 1[in Chinese]
  • 2[in Chinese]
  • show less
    DOI: Cite this Article
    SUN Xian-bin, YIN Jie, LI De-hua, XIAO Ben-lin. Point in polygon testing based on normal direction[J]. Optics and Precision Engineering, 2008, 16(6): 1122 Copy Citation Text show less

    Abstract

    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.
    SUN Xian-bin, YIN Jie, LI De-hua, XIAO Ben-lin. Point in polygon testing based on normal direction[J]. Optics and Precision Engineering, 2008, 16(6): 1122
    Download Citation