A cell-based point-in-polygon algorithm suitable for large sets of points

The paper describes a new algorithm for solving the point-in-polygon problem. It is especially suitable when it is necessary to check whether many points are placed inside or outside a polygon. The algorithm works in two steps. First, a grid of cells equal in size is generated, and the polygon is laid on that grid. A heuristic approach is proposed for cell dimensioning. The cells of the grid are marked as being inside, outside, or on the polygon border. A modified flood-fill algorithm is applied for cell classification. In the second step. points are tested individually. If the tested point falls into an inner or an outer cell, the result is returned without any additional calculations. If the cell contains the polygon border, it is possible to determine the local point position. The analysis of tithe complexity shows that the initialization is finished in O(n rootn) time, while the expected time complexity for checking an individual point is O(rootn), where n represents the number of polygon edges. The algorithm works with O(n) space complexity. The paper also gives practical results using artificial and real polygons from a GIS environment. (C) 2001 Elsevier Science Ltd. All rights reserved.