Discussion :

[dodup64]

Bonjour,

J'ai deux ensembles de points dans l'espace A et B. Je voudrais savoir quels sont les points de B qui sont proches de ceux de A (avec un seuil de distance).

J'ai implémenté un algorithme natif : je parcours tous les points de A et je calcules toutes les distances avec les points de B.

A et B étants très grands (5000 point en moyenne), cet algorithme est très long.

J'ai aussi essayé une autre méthode :
Je trouve une boite englobante de A (plus mon seuil de distance) et je cherche tous les points de B qui sont dans cette boite.

C'est mieux, mais je cherche un algorithme plus rapide.

Merci de m'aider

[PerlPicker]

Bonjour,

Il faut que tu organises les points d'un des ensembles dans une structure spaciale comme un quadtree ou un octree. Cette structure te permettra ensuite pour chaque point du deuxième ensemble de trouver ses points proches.

Tu peux regarder http://en.wikipedia.org/wiki/Kd-tree pour un algorithme et http://www.cs.wustl.edu/~suri/cs506/projects/quad.html pour un applet de demo d'un quadtree.

Bon courage.

[dodup64]

Merci,

C'est exactement ce que je cherchais.

[dodup64]

Ta solution marche bien dans un espace 2D mais quand on passe en 3D, on a un probleme. Il me semble que le tri n'est fait qu'en fonction des x.

Mais je me trompe peut être ...

En plus je ne suis pas convaincu que le temps de calcul soit inférieur à celui correspondant à trouver des points dans une boite.

Qu'en pensez vous ?

[KINENVEU]

bonjour,

je pense que la solution a ton probleme (deja citee plus haut) est la : http://en.wikipedia.org/wiki/Kd-tree

de plus, si la repartition de l'ensemble A et B n'est pas aleatoire,
j'entends par la que l'intersection de A et B est petite devant A et/ou B,
tu peux egalement evisager de ne travailler qu'avec les points se trouvant dans A inter B + epsilon.
ce qui est plus rapide a calculer que toutes les distances An-Bn.

tiens nous au courant, un code python qui gere ce probleme pourrait etre utile a beaucoup d'autres developpeurs.
donc le partager serait bien venue.

merci.