Maps usually contain data from different sources (e.g., population, natural resources, cities, roads, infant mortality rate, etc.) When all the information is complied it is almost impossible to distinguish a certain type of data from the rest. Geographic Information Systems (GIS) usually organize maps into layers, each representing an aspect of the real world (de Hoop et al. 1993). Layers form thematic maps of a single type of data, allowing users to query each one separately.
There are many uses derived from overlaying subdivisions of the map, such as:
Overlaying layers of geographical data in order to perform queries involving several layers.
Area interpolation: given the population of a region A that overlaps a region B, estimate B’s population, assuming that it is proportional to the area of A that is covered by B.
Boolean operations among polygons: union, intersection, difference.
Windowing: operation for which a window is overlaid over the map and everything outside of the window is eliminated.
Buffering: it is made around points, lines and polygons. If the combined buffer of several elements is needed, it is done as a polygon overlay.
The Map overlay problem is the overlay of several input maps into a single output map. A map is a 2D spatial data structure, which is compounded by nodes (2D point where two or more lines intersect), chains (connected set of segments that start and end on two nodes), and regions (connected subset of the plane with polygonal boundary) that create a plane subdivision. The output map contains all the nodes in the input maps plus the nodes generated by the intersections of the chains of both maps together. The chains of the input maps are interrupted at the intersection points creating the output map’s chains; hence, the output map contains new regions defined by the intersections of the input regions. The map overlay problem consists of generating and relating the structures of the output map (Wu, 2005).
The process of obtaining the output map can be divided into four steps (Wu, 2005):
Determine the new nodes at the intersection points of the input chains.
Form the new chains by splitting the chains at the new nodes.
Form the new regions, and solve the containment of boundaries.
Determine the overlay relationships between the regions of the output map and those of the input maps.
The first step is the most time consuming. In order to improve its performance, many algorithms based on spatial analysis and computational geometry techniques, have been developed.Top
State Of The Art
A Brief History
A naive algorithm for overlaying maps would take each segment of one map and compare it with all the segments of the other looking for intersections. If each input maps have segments, the algorithm runs in time. But, this is low performance for the most typical input sizes (over 100,000 points). To improve the time it is convenient to follow a local processing principle, which means not checking for intersections between segments of distant regions because they do not intersect. It has been proven that a lower bound for the problem of finding all the intersection points between a set of n segments is , where k is the number of intersections, and it can be achieved using space.
Bentley and Ottman (1999) were first at applying the local processing principle for reporting segment intersection through the plane sweep algorithm. Their algorithm takes time and space. In 1988 Chazelle and Edelsbrunner created the first algorithm that runs in time and uses space (Chazelle & Edelsbrunner, 1992). Balaban (1995) developed the first optimum algorithm with respect to time and space complexity, which also works for curves. For some cases the segment intersection problem can be easier than the general problem. In the map overlay problem, as the maps are a planar subdivision of the space, all intersections will occur between a segment of the first map with a segment of the second one. This particular problem is also known as the red-blue line intersection problem, and a solution was found by Mairson and Stolfi (1998), before the general problem was optimally solved, taking time and space. In the case of maps as connected subdivisions, Finke and Hinrichs (1995) showed that it can be done in time.
Key Terms in this Chapter
Windowing: Overlaying a rectangular window to a map and discarding everything that it is not inside of the window.
Line Segments Intersection: Consists in computing the intersections between two sets of line segments. It is also known as the red-blue line segments intersection when one set contains red segments and the other contains blue segments. In this case, intersections between red and blue segments are reported.
Plane Sweep: A computational geometry technique, mostly used in finding intersections between lines. It consists of moving a line across a plane while stopping at certain events stored in a priority queue. The events are then taken according to their priorities. A binary search tree is also used to represent the state of the line at each moment. The problem is partially solved for all the area that has already been swept by the line at each event. It is completely solved when the line finishes with the last event.
Subdivision Overlay: It is the process of generating an output plane subdivision from overlaying two or more input plane subdivisions. A plane subdivision is a set of points, lines, and the regions determined by such points and lines. The output subdivision must contain all the points from the input maps plus the points of intersection between the input subdivision segments. The lines in the output subdivisions will be those made up by the input lines divided at the intersection points and the input lines that do not intersect. The output regions will be the union and intersection of all the input regions.
Combined Buffer: Buffers are generated around points or lines. To obtain the combined buffer of two or more points and/or lines, the unions of the generated buffers for each one is computed.
Map Overlay: Overlay two or more thematic maps obtaining a single output map.