Calcul d'une enveloppe non
convexe d'un nuage de points
Introduction
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.
Le schéma suivant donne l'exemple d'un
tel contour :
L'objet de ce document est de présenter
un algorithme rudimentaire de calcul d'une telle enveloppe. Bien entendu, cette
enveloppe sera nécessairement choisie "arbitrairement" parmi
l'ensemble des candidates (le choix sera la conséquence de la règle de production
définie par l'algorithme) puisqu'un nuage de points est enveloppé par plusieurs
polygones, comme le montre l'exemple ci-dessous :
Calcul de l'enveloppe convexe
d'un nuage de points
Le calcul de l'enveloppe convexe d'un
nuage de points est possible dans un système d'information géographique
standard, à l'aide d'une méthode basique exploitant la fonctionnalité de fusion
de polygones offerte par tous les systèmes d'information géographique.
L'algorithme est fondé sur un constat
simple : l'enveloppe convexe coïncide avec la fusion de tous les triangles
définis par trois points appartenant au nuage de points, comme le montre
l'exemple suivant, dans lequel nous n'avons toutefois pas représenté tous les
triangles pour des raisons de lisibilité :
L'algorithme consiste donc à calculer
le triple produit cartésien du nuage de points, afin de calculer tous les
triangles qu'il suffit ensuite de fusionner avec la méthode standard de fusion
de polygones proposée par le système d'information utilisé.
Cette méthode, efficace dans son
principe, reste cependant très lourde de par le calcul du produit cartésien,
très consommateur en temps d'exécution et en mémoire.
Calcul d'une enveloppe non
convexe d'un nuage de points
L'algorithme de calcul d'une enveloppe
non convexe d'un nuage de points est dérivé de la méthode standard de calcul de
l'enveloppe convexe d'un nuage de points que nous venons de présenter.
Pour obtenir une enveloppe plus
"fine", non convexe, il suffit en effet de se contenter de calculer
et de fusionner les seuls triangles situés au voisinage immédiat du point
courant du nuage, comme on le voit dans l'exemple présenté figure 4.
L'ensemble des triangles calculés au
voisinage immédiat de chaque point dessine en effet une enveloppe qui suit le
contour intuitif représenté par les points, et qui le suit de manière d'autant
plus précise que le rayon de sélection utilisé pour calculer les triangles de
voisinage sera petit. Toutefois, ce rayon ne devra pas être trop petit, au
risque de ne sélectionner aucun point permettant le calcul d'un triangle.
Toute la difficulté du procédé consiste
à imaginer une règle de calcul du rayon de capture, qui, en fonction de la
distribution de points considérée et quelle que soit cette dernière, produise
dans tous les cas de figure une valeur de rayon de capture adaptée à la
situation -c'est à dire une valeur de rayon qui fournira une enveloppe non
convexe toujours convenable (la notion d'enveloppe non convexe convenable étant
par ailleurs non définie, non quantifiée et très fortement subjective. Nous ne
proposons pas de réponse à cette question. Toutefois c'est éviedemment sur ce
paramètre-là qu'il conviendra le cas échéant de jouer pour calculer un contour
plus ou moins fin.
Deux remarques s'imposent :
i)
la méthode de calcul d'enveloppe proposée est susceptible de
provoquer l'apparition de "trous" lors de la fusion des triangles,
lorsque la distribution sera par trop irrégulière, trous dont il faudra ensuite
se débarrasser pour calculer un polygone final plein. Nous présenterons une
méthode utilisable pour combler les trous d'un polygone
ii)
pour la même raison, la méthode de calcul d'enveloppe
proposée est susceptible de produire un polygone final non connexe, c'est à
dire un polygone constitué de la fusion de polygones connexes disjoints. Nous
proposons dans ce cas, arbitrairement, de ne conserver que le polygone entrant
en intersection avec le centre de gravité de la distribution des points, s'il
existe (car ce polygone peut ne pas exister).
Choix
d'un rayon de capture
L'idéal est que chacun des points de la
distribution puisse apporter une contribution à la production de l'enveloppe.
Le rayon de capture devra donc permettre, pour chacun des points de la
distribution, la sélection d'au moins deux points distincts.
Nous introduisons à cette fin :
Dmin = la plus
petite distance d'un point de la distribution au premier point distinct le plus
proche de la distribution
Dmax = la plus
grande distance d'un point de la distribution au premier point distinct le plus
proche de la distribution
Le choix d'un rayon de capture égal à Dmax permettra à coup sûr de
sélectionner un point distinct. Rien n'indique qu'il permette d'en sélectionner
deux. Toutefois, dans le cas d'une distribution suffisamment régulière, c'est à
dire dont les deux paramètres Dmax et
Dmin restent suffisamment proches, le
choix de Dmax permettra en général de
sélectionner plusieurs points.
Nous recommandons le choix d'une valeur
r = aDmin + bDmax, avec a+b=1
Vérifier pour chacune des valeurs de r que chacun des disques de rayon r centrés sur les points de la
distribution sélectionne bien deux autres points est une procédure possible
mais lourde.
Nous préconisons de lancer directement
l'algorithme avec, par exemple, (a,b)=(1/2,1/2) ou (a,b)=(3/4,1/4)
De toute façon, il n'existe pas de
valeurs fixes a et b utilisables systématiquement pour obtenir un résultat
conforme aux attentes de l'utilisateur, et nous ne proposons pas, faute d'en
avoir imaginée une, de méthode de détermination automatique de deux telles valeurs
""convenables"" que l'on pourrait calculer en fonction de
la distribution des points.
Une
méthode pratique utilisable pour combler les trous d'un polygone
Soit P un polygone à trous.
Soit R un rectangle qui contient P, le
plus petit des rectangles contenant P par exemple.
Tous les systèmes d'information
géographique offrent une fonctionnalité standard de calcul de la différence
entre deux polygones. On peut donc calculer D = R - P
D est un polygone non connexe qui peut
être décomposé en une liste de polygones connexes (fonctionnalité standard d'
"explosion" proposée par tout S.I.G.). Chacun de ces polygones
connexes sera utilisé pour combler un trou du polygone initial P si et
seulement il n'entre pas en intersection avec le contour du rectangle R (le calcul
du contour fait également l'objet d'une méthode standard proposée par la
plupart des S.I.G.).
Tous les éléments ont été présentés qui
permettent d'écrire un premier algorithme de calcul d'une enveloppe non convexe
d'une distribution de points.
Auteur : Christophe Faivre Duboz
Date
: 16/04/1996