Polygon Operations

Point-in-Polygon

The point-in-polygon operation determines whether a specific point is in a specific polygon. In many situations, there are many points (e.g., events like a crime scene) distributed across a set of jurisdictions (e.g., neighborhoods in a city). One may be interested in either assembling all the crimes that occurred in each neighborhood (summary by neighborhood) or summarizing the neighborhood characteristics (e.g., poverty status, average education level) of a given kind of crime. One case adds the point information to the polygons, while the other attaches the polygon information to the crime event points.

From the calculation viewpoint, it is relatively straightforward to determine whether a particular point falls inside a particular polygon. One well-established algorithm runs a straight line from the point along an axis. This is just a way to simplify calculation. If this ray crosses the polygon boundary just once, the point is inside. Similarly, any odd number also means the point is inside. In general, an even number (including zero) means the point is not inside. The trick with an operational algorithm is to provide the correct connection between a cloud of points and a collection of polygons without checking each possible pair.

Polygon Overlay

Polygon overlay shares many characteristics with point-in-polygon, except that in overlay, both sources are sets of polygons. The goal of polygon overlay is to produce a new set of composite polygons that contain the boundaries and selected attributes of both sources. With this combined polygon geometry, attribute relationships between the two sources are established through merged attribute tables. This capacity is particularly important in superimposing very different themes, such as environmental risk with population characteristics or simply two distinct elements of the environment. Many environmental regulations require the technique of polygon overlay to evaluate the location of a sensitive zone against a source of risk. Ian McHarg's book Design With Nature popularized the technique of polygon overlay inside a general treatment of environmental design. Publication of this book is considered one of the founding events in the development of geographic information systems.

On the computational front, polygon overlay requires calculation of intersections. Wherever the boundaries around a polygon from one set cross the boundaries of a polygon from the other set, new nodes must be created. All boundary lines must then be reconnected through these nodes to form new closed polygons made up of portions of boundary lines from [Page 343]the source polygons and their combined attributes. Since the original delineation of polygon boundaries is never exact, generally some amount of fuzzy tolerance is defined. This allows points that are within the tolerance width to be merged so as to avoid slivers, which are narrow, elongated polygons reflecting uncertainty in the location of boundaries, rather than unique areas worthy of designation. These are discussed in more detail below.

...