Un algorithme simplifié de
jointure spatiale point-point
Contexte
Considérons deux distributions
ponctuelles. Une application classique des systèmes d'information géographique
consiste à associer à chaque élément de l'une des distributions le ou les éléments
les plus proches appartenant à la deuxième distribution.
Un importateur automobile ayant acquis
un fichier de prospection voudra par exemple identifier la concession la plus
proche du domicile de chacun des prospects avant de lancer des opérations de
marketing direct ciblées.
Protocole
standard
Considérons donc deux tables de points.
Bien entendu, chacune des deux tables comporte un champ identifiant.
L'opération qui permet d'associer à
chacun des points de la première table le ou les points les plus proches
appartenant à la deuxième s'articule en trois étapes :
i) produit cartésien des deux tables :
le produit cartésien permet le calcul de la distance séparant un point de la
première table de chacun des points de la deuxième
ii) agrégation des données du produit
cartésien : l'agrégation des données, réalisée sur le champ identifiant de la
première table, permet d'obtenir la plus courte distance séparant un point de
la première table d'un point de la deuxième
iii) jointure entre la table obtenue en
ii) et le produit cartésien calculé en i), sur le critère d'identité des champs
identifiant les éléments de la première table et d'identité des valeurs de
distance. L'opération permet de mettre en ligne chaque point de la première
table avec les points successifs de la deuxième table qui réalisent la distance
la plus courte.
En pratique, le nombre de sites
"les plus proches" est souvent limité à 1 (même s'il peut
théoriquement être égal au nombre total d'éléments de la deuxième table), aussi
on peut se borner à réaliser une jointure incomplète qui abandonnera le
traitement en cours portant sur chaque enregistrement de la première table dès
lors qu'une correspondance aura été trouvée dans la deuxième table. Cette
opération associera à chaque point de la première table un point de la seconde qui vérifie le minimum de distance. Elle
porte le nom de jointure spatiale point-point.
Toutefois, le protocole décrit reste
intrinsèquement lourd et coûteux en ressources par la nature même des
traitements mis en œuvre (produit cartésien, groupement de données). Le
protocole sera d'autant moins performant que les tables manipulées contiendront
un grand nombre d'éléments. Nous proposons dans ce cas de lui substituer un
protocole plus léger et plus efficace.
Jointure
spatiale point-point par contrôle d'intersection point-polygone
Considérons une distribution ponctuelle
et un point appartenant à cette distribution. L'ensemble des points du plan qui
sont plus proches ou aussi proches du point considéré que de tout autre point
de la distribution délimite un polygone (dont certains côtés peuvent être
infinis si le plan de travail n'est pas borné). Nous appellerons ce polygone le
"secteur d'influence" du point donné.
Le secteur d'influence regroupe tous
les points qui peuvent être rattachés au point considéré lors d'une recherche
du point le plus proche dans la distribution. Le calcul du secteur d'influence
s'appuie sur le tracé des médiatrices des segments définis successivement par
le point considéré et chaque autre point de la table. Chaque médiatrice découpe
le plan autour du point étudié jusqu'à obtenir le tracé du secteur d'influence,
comme le montre la figure suivante :
Tous les secteurs étant définis, une
jointure spatiale point-point consiste alors seulement à comparer la position
d'un point du plan avec chacun des polygones et à s'arrêter dès qu'une
intersection est détectée. Ce protocole ne nous oblige pas à passer en revue la
totalité des points (examen exhaustif nécessaire pour le calcul des distances
dans le premier protocole), non plus qu'il ne contraint à exécuter les
opérations (coûteuses) d'agrégation de données et de jointure décrites
précédemment.
Le calcul préliminaire des secteurs
d'influence permettra donc d'obtenir un gain en rapidité d'exécution d'autant
plus intéressant que le nombre d'enregistrements à traiter sera élevé.
Auteur : Christophe Faivre Duboz
Date : 4/10/1997