Implementation and testing of variable scale topological data structures

Abstract

With the increase of the availability of large-scale geographic data set and the rise of widespread computer networks, such as the Internet, the need has arisen to be ableto transfer this data by means of these networks. The networks form the basis for a Geographic Information Infrastructure (GII), in which data users, data providers and data producers are connected with each other.There also exists the need to offer this data on several scales to end users, for example to get an overview of an area first. Because the geographical information are now sent by the computer networks and large-scale geographic information brings many data, data reduction must take place. This is to prevent that sending of the information takes too much time. Generalization of geographical information is a possible means to let this reduction take place.Generalization is the selection and simplification of detail appropriate to the scaleand or purpose of the map. The appliance of generalization demands that choices mustbe made with respect to which geographical objects are selected and simplified and how this selection and simplification must take place. Moreover, also the surroundings of the objects to be generalized, are often taken into account in the generalization process, which makes that the complete process even requires more time. This way, the complete process can not be carried out in real time.Earlier, reactive data structures, in which geographical information is stored in the computer with several levels of detail, have been proposed as a solution to allow the use of generalized large-scale geographical information in real time. So far, these data structures were using redundancy with respect to geometry. For this reason a new conceptual model has been developed, where a number of existing data structures have been combined into two new data structures, namely, the GAP face tree and the GAP edge forest (described in Van Oosterom, 2005). The complete structure is termed tGAP structure, inwhich tGAP stands for topological Generalized Area Partitioning.The tGAP structure has not been theoretically verified, nor implemented or tested. Therefore, the objective of this research is to theoretically verify the data structures and to test the data structures considering requirements such as loading time and storage capacity.To reach the objective literature study has been performed in the field of generalization, database management systems and the data structures. Moreover, a prototype has been built, with which the data structures have been implemented in a mainstream database management system (DBMS) with spatial data types. Literature study has shown that generalization is a key issue in the complete process of obtaining and processing geo-information and that using reactive data structures is asuitable option to offer the results of generalization within a GII in real time.The implementation of a prototype has shown, that it is possible to implement thedata structures in a mainstream DBMS. The data structures are implemented in Oracle Spatial, the DBMS, and by means of Apache, a web server, opened up to Google Earth, a geographical viewer. The data structures in the prototype make it possible to view thegeographical data interactively within the viewer independent from the size of the area to be loaded.The final conclusion must be, that with some workarounds and with some changes tothe proposed conceptual model, it is possible to implement the model as described in (Van Oosterom, 2005). With an implementation it becomes possible to show geographical data on a variable number of detail levels and the implementation shows that the data structures can provide the desired data reduction within a GII in real time.