précédent | suivant | table des matières

Marche de Jarvis.

Algorithme

On part d’un point “extrême” X₀ : par exemple le plus bas à droite. Ce point fait partie de l’enveloppe convexe. Puis on recherche le point X₁ tel que l’angle de X₀ X₁ avec l’horizontale soit minimum. Puis on itère la recherche du point X_i tel que l’angle X_i-1X_i avec X_i-2X_i-1 soit minimum jusqu’à obtenir le point X₀. Cet algorithme est appelé parfois technique du « papier cadeau ». L’algorithme a la même structure que l’algorithme de tri par sélection et échange.

   void jarvis(ArrayList<Point> lp, ArrayList<Point> env){
      // recherche du point le plus bas,
      // puis à chaque étape recherche du point qui forme le plus petit
      // angle, avec le segment des 2 points précédents de l'enveloppe
      env.clear();
      // recherche du point le plus bas à droite
      int iBas = 0;
      Point pBas= (Point)lp.get(0);
      for( int i = 1; i < lp.size(); ++i) {
         Point p = ((Point)lp.get(i));
         if(p.y > pBas.y || (p.y == pBas.y && p.x > pBas.x) ) {
            pBas = p;
            iBas = i;
         }
      }
      lp.add(pBas);

      double angle = 0.0;
      double anglePrec;
      int m, iMin = iBas;
      for(  m = 0; m < lp.size()-1; ++m){
          echanger (lp, iMin, m);
          // recherche du point suivant
          iMin = lp.size()-1;  anglePrec = angle; angle = 2*Math.PI;
          for( int i = m+1; i < lp.size(); ++i){
             double a =  angle(lp, m, i) ;
             if(a > anglePrec && a < angle){
                     iMin = i; angle = a;
             }else if( a==angle ){ // points alignés : choisir le plus éloigné
                  if(lp.get(iMin).distance(lp.get(m)) < lp.get(i).distance(lp.get(m))) 
                      iMin = i; 
             }
          }
          if(iMin == lp.size()-1 )break;// on est retombé sur le point de départ
      }
      for( int i = 0; i < =m; ++i) env.add(lp.get(i));
      lp.remove(lp.size()-1);
   }

Estimation

Soit n le nombre de points et m le nombre de points de l’enveloppe convexe. Pour tous les points de l’enveloppe convexe, il y a un parcours de l’ensemble des points pour chercher celui dont l’angle avec le segment précédent de l’enveloppe est minimal. L’algorithme a donc une complexité égale à n×m. Le cas le plus défavorable est le cas où n=m, tous les points font partie de l’enveloppe convexe.

haut de la page