Discussion :

[Vol]

Bonjour,

Voici mon problème:
J'ai un tableau (tab1) contenant des dizianes de milliers de points (x,y,z). Pour chacun des points de tab1, je dois déterminer quel point est le plus près parmis un tableau (tab2) contenant lui aussi des dizaines de milliers de points (x,y,z). Les points de tab1 changent de position à chaque dt et dt>1000. Il faut donc un algo de recherche très rapide.

Présentement, j'utilise une recherche qui teste tous les points mais ce n'est vraiment pas assez rapide (en fait, j'utilise cette technique surtout pour tester les autres fonctionnalités de mon code). La création d'une structure de donnée sera donc nécessaire. Le problème est que je n'ai aucune idée laquelle utilisée.


J'ai trouvé que dans cette discussion il est question d'utiliser une structure de données géométrique du type quadtrees. Par contre, selon ma lecture rapide de documentation que j'ai trouvé, les quadtrees sont faits pour être utilisés sur un espace 2D, donc des points en (x,y) seulement. Existe-t-il une structure pour le 3D. Autres suggestions?

Merci!

[Graffito]

Bonjour,

On pourrait optimiser le traitement de la façon suivante :
- soit D2[j], la distance d'un point de tab2 à l'origine, ces distance sont calculéers à l'initialisation,
- soit D1[i] la distance du point de tab1 à l'origine,
- soit DMin la distance minimum trouvée lors de la recherche,
- si l'on envisage les points de tab2 en s'éloignant de part et d'autre de la valeur D1[i], on pourra s'arréter dès que D2[j]-D1[i]>Dmin.

Cette optimisation donnera de bon résultats lorsque les Distances au point le plus proche sont faibles comparées à la distance moyenne entre 2 points de tab2.

Si ce n'est pas le cas, on peut envisager de découper l'espace en cubes virtuels, indexer tab2 en fonction du cube auquel appartient le point, chercher le cube le plus proche contenant un point de tab2 et se contenter de tester tous le points de ce cube et ceux de ses 26 voisins.

[plegat]

Salut,

Ca s'appelle en octree en 3D....
Pas d'autre suggestion que ça, c'est ce que j'utiliserais personnellement... mais je ne connais pas d'autre alternative pour être plus rapide non plus!

[Vol]

Merci pour les réponses.

Graffito, je dois avouer que j'ai de la difficulté à comprendre ta première solution. De plus, j'ai du mal à voir comment la procédure pourra différencier des points tels P1(x1,y1,z1) et P2(-x1,y1,z1) où leur distance seront équivalentes.

Si ce n'est pas le cas, on peut envisager de découper l'espace en cubes virtuels, indexer tab2 en fonction du cube auquel appartient le point, chercher le cube le plus proche contenant un point de tab2 et se contenter de tester tous le points de ce cube et ceux de ses 26 voisins.

C'est une bonne alternative, merci. Les 26 voisins? Est-ce qu'ils proviennent de ceci: nbVoisins = 6 faces + 12 arrêtes + 8 sommets?

Ca s'appelle en octree en 3D....

J'ai fouiller pour trouver de la doc sur les octrees et tout ce que j'ai trouvé fait toujours références à des applications de jeu vidéo. Est-ce que ces références pourraient être appliquées à mon cas?

Est-ce que quelqu'un à de bons tutoriels/références pour créer un octree? (J'ai chercher sur le forum et il faut dire que le mot octree n'a pas été mentionné souvent dans les 3 dernières années )

[Graffito]

Bonjour,

Les 26 voisins? Est-ce qu'ils proviennent de ceci: nbVoisins = 6 faces + 12 arrêtes + 8 sommets?

Les 26 voisins sont les cubes externes d'un supercube de coté 3 (3x3x3=27).

PS: pour la solution 1, on ne distingue pas les points de coord x et -x ni les autres points de la surface de la sphére de rayon x, mais si pour un point de tab1 situé à une distance R du centre et à une petite distance d de la sphére de rayon R, on peut ne pas regarder les sphères de rayon supérieur à R+d et celles inférieures à R-d.

[plegat]

J'ai fouiller pour trouver de la doc sur les octrees et tout ce que j'ai trouvé fait toujours références à des applications de jeu vidéo. Est-ce que ces références pourraient être appliquées à mon cas?

Oui, elles peuvent.
La seule différence est qu'en général, les jeux vidéos travaiellent avec des triangles ou des quad, et toi des points. Le principe de partitionnement de l'espace reste le même.
Une autre petite différence avec les jeux vidéos, c'est que eux vont chercher tous les petits cubes qui sont interceptés par un cône de visée (entre l'oeil de l'observateur et le point de visée) alors que toi tu vas te contenter de trouver le cube qui contient ton point (et éventuellement les quelques cubes voisins pour éviter des surprises).

Pour les tutoriels... ça je n'ai pas... mais inspire-toi de ceux pour les jeux, ça marchera très bien. La marche à suivre est toute bête, tu coupes l'espace en huit cubes... puis chaque cube en huit cubes aussi... et tu t'arrêtes quand tu as assez de points dans chaque cube.

Le temps de construction de l'octree peut être assez long, mais tu gagnera beaucoup en traitement derrière.

[Jean-Marc.Bourguet]

Comme structure de donnee pour representer des objets dans l'espace, il y a aussi
les R-Tree (http://www.rtreeportal.org/).

[Vol]

PS: pour la solution 1, on ne distingue pas les points de coord x et -x ni les autres points de la surface de la sphére de rayon x, mais si pour un point de tab1 situé à une distance R du centre et à une petite distance d de la sphére de rayon R, on peut ne pas regarder les sphères de rayon supérieur à R+d et celles inférieures à R-d.

J'aurais du initialement spécifier que mes points sont situés sur la surface d'un cylindre... Je ne voulais pas être trop précis pour mes besoins afin d'avoir une technique la plus générale possible qui pourrait fonctionner dans le cas où la distribution ne se fait pas sur un cylindre.

Oui, elles peuvent.
La seule différence est qu'en général, les jeux vidéos travaiellent avec des triangles ou des quad, et toi des points. Le principe de partitionnement de l'espace reste le même.
Une autre petite différence avec les jeux vidéos, c'est que eux vont chercher tous les petits cubes qui sont interceptés par un cône de visée (entre l'oeil de l'observateur et le point de visée) alors que toi tu vas te contenter de trouver le cube qui contient ton point (et éventuellement les quelques cubes voisins pour éviter des surprises).

Pour les tutoriels... ça je n'ai pas... mais inspire-toi de ceux pour les jeux, ça marchera très bien. La marche à suivre est toute bête, tu coupes l'espace en huit cubes... puis chaque cube en huit cubes aussi... et tu t'arrêtes quand tu as assez de points dans chaque cube.

Le temps de construction de l'octree peut être assez long, mais tu gagnera beaucoup en traitement derrière.

Super, je vais donc essayer avec les tutoriels de jeux vidéos que j'ai trouvés. De plus, comme mentionné précédemment, je ne voulais pas rendre le topic trop pointu. C'est pour cette raison que j'ai parlé seulement de point distribué dans un espace 3D.

En réalité, mes points correspondent aux noeuds d'éléments triangulaires. Ces éléments triangulaires forment un cylindre qui est fermé au deux extrémités par des surfaces quelconques. La recherche doit se faire sur les noeuds/points composants les triangles sur la surface du cylindre et sur les deux extrémités. C’est point sont ceux de tab2 de mon post original. Le but étant de déterminer, pour un point de tab1, quel triangle contient ce point. Ainsi en déterminant le point/noeud le plus près dans tab2, je connais les éléments qui utilisent ce noeud et alors, ces éléments sont testés pour voir si mon point est à l'intérieur.
Bon... puisque le dernier paragraphe n'est probablement pas trop clair, vous comprendrez pourquoi j'avais initialement parlé seulement de points dans un espace 3D.

Comme structure de donnee pour representer des objets dans l'espace, il y a aussi
les R-Tree (http://www.rtreeportal.org/).

Merci pour cette alternative, je vais étudier les deux méthodes et essayer de déterminer la meilleure pour mon application en particulier.

Merci pour toutes les suggestions. Je laisse le topic ouvert un brin de plus au cas où d'autres suggestions pourraient être apportées.