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.

 

Nous nous limitons, dans ce document, aux trois classes d'objets graphiques suivantes :

 

·         les points,

·         les polylignes

·         les polygones connexes.

 

 

 

Intersection point - point

 

Le contrôle de l'intersection de deux points (X1,Y1) et (X2,Y2) se ramène à la comparaison des valeurs numériques de leurs coordonnées. Les deux points vérifieront la relation d'intersection si et seulement si X1=X2 et Y1=Y2

 

 

Intersection point - segment de droite

 

Le contrôle de l'intersection d'un point (X,Y) et d'un segment de droite défini par les deux points (X1,Y1) et (X2,Y2) se ramène à la vérification des deux conditions suivantes :

 

i) X est compris dans l'intervalle X1, X2  (ou bien : Y est compris dans l'intervalle Y1, Y2)

ii) (X,Y) vérifie l'équation de la droite (X1,Y1)(X2,Y2)

 

 

Intersection point - polyligne

 

Une polyligne (ligne brisée) est définie par une liste de points. Le contrôle de l'intersection d'un point (X,Y) et d'une polyligne définie par les n points (X1,Y1), (X2,Y2),..(Xn,Yn) se ramène à vérifier successivement l'intersection entre le point (X,Y) et chacun des (n-1) segments de droite constituant la polyligne. L'itération s'arrête lorsqu'une intersection est détectée ou lorsque l'ensemble des segments ont été testés.

 

 

Intersection segment de droite- segment de droite

 

Deux segments de droite non parallèles définis par les points (X1,Y1), (X2,Y2) d'une part, (X3,Y3), (X4,Y4) d'autre part, ont un point d'intersection si et seulement si

 

i)   les deux droites définies par (X1,Y1), (X2,Y2)  et (X3,Y3), (X4,Y4)  ont un point en commun (X,Y)

ii)  X est compris dans l'intervalle X1, X2 (ou bien : Y est compris dans l'intervalle Y1, Y2)

iii) X est compris dans l'intervalle X3,X4 (ou bien : Y est compris dans l'intervalle Y3,Y4)

 

Deux segments de droite parallèles entreront en intersection si et seulement si :

 

i) les deux droites (X1,Y1), (X2,Y2)  et (X3,Y3), (X4,Y4) ont la même ordonnée à l'origine,

ii) les intervalles (X1,X2) et (X3,X4) ont une intersection non vide (ou : les intervalles (Y1,Y2) et (Y3,Y4) ont une intersection non vide)

 

 

Intersection polyligne - polyligne

 

Le contrôle de l'intersection entre deux polylignes se ramène à contrôler l'intersection de segments de droite en contrôlant un par un l'intersection de chacun des segments composant la première polyligne avec chacun des segments composant la deuxième polyligne. L'itération s'arrête si une intersection est détectée ou si la totalité du produit cartésien a été parcourue.

 

 

Intersection point - polygone connexe

 

L'algorithme de contrôle de l'intersection d'un point (X,Y) et d'un polygone connexe défini par n points (X1,Y1) (X2,Y2)..(Xn,Yn) est fondé sur un constat graphique préliminaire très simple :

Une demi-droite verticale issue d'un point intérieur à un polygone convexe rencontre le contour de celui-ci en un point (cf. fig.1)

 

Une demi-droite verticale issue d'un point extérieur à un polygone convexe rencontre le contour de celui-ci en zéro ou deux points (cf. fig.2)

 

 

La même opération appliquée à un polygone connexe mais non convexe semble mettre en évidence une règle plus générale : un point est intérieur (respectivement extérieur) à un polygone connexe si et seulement si la demi-droite verticale tirée à partir du point rencontre le contour du polygone en un nombre impair (respectivement pair) de points (cf. fig. 3).

 

 

En poursuivant la réflexion, on constate qu'il peut être difficile de compter le nombre de points d'intersection lorsque l'un des côtés du polygone est lui-même un segment vertical (cf. fig. 4). Le choix d'une demi-droite de pente distincte de chacune des pentes des côtés du polygone permet d'exclure cette possibilité.

 

 

De plus, on s'aperçoit rapidement que la règle que nous avons imaginée tombe en défaut dès lors qu'il existe au moins un point d'intersection "double" (c'est à dire un point d'intersection qui coïncide avec l'un des sommets du polygone) (cf. fig. 5).

Il convient donc de choisir une droite dont la pente sera distincte de chacune des pentes des côtés du polygone, et qui ne rencontrera aucun des sommets du polygones.

 

Cette précaution permet d'assurer un résultat correct.

 

Enfin, le cas de l'intersection du point avec l'un des côtés du polygone peut être écarté au départ, pour distinguer une intersection stricte d'une intersection avec le contour du polygone.

 

Ces éléments construits à partir d'une approche intuitive et à partir de constats visuels permettent de construire un algorithme efficace (mais qui est loin d'être le mieux optimisé pour un traitement informatique).

 

Nous décrivons ci-dessous l'algorithme que nous venons de définir :

 

Soit (X,Y) un point et { (X1,Y1) , (X2,Y2) , … , (Xn,Yn) } un polygone connexe à  n sommets (chacun des sommets est bien entendu distinct d'un autre).

Nous commençons par vérifier si (X,Y) appartient à l'un des segments (Xi,Yi), (Xi+1,Yi+1) auquel cas nous avons terminé.

Si ce n'est pas le cas, nous calculons et plaçons dans une liste les n-1 pentes des segments de droite (Xi,Yi), (Xi+1,Yi+1).

Nous calculons et ajoutons à la liste les n pentes des droites (X,Y) (Xi,Yi).

La liste que nous venons de constituer est triée par ordre croissant (ou décroissant), et nous définissons la pente p comme la moyenne arithmétique des deux premières pentes distinctes de la liste triée.

Le segment de droite S de pente p issu du point (X,Y) et dont l'autre extrémité a pour abscisse le nombre max{X1, X2, .., Xn} vérifie les conditions requises pour appliquer la règle mise en évidence.

A l'aide d'une itération, nous vérifions si le segment de droite S entre en intersection avec chacun des segments qui constituent le polygone, et incrémentons un compteur (initialement nul) dans ce cas.

 

Le test de parité de la valeur finale du compteur permet de conclure.

 

Intersection polyligne - polygone connexe

 

La vérification de l'intersection d'une polyligne et d'un polygone connexe se borne à vérifier en premier lieu si l'un des segments composant la polyligne a une intersection avec l'un des côtés du polygone (Fig. 6). Si ce n'est pas le cas, il convient alors de vérifier si l'un des noeuds de la polyligne est en intersection avec le polygone. A défaut, on conclut que la polyligne n'entre pas en intersection avec le polygone.

 

Intersection polygone connexe - polygone connexe

 

L'intersection entre un polygone connexe et un polygone connexe a lieu si l'un des côtés du premier polygone entre en intersection avec l'un des côtés du deuxième polygone, ou si l'un noeuds du premier polygone entre en intersection avec le deuxième polygone.

 

 

Auteur : Christophe Faivre Duboz

Date    : 21/11/2001