CoastGIS’99: geomatics and coastal environment
à jour dans une base de données clients, recalage de données sur un référentiel, intégration de bases de données géographiques (BDG), contrôle
qualité, superposition de couches pour fusionner les géométries.
La distance linéaire de Fréchet
Pour comparer la géométrie de deux objets ponctuels, la distance euclidienne (d E ) s’impose. Par contre, pour comparer la géométrie de deux
objets linéaires, plusieurs distances et plusieurs outils de comparaison
de leur forme existent. En terme de précision de la position, les distances
entre ces objets sont les mesures les plus pertinentes. Plusieurs distances peuvent être employées (Devogele, 1997). Certaines reflètent
l'écart moyen entre les deux lignes (distance moyenne), d’autres représentent l'écart maximum entre les deux lignes (distance maximum).
La distance de Fréchet est une distance maximum entre deux lignes orientées. Elle s’appuie sur la propriété suivante : toute polyligne orientée
est équivalente à une application continue f : fa, b]—>V où a, b e 9Î,
a soit f : [a, a ] ® V et g : [b, b’] ® V’ deux polylignes et II II la norme
usuelle.
d F (J,g) inf„
:|01] Aaal
m ax te[01] |/(or([))-g(/î(t))||
/HO.lMIb.b']
Une illustration intuitive de la distance de Fréchet est la suivante : un
maître et son chien suivent deux chemins. Ils avancent ou s’arrêtent à
volonté, indépendamment l’un de l’autre, mais ils ne peuvent pas revenir sur leurs pas. La distance de Fréchet entre ces deux chemins est la
longueur minimale de la laisse qui permet de réaliser une progression
de concert satisfaisant ces conditions.
La distance de Fréchet a l’avantage de calculer la distance uniquement
sur des couples de points qui auraient pu être mis en correspondance
visuellement. La distance de Fréchet est donc très proche d’une distance
maximum visuelle entre deux lignes. Hélas, la programmation de cette
distance est complexe. Un algorithme d’ordre O(n.m.log
2 (n.m)) où n
et m sont les nombres de segments des polylignes, est donné dans Alt
& Gadau (1995).
La distance de Fréchet discrète
Néanmoins, un algorithme simple (O(n.m)) donnant une approximation discrète de la distance a été proposée dans Eiter & Mannila (1994)
pour des couples de polylignes (lignes composées de segments). Si nous
notons L 1 et L 2 un couple de polylignes, chacune composée d’une suite
ordonnée des extrémités des segments pour L 1 et
162
à jour dans une base de données clients, recalage de données sur un référentiel, intégration de bases de données géographiques (BDG), contrôle
qualité, superposition de couches pour fusionner les géométries.
La distance linéaire de Fréchet
Pour comparer la géométrie de deux objets ponctuels, la distance euclidienne (d E ) s’impose. Par contre, pour comparer la géométrie de deux
objets linéaires, plusieurs distances et plusieurs outils de comparaison
de leur forme existent. En terme de précision de la position, les distances
entre ces objets sont les mesures les plus pertinentes. Plusieurs distances peuvent être employées (Devogele, 1997). Certaines reflètent
l'écart moyen entre les deux lignes (distance moyenne), d’autres représentent l'écart maximum entre les deux lignes (distance maximum).
La distance de Fréchet est une distance maximum entre deux lignes orientées. Elle s’appuie sur la propriété suivante : toute polyligne orientée
est équivalente à une application continue f : fa, b]—>V où a, b e 9Î,
a soit f : [a, a ] ® V et g : [b, b’] ® V’ deux polylignes et II II la norme
usuelle.
d F (J,g) inf„
:|01] Aaal
m ax te[01] |/(or([))-g(/î(t))||
/HO.lMIb.b']
Une illustration intuitive de la distance de Fréchet est la suivante : un
maître et son chien suivent deux chemins. Ils avancent ou s’arrêtent à
volonté, indépendamment l’un de l’autre, mais ils ne peuvent pas revenir sur leurs pas. La distance de Fréchet entre ces deux chemins est la
longueur minimale de la laisse qui permet de réaliser une progression
de concert satisfaisant ces conditions.
La distance de Fréchet a l’avantage de calculer la distance uniquement
sur des couples de points qui auraient pu être mis en correspondance
visuellement. La distance de Fréchet est donc très proche d’une distance
maximum visuelle entre deux lignes. Hélas, la programmation de cette
distance est complexe. Un algorithme d’ordre O(n.m.log
2 (n.m)) où n
et m sont les nombres de segments des polylignes, est donné dans Alt
& Gadau (1995).
La distance de Fréchet discrète
Néanmoins, un algorithme simple (O(n.m)) donnant une approximation discrète de la distance a été proposée dans Eiter & Mannila (1994)
pour des couples de polylignes (lignes composées de segments). Si nous
notons L 1 et L 2 un couple de polylignes, chacune composée d’une suite
ordonnée des extrémités des segments pour L 1 et
162