Map Overlay Problem

In this article, we will be exploring the Map Overlay Problem which is a core problem in Computational Geometry. We have explored simple variants of Map Overlay Problem.

Table of contents:

1. Geographic Information System
2. Map Overlay Problem
3. Point in Polygon
4. Line on Line
5. Line in Polygon
6. Polygon in Polygon
7. Line Segments
8. Plane Sweep Technique
9. Applications of Map Overlay
10. Conclusion

Before we discuss that we shall discuss what is (GIS) Geographic Information System.

Geographic Information System

In a geographic information system (GIS), information about countries, mountains, rivers, vegetation types at different locations, population densities, and rainfall is stored. Cities, roads, railways, electricity lines, and gas pipes, among others, can also be stored in caves.

The GIS is capable of extracting information about certain geographical areas and, in particular, the relationship between alternative types of data. There is so much data that efficient algorithms are required to deal with it.

For example, a biologist may want to figure out how average rainfall correlates with particular types of plants, and a civil engineer may use a GIS to determine whether there are gas pipes underneath a lot where excavation work is planned.

Map Overlay Problem

A map can be considered a 2D spatial structure composed of nodes, chains, regions, and subregions that divide a plane. As the name implies, map overlay refers to overlaying two or more maps to produce one resultant map. It takes in more than one map as input and produces one map as output. Due to intersections between those input maps, the output map contains new regions defined by those intersections as a result of the nodes on the input maps plus nodes generated by the intersections between the chains of the input maps together. Output maps consist of generating and relating structures. Our goal is to find intersection points between two sets of line segments (such as regions boundaries) to solve map overlay questions.

The process of obtaining the output map can be divided into four steps:

1. Find the new node at the intersection of the input chains.
2. Split the chains at the new nodes to form the new chains.
3. The new regions need to be formed, and boundaries need to be contained.
4. Establish overlay relationships between the input and output maps.

The first step takes the most time. Many algorithms have been developed to improve its performance, based on spatial analysis and computational geometry techniques.

A Few Map Overlay problems are:

1. Point in Polygon:

In This Problem we try to find if a point in a plane is present inside , outside or on the border of a Polygon. Practical example would be if any location(Monument , hotel etc) is present in a specific location.

In the above example we can say that point p lies in polygon D.

2. Line on Line:

In Line on Line overlay we try to detect if 2 lines intersect each other or not. A Real world example would be do 2 railway tracks intersect at any location?.

From the above image , we can clearly see A and B do not intersect , but lines C and D do intersect.

3. Line in Polygon:

As the Name Suggest we try to find whether a Line is Present inside a Polygon or outside it , whether it intersects the boundaries of the polygon or it doesn't.
A Real world example would be whether a river flows through a region , here the river could be denoted as a line and the region as a polygon.

4. Polygon in Polygon:

In This Overlay method we try to find whether a polygon is present on , inside or outside another polygon. An Example would be does one region contain another? Is One Locality present inside a city?

In this image we can see that Polygon P contains Polygon Q.

We can perform these operations using two methods , which are:

1. Vector based Overlay
2. Raster based Overlay

To Make things easy we will only be discussing Line in Line , i.e Line Segments problem and a advanced case of it.

Line Segments

Let's start by discussing the simplest form of map overlay , when two map layers are networks represented as collections of line segments. An example could be overlay of
map layer storing roads, railroads, or rivers at a small scale. This is called as Line Segment Problem , where we have to find the intersection of the lines.
The Plane Sweep Technique can be used to solve this problem.

Plane Sweep Technique

Imagine that a horizontal line passes over the plane from top to bottom, finding intersections as it moves. Basically the sweeping line starts at the top and calculates the intersections as it descends, finding all intersections.

Sub-Divisions

The Line Segments problem is a simple problem. The general structure of maps is more complex: they consist of labeled subdivisions of the plane. If we were creating a thematic map of forests in Canada, for example, the country would be divided into regions with titles such as "pine and deciduous", "birch and mixed", etc.

It is necessary to develop a suitable representation of a subdivision before calculating the overlay of two subdivisions. It is not such a good idea to store a subdivision as a collection of line segments.

Doubly-connected Edge List

Double-connected edge lists contain records for each face, edge, and vertex of a subdivision. Each record may also store additional information in addition to the geometric and topological information described shortly. As an example, if the subdivision represents a map of vegetation, then the edge list could store the type of vegetation associated with each face record.

Computing overlay of two Sub-Divisions

A modified version of Plane sweep algorithm is used to find the overlay of two subdivisions. As a first step, we copy the DCE list of the two subdivisions and convert it into a valid DCE list for Overlay (Merge them both) , then we apply the plane sweep algorithm , to which a few modifications are made, then we obtain the resultant DCE.

Time Complexity

A Fairly Common problem at the time when GIS were in infancy stages , a solution to this was given by Bentley and Ottmann , which had a runtime complexity of
O(nlogn+k logn). If our goal is simply to know whether there was any intersection between the lines , then we could use the method of Shamos and Hoey , which has a lower runtime complexity , it being O(nlogn).

Applications of Map Overlay

Using a suitable model, one can determine the best location for new schools, hospitals, police stations, industrial corridors, etc. Some Lands were better suited for schools than for offices.
For the site suitability overlay keep in mind some point

1. Selection of criteria
2. Reclassify the data as per the criteria
3. Overlay (Boolean or Map Algebra)
4. Extraction and representation of suitable site.

For example, a nuclear waste repository's site must be situated in an ideal geological area, not easily accessible, away from densely populated areas, and outside of the area designated for conservation.

Conclusion

Overlays are an integral part of any Geographic Information System, they help us find new features by overlaying existing features atop each other (superimposing them on each other). An example of an overlay is Google Maps, where we can view multiple features at once.

With this article at OpenGenus, you must have a strong idea of Map Overlay Problem.