La structure de localisation utilisée comporte plusieurs niveaux. Au niveau le plus bas contient la triangulation de Delaunay de tous les points, ensuite chaque niveau contient la triangulation d'un echantillon aléatoire des points du niveau précédent. La localisation d'un nouveau point est effectuée en marchant dans une triangulation afin de déterminer le plus proche voisin du nouveau point à ce niveau ; puis la marche reprends à partir de ce voisin au niveau inférieur. L'utilisation d'échantillon assez petit (3 %) garanti un faible coût mémoire ; la marche et l'utilisation du plus proche voisin pour changer de niveau une convergence rapide pour localiser la requète.
La suppression est implémenté par dualité avec l'enveloppe convexe 3D en utilisant un effeuillage (shelling) partiel.
Last modified: Tue Jan 17 11:07:47 CET 2006 | Olivier Devillers | Logiciels |