Optics and Precision Engineering, Volume. 16, Issue 6, 1122(2008)

Point in polygon testing based on normal direction

SUN Xian-bin1...2,*, YIN Jie1, LI De-hua2 and XIAO Ben-lin1 |Show fewer author(s)
Author Affiliations
  • 1[in Chinese]
  • 2[in Chinese]
  • show less

    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.

    Tools

    Get Citation

    Copy Citation Text

    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

    EndNote(RIS)BibTexPlain Text
    Save article for my favorites
    Paper Information

    Category:

    Received: Nov. 16, 2007

    Accepted: --

    Published Online: Feb. 28, 2010

    The Author Email: Xian-bin SUN (xianbinsun@126.com)

    DOI:

    CSTR:32186.14.

    Topics