Algo de recherche dans un cube de couleur

Bonjour à tous,

Je voudrais savoir si il existe des algo optimisés pour la recherche dans un espace discret 3D.

Mon problème c'est de partir d'un point (coordonnées 3D) dans un cube de couleur, et je veut trouver la nuance parmi les présentes la plus proche de mon point de départ. (toutes les nuances n'existent pas dans le cube comme vous l'aurez compris)

J'ai essayé *un peu* avec une recherche récursive sur toutes les directions, mais pour qu'elle soit efficace, il faut intégrer des contraintes (pas aller dans la direction du point de départ dans les sous appel dû à la récusivité, par exemple), et comme je manque de méthode je m'y perd facilement.

Quelqu'un peut m'aider ou me pointer vers la bonne méthode ?

Merci

A l'heure ou j'ecris, + de 40 visites, mais pas de réponses :/

est ce que ca veut dire que personne n'a d'idée ou bien que la question est trop bete ou encore le sujet trop spécifique ... ou bien ?

En tout cas, je reste à l'écoute ;-)

Clarification : quand je dis algo optimisé, je parle pas d'un truc ecris en asm, je cherche juste un truc mieux que 3 for imbriqués avec un calcul de distance à chaque point..

A+

bon, j'ai pas pris baucoup de temps à réflaichir sur le problème mais deux algo me vient à l'esprit:

• 1- une recherche sequenciel avec utilisation d'une liste tabou
  2- un algorithme sequenciel en considerant la recherche sur une surface soit d'une boule ou d'un cube (la deuxième etant meilleur)

Explication des deux Algo
1- Recherche sequenciel avec utilisation d'une liste tabou:
On commence par la definition de la definition des classes suivantes (déclaré avec un pseudo langage, que je vien d'inventer pour l'occasion)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

type // definition d'un point dans un espace 3D discret T3DPoint=Classe T3DPoint(unX, unY, unZ); // un constructeur de point 3D X:Int Y:Int Z:Int fin;   // definition d'une collection de points T3DPoints=Classe // Interface pour indexer les elements de la collection fonction Count:Int; // le nombre de points dans la collection fonction GetPoint(Index:Integer):T3DPoint; function IndexOf(Point:T3DPoint):bool; // un interface pour visiter la collection procédure First; // aller au debut de la liste fonction CurrentPoint:T3DPoint; // le point courant procedure Next; // aller au point suivant fonction EndOfCollection:bool; // indique si on a atteint la fin de la liste // Interface pour manipuler le contenu de la collection fonction Add(Point:T3DPoint):int; fonction Remove(Point:T3DPoint):int; procedure Clear; procedure fusion(Points:T3DPoints); // pour integrer les elements de Points fin;

---

les classes de base etant declarée je passe à l'explication de l'algo.
on dispose de deux collections

Code:

---

CurrentPath, Tabou :T3DPoints

---

CurrentPath contient la liste des points à vister et Tabou contient l liste des points déja visités. on aurra aussi besoint d'une fonction donnant le voisinage d'un point; c'est à dire les 26 points entourant le point;

Code:

---

1 2 3 4

fonction NeighborOf(point:T3DPoint):T3DPoints; debut // créer une CollectionResultat contenant les 26 points voisins fin

---

on commence à partir d'un point donné, si la nuance à été trouvé c'est bon (return point) sinon on prend la liste des points voisins et on l'ajoute à la collection CurrentPath, et le point visté est ajoute à la collection Tabou (Tabou joue le rôle d'une liste noire, les points qu'elle contient sont interdits de visite).
l'algo de recherche etant

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

les variablesglobales CurrentPath, Tabou de type T3DPoints ... fonction FindNearest(Point:T3DPoint):T3DPoint les variables locales CurrentP de type T3DPoint Sortie, Trouve de type bool ... debut CurrentPath.Clear; CurrentPath.Add(Point) CurrentPath.First;   Tanque (non Sortie) faire CurrentP = CurrentPath.CurrentPoint CurrentPath.Remove(CurrentP) si Tabou.IndexOf(CurrentP) != -1 alors // si le point n'est pas interdit de visite // on teste si le point en cours correspond à la nuance recherché si GoodNuance(CurrentP) then Trouve = vrai sinon Trouve = Faux CurrentPath.Fusion(NeighborOf(CurrentP)) Fsi FSI Sortie = (CurrentPath.Count==0) ou (Trouve == vrai) Ftanque si Trouve alors return CurrentP sinon return null fsi fin

---

2- Recherche sur les surfaces de cubes englobants:
l'algo consiste à démarrer d'un point et de grossir le champ de recherche, j'usqu'à trouver le point; le champ de recherche n'est autre qu'une surface de cube de rayon R.
On utilise les deux classes T3DPoint, T3DPoints déclarées précédemment et une nouvelle fonction qui donne les points de la surface du cube de rayon R, centré sur un point P

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

fonction PointsOfCube(Point:T3DPoint; Rayon:int):T3DPoints les variables i,j,k de type int CubResultat de Type T3DPoints DEBUT POUR i allant de Point.X-Rayon jusqu'à Point.X+Rayon FAIRE POUR j allant de Point.Y-Rayon jusqu'à Point.Y+Rayon FAIRE POUR k allant de Point.Z-Rayon jusqu'à Point.Z+Rayon FAIRE CubResultat.Add(new T3DPoint(i,j,k)) // ajouter le point FPOUR FPOUR FPOUR FIN

---

a chaque fois on crée un champs de recherche un peu plus grand et qui entour l'ancien champ de recherche.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

fonction FindNearest2(Point:T3DPoint):T3DPoint les variables locales CurrentPath de type T3DPoints // on a plus besoin de la liste Tabou CurrentP de type T3DPoint Sortie, Trouve de type bool Ray de type int ... debut trouve Ray = 0 Tanque (non Sortie) faire CurrentPath := PointsOfCube(Point, Ray) CurrentPath.First; Tanque ((non trouve) et (non CurrentPath.EndOfCollection)) faire CurrentP=CurrentPath.CurrentPoint si CurrentP est la bonne nuance alors trouve = vrai sinon trouve = faux CurrentPath.Next fsi FTanque Sortie := trouve ou (un teste pour eviter une explosion de memoire) Ray++ FTanque SI Trouve ALORS return CurrentP SINON return null FSI fin

---

ce deuxieme algo est plus efficace que le premier, mais si cela ne te suffis pas (j'en suis sure) alors cherche du coté des heuristiques, les algos de type A* (ou Branch and Bound en RO) se prêtent bien a ce genre de prob

===============================================
excuse moi pour ce pseudo code, c'est un melange d'algo de pascal et de C++. pour A* t'as le vieux google. et bonne prog

Merci pour la réponse ''rapide" :-) je suis épaté par toutes ces informations

Pour les algos de recherche opérationnelle, je les ai vu en cours, mais je pensais que ce serai "se servir d'une bombe pour enculer une mouche" ;-) comme disais mon psychopate de prof de logique.

Je vais étudier attentivement la deuxième solution, que je ne connais pas, et je vous tiens au courant.

Merci encore

Pour avoir un algo efficace, il serait intéressant d'étudier comment sont réparties les nuances "valides" dans le cube 3D et comment elles sont données en entrées.
Si elles sont a priori aléatoires et données sous une forme de liste (ou de tableau), il serait intéressant d'échantillonner cette liste sous-forme de sous-listes qui contiendrait les points contenus dans un sous-cube du cube initial. Par exemple, le cube [2,4,6] contient la liste des points (x,y,z) qui satisfont 20<=x<30, 40<=y<50, 60<=z<70.
Ainsi, pour trouver le point le plus proche d'un point donné, il suffit de calculer dans quel sous-cube se trouve le point et de chercher le voisin le plus proche dans ce sous-cube et les sous-cubes voisins.

Il est aussi possible de structurer l'information de départ (les nuances disponibles) sous la forme d'un diagramme de Voronoï en 3D (mais c'est sans doute beaucoup de travail au vu du besoin).

J'ai une proposition, sur laquelle je n'ai pas trop trop réfléchi, mais qui peut peut être donner des résultats, avec une bonne implémentation ...

Le principe serait de diviser ton cube en boîtes de plus en plus petites.

En gros, tu fais le tri des valeurs de couleur dans le cube, rangées par ordre d'une composante croissante (mettons le rouge). Tu coupes le cube en 2, pour avoir 50% des valeurs d'un côté, 50% de l'autre.

Rebelote, sur les deux parallèlepipèdes résultants, tu tries sur une composante (mettons le vert), tu coupes chacun des deux (la position de la frontière sera différente pour chacun) en deux parts présentant autant d'échantillons.

Et encore (sur le bleu ?), et encore (rouge, puis vert, puis bleu ...).

Tu arrêtes quand tu en as marre ... ou bien quand on ne peut plus séparer en deux parts égales ( 1 seul échantillon ;) ).

Tu définis ainsi une sorte d'arbre binaire. Quand tu veux localiser une couleur, tu inspecte ses composantes et tu descends dans le noeud suivant, selon qu'elles sont au dessus ou au dessous du seuil de séparation de 50% des échantillons, et tu réitère la comparaison.

Voila ... ça vaut ce que ça vaut ...

Je le testerai peut-être quand j'aurai un peu de temps ;)