Transcript M 1
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] ???