Discussion :

[Infophile]

Bonjour,

Je dispose d'une liste d'angles triée dont les éléments theta_i sont entre -pi et pi. Je note v_i=(cos theta_i,sin theta_i) le vecteur élémentaire correspondant. Je souhaite étant donné un vecteur élémentaire quelconque V, déterminer les vecteurs v_i proches de +/- epsilon de V.

La première idée naïve consiste donc à parcourir tous les v_i et à vérifier si leur produit scalaire avec V est plus petit que epsilon :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
V = [cos x sin y];
for i=1:n 
     vi = [cos(theta(i+1)) sin(theta(i+1))];
     anglediff = acos(dot(vi,V));
     if abs(anglediff)<epsilon
        OK;
     end if;
end for;

Mais j'imagine qu'il doit y avoir bien plus efficace si on exploite la structure de la liste des angle theta_i (triée ou en arbre je ne sais pas ce qui est mieux), comme la recherche dichotomique...

Qu'en pensez-vous ?

PS : j'utilise les vecteurs plutôt que les angles pour traiter les cas où un angle est proche de -pi et l'autre de pi, auquel cas les vecteurs sont effectivement proches.

[PRomu@ld]

Etant donné que ta liste des angles est triée, une simple recherche dichotomique doit pouvoir te donner un résultat en log(n)