Optics and Precision Engineering, Volume. 16, Issue 6, 1122(2008)
Point in polygon testing based on normal direction
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.
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
Category:
Received: Nov. 16, 2007
Accepted: --
Published Online: Feb. 28, 2010
The Author Email: Xian-bin SUN (xianbinsun@126.com)
CSTR:32186.14.