Les algorithmes de l’Institut d’Analyse Géographique
Rubrique dirigée par Christophe
Faivre-Duboz
Présentation d'algorithmes permettant de contrôler l'intersection de
deux objets géographiques
Au-delà de la seule consultation visuelle des données,
l'intérêt d'une base de données géographique réside en grande partie dans la
mise en œuvre d'analyses et de traitements (requêtes, jointures) de nature
géographique, c'est à dire qui exploitent les relations géographiques entre
objets.
De
telles analyses reposent notamment sur la capacité à déterminer de manière
automatique si deux objets graphiques géopositionnés présentent une
intersection.
L'objet de ce document est de
décrire quelques-uns des algorithmes théoriques (non optimisés) qui permettent
de réaliser un tel contrôle.
Un
algorithme simple de calcul de route
Le
calcul et l'optimisation d'itinéraires est une application naturelle des
systèmes d'information géographique.
Nous
présentons dans cet article un algorithme élémentaire de calcul d'un chemin reliant
un point à un autre le long d'un réseau existant.
Cet
algorithme fait appel aux fonctionnalités les plus générales d'un SIG, comme le
contrôle de l'intersection point-polyligne.
Calcul d'une enveloppe non convexe d'un nuage de points
Lorsque l'on dispose d'un nuage de points géopositionnés, il peut être utile de dessiner le contour défini par ce nuage de points. Nous ne parlons pas ici de l'enveloppe convexe de l'ensemble des points, mais d'un contour plus fin, dont l'approximation est rendue possible par la nature de la distribution des points, supposée suffisamment dense et régulière.
Un
algorithme simplifié de jointure spatiale point-point
Une application classique des systèmes d'information géographique consiste à associer de manière automatique à chaque élément d'une distribution ponctuelle le ou les éléments les plus proches appartenant à une autre distribution.
Nous proposons ici une méthode simplifiée de jointure spatiale point-point.
Considérons un polygone connexe et une polyligne. Chacun des deux
objets est défini par la liste ordonnée des points qui constituent les sommets.
Nous
proposons dans le présent document un algorithme simple permettant de découper
le polygone à l’aide de la polyligne.
Pour toute information
concernant les articles du site de l’Institut d’Analyse Géographique : iag@iag.asso.fr