Discussion :

[Benoit_T]

Bonjour,

Voici le problème auquel je suis confronté:

Je dispose d'un vecteurs de points. Chaque points est caractérisé par des coordonnées cartésiennes x et y. Ce vecteur contient tout de même la bagatelle de 15 millions d'éléments ...

Je dois régulièrement chercher dans le vecteur les n points les plus proches selon la distance d1 de points A(x,y) en entrée de la méthode.
(d1(A,B)= |xA-xB|+|yA-yB|)


Actuellement je suis tenté de faire comme il suit:
Je maintiens un arbre binaire B qui contient les n points de distances minimales trouvés dans la liste. Chaque noeud du tas binaire forme un couple N(indice du point dans le vecteur, distance à A).
J'initialise mon tas binaire vide, je parcours mon vecteur de points.
- Si mon tas contient moins de n éléments, alors j'insère l'élément courant.
- Sinon, j'extrais l'élément N1 de distance à A maximale du tas. Si l'élément courant (point) de la liste a une distance à A inférieure, alors j'insère cette élément dans le tas et je retire l'élément de distance à A maximale dans le tas.

Ainsi, je n'effectue qu'un seul parcours de liste et qui plus est, la liste des points candidats est codé par un tas binaire qui offre des complexités plutôt correctes pour les opérations sur cette liste de candidats (extraction du maximum, insertion d'un nouvel élément, suppression d'un élément).

Mon problème est le suivant:
- Je parcours toute la liste à chaque recherche !
Je pense qu'il y a peut être possibilité de trier la liste pour pruner les espaces de recherche lors d'une requête, et ce indépendamment du point A en entrée. J'ai quelques doutes cependant. J'imagine que je ne suis pas le premier à rencontrer ce problème. Peut-être certains auront t'ils des solutions élégantes, plus rapide. Je précise que les coordonnées sont entières et bornées (minX, maxX, minY, maxY).

Cordialement,

[panda31]

Je vais essayer de reformuler ton problème pour mieux le comprendre moi-même .

p point caractérisé par ses coordonnées 2D (x,y)
V vecteur de grande taille contenant des points

Tu veux isoler ("régulièrement" comme tu dis) les couples de points les plus proches grâce au calcul de la distance.

Tu ne veux pas calculer toutes les distances une fois pour toutes (ordre N²)
En effet, si tu as N points, tu auras N² calculs.

As-tu des valeurs seuil ?
Quel est le problème final auquel tu es confronté ?

Dis-moi si j'ai dit des absurdités

[pseudocode]

Mon problème est le suivant:
- Je parcours toute la liste à chaque recherche !
Je pense qu'il y a peut être possibilité de trier la liste pour pruner les espaces de recherche lors d'une requête, et ce indépendamment du point A en entrée. J'ai quelques doutes cependant. J'imagine que je ne suis pas le premier à rencontrer ce problème. Peut-être certains auront t'ils des solutions élégantes, plus rapide. Je précise que les coordonnées sont entières et bornées (minX, maxX, minY, maxY).

En découpant ton espace en zones, tu peux tout d'abord réduire ta recherche aux points qui sont dans la même zone que A(x,y). Puis, si tu n'as pas ton compte de "n" points, étendre la recherche aux zones voisines, etc.

Il te faut donc une structure hiérarchique de découpage en zones, qui te permette de "dézoomer" progressivement autour du point A(x,y). Le découpage en zone peut être uniforme (structure Quad-Tree) ou non-uniforme (structure kd-tree).

[Benoit_T]

Tu ne veux pas calculer toutes les distances une fois pour toutes (ordre N²)
En effet, si tu as N points, tu auras N² calculs.

Le vecteur fait quelques fois autour de 15 millions de points, 15000000² = 2,25*10^16 ce qui fait, à raison de 4octets par valeur de distance une matrice de distance de ... 22,5 petaocets ...

As-tu des valeurs seuil ?
Quel est le problème final auquel tu es confronté ?

En fait je dispose de ce vecteur et dedans je "pioche" un sommet. Ensuite, je cherche dans la vecteur de points les n points les plus proches de ce sommet, c'est pas plus compliqué que ça !

[Benoit_T]

En découpant ton espace en zones, tu peux tout d'abord réduire ta recherche aux points qui sont dans la même zone que A(x,y). Puis, si tu n'as pas ton compte de "n" points, étendre la recherche aux zones voisines, etc.

Il te faut donc une structure hiérarchique de découpage en zones, qui te permette de "dézoomer" progressivement autour du point A(x,y). Le découpage en zone peut être uniforme (structure Quad-Tree) ou non-uniforme (structure kd-tree).

Intéressant ça, je vais y jeter un coup d'oeil, merci !

[panda31]

Le vecteur fait quelques fois autour de 15 millions de points, 15000000² = 2,25*10^16 ce qui fait, à raison de 4octets par valeur de distance une matrice de distance de ... 22,5 petaocets ...

Oui c'est pour cela que j'écrivais "Tu ne veux pas". Et c'est normal . Ce n'était pas une question

En fait je dispose de ce vecteur et dedans je "pioche" un sommet. Ensuite, je cherche dans la vecteur de points les n points les plus proches de ce sommet, c'est pas plus compliqué que ça !

Je comprends mieux maintenant. Des problèmes comme celui-ci, il ne faut pas s'y atteler de bon matin.

Quand je parlais de valeurs seuil, je pensais également à établir des zones.

Tiens nous au jus

[SpiceGuid]

Comme l'a déjà dit pseudocode tu as le choix entre un Quadtree et un KD-tree.
Vu le nombre d'éléments j'opterais pour un KD-tree car plus économe en mémoire.

L'inconvénient du Quadtree et du KD-tree c'est qu'aucun des deux ne te donne directement les n plus proches voisins. Par contre ils peuvent te donner facilement l'ensemble de tous les points inclus dans un rectangle. À toi de (re-)dimensionner ce rectangle (au besoin dynamiquement, au cours de la remontée dans l'arbre) pour t'assurer qu'il contienne bien les n points recherchés.

[bretus]

Bonsoir,

Comme l'a déjà dit pseudocode tu as le choix entre un Quadtree et un KD-tree.
Vu le nombre d'éléments j'opterais pour un KD-tree car plus économe en mémoire.

S'il a une répartition (sensiblement) homogène de ses points dans l'espace, un bête maillage reposant sur une grille régulière peut être suffisant...

C'est d'ailleurs plus économe pour la mémoire et plus facile à parcourir que les arbres cités. Aussi, c'est plus facile de trouver les mailles voisines d'une autre que les éléments voisin d'une feuille de l'arbre...

La version simple est la suivante :
- Choisir une taille de grille : nx,ny
- Numéroter l'ensemble de tes points : [1..NPT]
- Générer une liste des points dans chaque maille
=> Pour chaque point, l'ajouter à la liste des points de la maille concernée

Pour chaque maille, tu as un pointeur "direct" sur les points qu'elle contient via la liste que tu as généré.

Ensuite, prenons un point P(X,Y) pour lequel tu cherches le voisinage. Tu trouve la maille correspondant à ce point (I,J). Au besoin, tu récupères les mailles voisines de (I,J) (et les points qu'elles contiennent) si tu n'as pas assez de points dans (I,J)

Remarques :

- C'est pas très snobe comme méthode. Au diable l'élégance, faut que ça fonctionne et vite

- Je ne suis pas fan de ces arbres d'indexation spatiale. (La relation père fils de l'arbre que l'on traine ne sert pas à grand chose et complexifie la recherche de voisinage entre les points) Quitte à avoir une structure de données complexes, il faudrait au moins que celle ci possède la notion de voisinage...

- Quadtree et Kdtree ne sont utiles qu'en cas de répartition non homogène.

- Le "rattachement" des points, segment et surface à un "tree" est beaucoup plus couteux que le rattachement à une grille régulière.

- En cas de répartition non homogène des points, rien n'interdit de faire des grilles dans la grille là où c'est nécessaire. La notion d'arborescence est là, on la connait, mais on ne la parcourt pas systématiquement en mémoire. On a, pour chaque niveau de maillage, une indication sur le nombre d'éléments contenus dans une maille et un pointeur sur les éléments qu'elle contient.

Bye

ps : C'est quoi tes données? Répartition sensiblement homogène ou non? Répartition régulière par hasard (genre un point tout les 250m en x et en y)?

[Benoit_T]

ps : C'est quoi tes données? Répartition sensiblement homogène ou non? Répartition régulière par hasard (genre un point tout les 250m en x et en y)?

Merci pour cette réponse, cette approche me semble très intéressante. Le gain en temps de calcul semble conséquent, l'implémentation aisée et qui plus est la structure est économe en mémoire.

Concernant les données, il s'agit de coordonnées cartésiennes de sommets d'un graphe routier. A l'échelle française, mon graphe de travail contient tout de même 10 millions de sommets et 20 millions d'arêtes. A l'échelle Européenne, c'est carrément 20 millions de sommets et 100 millions d'arêtes. La répartition des sommets est relativement uniforme; si ce n'est qu'en zone urbaine, la densité de sommet par unité d'aire est nettement supérieure à la moyenne.

Cordialement,

[bretus]

De rien, content que ça t'aide!

Essaye peut être de faire un niveau spécifique pour les régions urbaines si vraiment.

Par contre, question bête, mais tu gagnerais pas plus de temps avec un SGBD géographique? Genre postgres/postgis? (ces bêtes là assurent elles même une indexation spatiale)

++

[souviron34]

ce que je proposerais (je l'ai déjà exposé ailleurs ici) c'est :

1. tout d'abord un tri simultané X,Y, une fois pour toutes :
   
   
   • en X croissant
   • pour X constant en Y croissant
   
   
   
2. Puis découper en "bin", c'est à dire évaluer une taille "raisonnable" de découpage en X, donnant un résultat relativement correct en taille (par exemple en France au km = 1000 points), et stocker dans une table l'adresse (je suppose que tu as une liste chaînée) du point correspondant (si ce n'est pas une liste chaînée tu stockes directement l'indice).
   
   
3. Enfin, chaque fois qu'on te demande le voisinage de (x,y) :
   
   • trouver le numéro de "bin" (simple division)
   • partir de ce point et explorer dans les 2 sens. On s'arrête dès que la distance en X devient supérieure à ta distance limite.

ça devrait être pas mal rapide..


Je le fais sur 300 à 500 000 points, et ça prend, sur un petit PC "normal", pas boosté du tout, moins de 1/10 seconde...