An Algorithm for Deciding Whether a Point Set Is Inside a Polygon Based on Binary Search
Pan Ri · 2001
An algorithm for deciding whether a point set is inside a polygon is given on the basis of binary search method. This algorithm first splits the plane to generate an ordered set R of planar areas, and determines whether it is inside a given polygon L for each area in R . With those preprocessing steps, this algorithm then decides whether it is inside polygon L by binary search in R for each point in a given point set S . The time complexity of the algorithm in the worst case is max (O(n log m) ,O(tm log m)), where n is the number of points in set S , m is the number of vertexes of polygon L , and t is the number of different X ordinate values of all polygon L vertexes. In general cases, this algorithm is more efficient than the existing algorithms.