Structures de données dans un SIG

Ajouter des liens
Un article de Wikipédia, l'encyclopédie libre.

Un Système d'information géographique contient des données alphanumériques et des données spatiales. Dans un SIG, les données sont stockées soit sous format vectoriel, soit sous format raster[1],[2]. Le format vectoriel gère les points, les lignes et les polygones, les vecteurs sont complétés par des informations alphanumériques. Les données raster sont stockées sous forme de cellules formant une maille. Ces données sont aussi complétées par des données alphanumériques telles que la moyenne, le max, le min, la somme de grandeurs géographiques[3].

Pour indicer les données vectorielles on utilise les arbres ou les graphes[4],[5].

Arbres[modifier | modifier le code]

Parmi les arbres, un Quad tree[6] est une structure en forme d'arbre dans laquelle chaque nœud a exactement quatre enfants. Les Quad trees sont généralement utilisés pour partitionner un espace à deux dimensions par divisions successives en quatre quadrants. Il sert à l'indexation spatiale, de même que l'octree qui est un arbre analogue.

En informatique, un kd-tree (abréviation pour arbre à k-dimensions) est une structure de données en forme d'arbre binaire dans lequel chaque nœud est un point dans un espace à k-dimensions.

Un R-tree est une structure de données similaire à un B-tree, utilisée comme méthode d’accès spatiale, c'est-à-dire servant à indexer des informations multi-dimensionnelles, comme par exemple, les coordonnées (x,y) de données géographiques.

Un vp-tree (« vantage point tree ») est un arbre BSP qui sépare les données dans un espace métrique en choisissant une position dans l'espace, le point privilégié (« vantage point ») et en divisant les points de données en deux partitions : ceux qui sont à une distance du point privilégié inférieure à un seuil donné, et ceux qui ne le sont pas. En répétant cette procédure pour partitionner les données en ensembles de plus en plus petits, une structure d'arbre est créée dans lequel des voisins dans l'arbre ont de grandes chances d'être des voisins dans l'espace[7].

D'autres structures en arbre sont utilisées comme les M–way vp–tree, Multi-vantage-point tree et les M tree.

Graphes[modifier | modifier le code]

  • Graphe de voisinage

Un graphe de voisinage sert à visualiser les relations de voisinage. Les voisins peuvent être des régions contiguës ou non, ou des points, la relation peut être pondérée par une distance. Il existe plusieurs types de graphes : le graphe du plus proche voisin relatif, le graphe de Gabriel, la triangulation de Delaunay[8],[9], etc.

Autres[modifier | modifier le code]

Un rectangle à limite minimum ou une boite à limite minimum (« Minimum bounding rectangle » ou « Bounding box »)[10] est l'étendue maximum d'un objet géographique dans un système de coordonnées.

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]


Références[modifier | modifier le code]

  1. ↑ CRDP Versailles, « Les Systèmes d’Information Géographiques libres » (consulté le )
  2. ↑ [PDF]Laetitia Perrier Brusle, « SIG : Théorie, définition, applications » (consulté le )
  3. ↑ coastlearn, « Formats raster et vectoriel » (consulté le )
  4. ↑ (en) Ajay Gupta, « Spatial Data Structures, Computations » (consulté le )
  5. ↑ [PDF]Jean-François Gleyze, « Réseau, transport, mobilité et analyse spatiale » (consulté le )
  6. ↑ [PDF](en) Petr Kuba, « Data Structures for Spatial Data Mining » (consulté le )
  7. ↑ (en) Peter N. Yianilos « Data structures and algorithms for nearest neighbor search in general metric spaces » () (lire en ligne, consulté le )
    — « (ibid.) », dans Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, Society for Industrial and Applied Mathematics Philadelphia, PA, USA, p. 311–321
  8. ↑ [PDF](en) Remco c. Ve Ltkamp, « The ?-neighborhood graph » (consulté le )
  9. ↑ Marie-Aude Aufaure, Laurent Yeh, Karine Zeitouni, « Fouille de Donnees Spatiales » (consulté le )
  10. ↑ [PDF](en) Krzysztof Koperski, Junas Adhikary, Jiawei Han, « Spatial Data Mining : Progress and Challenges : Survey paper » (consulté le )

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) Harvey Miller et Jiawei Han, Geographic Data Mining and Knowledge Discovery, Boca Raton, CRC Press, , 458 p. (ISBN 978-1-4200-7397-3).Document utilisé pour la rédaction de l’article
  • (en) Yee Leung, Knowledge Discovery in Spatial Data, Heidelberg, Springer, , 360 p. (ISBN 978-3-6420-2664-5)
  • (en) Hillol Kargupta, Jiawei Han, Philip Yu, Rajeev Motwani et Vipin Kumar, Next Generation of Data Mining, CRC Press, , 3e éd., 605 p. (ISBN 978-1-4200-8586-0)
  • Franck Guarnieri et Emmanuel Garbolino, Systèmes d'information et risques naturels, Paris, Presses des MINES, , 251 p. (ISBN 978-2-911762-52-9, lire en ligne)

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Structures_de_données_dans_un_SIG&oldid=202493104 ».