Vector overlay
Vector overlay is an operation (or class of operations) in a geographic information system (GIS) for integrating two or more vector spatial data sets. Terms such as "polygon overlay", "map overlay", and "topological overlay" are often used synonymously, although they are not identical in the range of operations they include. Overlay has been one of the core elements of spatial analysis in GIS since its early development. Some overlay operations, especially Intersect and Union, are implemented in all GIS software and are used in a wide variety of analytical applications, while others are less common. Overlay is based  on the fundamental principle of geography known as areal integration, in which different topics (say, climate, topography, and agriculture) can be directly compared based on a common location. It is also based on the mathematics of set theory and point-set topology. The basic approach of a vector overlay operation is to take in two or more layers composed of vector shapes, and output a layer consisting of new shapes created from the topological relationships discovered between the input shapes. A range of specific operators allows for different types of input, and different choices in what to include in the  output. History. Prior to the advent of GIS, the overlay principle had developed as a method of literally superimposing different thematic maps (typically an isarithmic map or a chorochromatic map) drawn on transparent film (e.g., cellulose acetate) to see the interactions and find locations with specific combinations of characteristics. The technique was largely developed by landscape architects. Warren Manning appears to have used this approach to compare aspects of Billerica, Massachusetts, although his published accounts only reproduce the maps without explaining the technique. Jacqueline Tyrwhitt published instructions for the technique in an English textbook in 1950, including: Ian McHarg was  perhaps most responsible for widely publicizing this approach to planning in "Design with Nature" (1969), in which he gave several examples of projects on which he had consulted, such as transportation planning and land conservation. The first true GIS, the Canada Geographic Information System (CGIS), developed during the 1960s and completed in 1971, was based on a rudimentary vector data model, and one of the earliest functions was polygon overlay. Another early vector GIS, the Polygon Information Overlay System (PIOS), developed by ESRI for San Diego County, California in 1971, also supported polygon overlay. It used the Point in polygon  algorithm to find intersections quickly. Unfortunately, the results of overlay in these early systems was often prone to error. Carl Steinitz, a landscape architect, helped found the Harvard Laboratory for Computer Graphics and Spatial Analysis, in part to develop GIS as a digital tool to implement McHarg's methods. In 1975, Thomas Peucker and Nicholas Chrisman of the Harvard Lab introduced the POLYVRT data model, one of the first to explicitly represent topological relationships and attributes in vector data. They envisioned a system that could handle multiple "polygon networks" (layers) that overlapped by computing "Least Common Geographic Units" (LCGU), the  area where a pair of polygons overlapped, with attributes inherited from the original polygons. Chrisman and James Dougenik implemented this strategy in the WHIRLPOOL program, released in 1979 as part of the Odyssey project to develop a general-purpose GIS. This system implemented several improvements over the earlier approaches in CGIS and PIOS, and its algorithm became part of the core of GIS software for decades to come. Algorithm. The goal of all overlay operations is to take in vector layers, and create a layer that "integrates" both the geometry and the attributes of the inputs. Usually, both inputs are  polygon layers, but lines and points are allowed in many operations, with simpler processing. Since the original implementation, the basic strategy of the polygon overlay algorithm has remained the same, although the vector data structures that are used have evolved. Parameters are usually available to allow the user to calibrate the algorithm for a particular situation. One of the earliest was the "snapping or fuzzy tolerance", a threshold distance. Any pair of lines that stay within this distance of each other are collapsed into a single line, avoiding unwanted narrow "sliver polygons" that can occur when lines that should be  coincident (for example, a river and a boundary that should follow it "de jure") are digitized separately with slightly different vertices. Operators. The basic algorithm can be modified in a number of ways to return different forms of integration between the two input layers. These different "overlay operators" are used to answer a variety of questions, although some are far more commonly implemented and used than others. The most common are closely analogous to operators in set theory and boolean logic, and have adopted their terms. As in these algebraic systems, the overlay operators may be "commutative" (giving the same  result regardless of order) and/or "associative" (more than two inputs giving the same result regardless of the order in which they are paired). Boolean overlay algebra. One of the most common uses of polygon overlay is to perform a suitability analysis, also known as a suitability model or multi-criteria evaluation. The task is to find the region that meets a set of criteria, each of which can be represented by a region. For example, the habitat of a species of wildlife might need to be A) within certain vegetation cover types, B) within a threshold distance of a water  source (computed using a buffer), and C) not within a threshold distance of significant roads. Each of the criteria can be considered "boolean" in the sense of Boolean logic, because for any point in space, each criterion is either present or not present, and the point is either in the final habitat area or it is not (acknowledging that the criteria may be vague, but this requires more complex fuzzy suitability analysis methods). That is, which vegetation polygon the point is in is not important, only whether it is suitable or not suitable. This means that the criteria can be  expressed as a Boolean logic expression, in this case, H = A and B and not C. In a task such as this, the overlay procedure can be simplified because the individual polygons within each layer are not important, and can be dissolved into a single "boolean region" (consisting of one or more disjoint polygons but no adjacent polygons) representing the region that meets the criterion. With these inputs, each of the operators of Boolean logic corresponds exactly to one of the polygon overlay operators: intersect = AND, union = OR, subtract = AND NOT, exclusive or = XOR. Thus , the above habitat region would be generated by computing the intersection of A and B, and subtracting C from the result. Thus, this particular use of polygon overlay can be treated as an algebra that is homomorphic to Boolean logic. This enables the use of GIS to solve many spatial tasks that can be reduced to simple logic. Lines and points. Vector overlay is most commonly performed using two polygon layers as input and creating a third polygon layer. However, it is possible to perform the same algorithm (parts of it at least) on points and lines. The following operations  are typically supported in GIS software: Implementations. Vector Overlay is included in some form in virtually every GIS software package that supports vector analysis, although the interface and underlying algorithms vary significantly.