One of the most basic of spatial operations is that of determining whether a given point lies inside a polygon. More generally the problem extends to the case of multiple points and polygons, with the problem being to assign every point to the correct polygon. Related problems include line in polygon and polygon in polygon tests. A fast initial screening approach is to check whether a point (or line, polygon) lies in the polygon’s MBR. However, the standard algorithm for determining PIP in the vector model (known as the semi-line algorithm) is to extend a line vertically upwards (or horizontally, e.g. to the right) and then count the number of times this line crosses the polygon boundary. If the line crosses the boundary an odd number of times it lies inside the polygon. This is true even when the polygon is concave or contains holes. A number of special cases need to be considered, as illustrated in Figure 4‑13, below. These include points that lie on the boundary or at a vertex, and points that lie directly below a vertical segment of the polygon boundary. A useful discussion of PIP algorithms and related procedures is provided in Worboys and Duckham (2004, pp 197-202).
If the given point lies on the boundary or at a vertex of the polygon there is a further difficulty, since a unique assignment rule could prevent the point from being allocated to any polygon. Solutions to such cases include: assigning the point to the first polygon tested and not to any subsequent polygons; randomly assigning the point to a unique polygon from the set whose boundary it lies on; reporting an exception (non-assignment); assigning a weight value to the point (e.g. 0.5 on a boundary or 1/n at a vertex, where n is the number of polygons meeting at that vertex).
Figure 4‑13 Point in polygon — tests and special cases
Where the PIP process is one of overlaying, the procedure within a GIS will typically append attribute data from the polygon to the point, although this may be in accordance with user-selectable transfer rules (e.g. sum or average a particular field). ArcGIS includes two PIP-related topology rules: (i) point must be properly inside polygon; and (ii) point must be covered by boundary of polygon (i.e. must be exactly on the boundary). These are two of 16 main vector topology rules supported within ArcGIS for combinations of point, line and polygon features.
A second PIP algorithm of similar computational complexity, but requiring trigonometric operations in its standard form (so more processor intensive) is known as the winding number method. In this procedure a line is extended to each vertex of the polygon from the sample point in turn (traversing anticlockwise). If the sum of the angles from the point to the vertices, vi, is 0 the point lies outside the polygon, otherwise it lies inside or on the polygon. To clarify this procedure, let the polygon have n vertices vi=v1,v2,v3,… vn=v0 and consider a unit vector from a sample point, p, to each vertex in turn. Define the (signed) angle at p between the vectors from p to vi and vi+1, as θi. Then compute the winding number:
If wn=0 the point lies outside the polygon, otherwise it lies inside or on the polygon boundary. With some adjustment the algorithm can avoid calculating the angle and result in a computation that is as fast, or faster than crossing methods (tests suggest 20-30% faster for many non-convex polygons). It is also more general, in that it applies to cases where polygons are not simple, i.e. self-crossing of the polygon boundary is permitted.
The above addresses the issue for the case of a single polygon and for multiple non-overlapping contiguous polygons. With overlapping polygons, which is supported for example within the Manifold GIS, then unique allocation is not assured. Furthermore, if the sample region is not completely covered by polygons sample points may fall into no polygon. Similar issues arise with raster representation of points and polygons (as zones of continuous fields) but the problem of locating points inside zones is far simpler, whilst the allocation issues remains.