Departamento de
Informática
Universidade
Federal de Viçosa
A more efficient map overlay method for Terralib
Vinícius Lopes Rodrigues
Marcus Vinícius Alvim Andrade
Gilberto Ribeiro de Queiroz
Mirella Antunes de Magalhães
Introduction
TerraLib: A Component Library for GIS
Development
Developed by: INPE, Tecgraf/PUC-Rio,
FUNCATE
Implementation of “Small GIS”
Terralib
Terralib has a geometric algorithms
module
Used for manipulation of spatial data
Contains all basic operations involving simple
geometric forms (Points, Lines, Polygons)
Spatial data are manipulated in a lower level
Terralib
Terralib has also a functional module
This module uses basic geometric
operations to build functions in a higher
level
Map Overlay
Description:
Is used to combine the information of two
maps
Calculates the geometrical overlay between
map polygons and joins the non-spatial
information of two maps
Map Overlay
Example:
Terralib’s Polygon Overlay
Basic operation for map overlay
Computes intersection, union or
difference of two polygons
Named TeOverlay – included in kernel
of Terralib
Based on Margalit and Knott’s algorithm
Terralib’s Polygon
Overlay
Terralib’s Polygon Overlay
The computation of the intersection
points on the boundaries is essential to
obtain the final result
These points are used to determine the
fragmentation of the boundary
The generated fragments are grouped
according to chosen operation
Terralib’s Map Overlay
Let M1 and M2 be two maps
Suppose that M1 has less polygons than
M2
b2
M1: blue
M2: red
a3
a1
a2
b1
Terralib’s Map Overlay
In Terralib, the original method proceeds
as the following:
for each polygon bi in M1, a spatial query on
the database is done, fetching all the
polygons on the map M2 which bounding
box intercepts the bi’s bounding box
b2
a3
a1
a2
b1
Terralib’s Map Overlay
The operation TeOverlay is applied to
determine the intersection between the
polygon ai and all polygons returned by the
query.
To execute the operation above, it is necessary
to determine the intersection points between
the borders of the polygons.
b2
a3
a1
a2
b1
Terralib’s Map Overlay
All the regions returned by the TeOverlay
operation are stored in the resulting map
Each computed polygon has attributes from
both the original polygons (maps)
Terralib’s Map Overlay
Considerations
This operation proceeds many spatial
queries on the database that implies a large
execution time
The same polygon of the map M2 could be
processed twice or more times
An alternative map
overlay
Developed to avoid the database
queries
The intersection points are found based
on the Bentley & Ottman’s plane sweep
algorithm.
An alternative map
overlay
The maps are full loaded from the
database to build two segments sets.
So, the intersection algorithm is used to
determine the intersection points
between the segments of these two
sets.
b2
a3
a1
a2
b1
An alternative map
overlay
After finding the intersection points, a
matrix is built to store them.
In this matrix, the position ( i , j )
contains the intersection points
between polygon bi from M1 and aj from
M2
a1
a2
a3
b2
b1
b2
p5
p1
p3
p5
p2
p4
p6
p6
p7
p7
p8
p8
a3
a2
a1
p2
p1
p3
p4
b1
An alternative map
overlay
In this version, TeOverlay was modified
to receive as parameter the intersection
points previously calculated
For each position of the matrix where
the list is not empty, the new version of
TeOverlay is called with the respective
polygons and their intersection points
An alternative map
overlay
Special case:
if a polygon a1 is “inside” another polygon
b1.
In this case, the list of intersection points is
empty but the polygons intersection is not.
To circumvent this case, the algorithm
checks if the polygons bounding box
intersect each other.
If they intersect, only a point-polygon
localization is needed
Results
Input Maps:
Number
Map
Number of
Regions
Number of
segments
M1
Cities MG
853
61237
M2
Cities MG (translated)
853
61237
M3
M4
M5
M6
Temperature MG
20
4659
Soil MG
3067
858696
Cities Brasil
5560
571747
Cities Brazil (translated)
5560
571747
Results
M1
M4
M3
M5
Results
M1 x M2
M1 x M4
M1 x M3
M5 x M6
Results
Time Results
Number
Time (ms)
Overlay
Intersections
Output
polygons
Terralib’s Alternative
M1 x M2
15382
3885
184516
25037
M1 x M 3
3678
1323
21591
18626
M1 x M4
39317
7437
433884
172007
M5 x M6
110232
25657
1554776
307913
Future Work
Implement a plane sweep based map
overlay
Based on Kriegel’s algorithm
Does not require database queries and
intersection points are determined as
result regions are generated
Questions
?
?
?
?
?
?
?
?
?
?
?
?
?
???
Vinícius Lopes
[email protected]
???