Quadtree Data Structures for Geographic Information Systems

RÉSUMÉ

Les systèmes d'information à référence spatiale peuvent devenir des outils très performants pour le traitement de grandes quantités de données spatiales acquises par télédétection ou par des techniques de cartographie classiques. Il faudra mettre au point des modèles ou des structures de données spatiales qui permettront l'interaction efficace des données représentées, dans les systèmes d'information à référence spatiale, sous forme de régions, de lignes et de points. Par modèles de données spatiales améliorés on entend notamment des structures hiérarachiques en mosaique, tels que des quadrants arborescents (quadtrees) de régions, de contours et de points. Les quadrants sont définis comme la décomposition récursive de l'espace, l'hétérogénéité spatiale des données imposant la résolution. Dans certaines conditions, les quadrants arborescents peuvent permettre de stocker et de traiter les données de façon très efficace. Des techniques liées à l'intelligence artificielle, telles les méthodes de recherche heuristique, peuvent utiliser les quadrants pour réduire l'espace de recherche ainsi que les besoins de calcul. Il est nécessaire de poursuivre la recherche non subordonnée à un type de machine particulier en vue d'identifier les modèles de données spatiales les plus appropriés.

SUMMARY

Geographic information systems can become powerful tools for handling large quantities of spatial data acquired by remote sensing and from conventional map sources. There is a need to develop spatial data models or structures that will permit the efficient interaction of data represented as regions, lines, and points in geographic information systems. Improved spatial data models include hierarchical tesselations, such as region quadtrees, edge quadtrees, and point quadtrees. Quadtrees are based on the recursive decomposition of space with the spatial heterogeneity of the data dictating the resolution. Significant data storage and processing efficiencies can be realized under certain conditions with quadtrees. Techniques in artificial intelligence, such as heuristic search procedures, can use quadtrees to reduce the search space and to minimize computational requirements. Machine-independent research is needed to identify the most appropriate spatial data models.