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

Algorithme des arêtes externes.

Algorithme

Les arêtes externes sont les arêtes telles que tous les points de l’ensemble sont du même coté de l’arête. L’algorithme consiste donc à énumérer toutes les arêtes, et pour chaque arête calculer si tous les points sont du même coté de l’arête ou non.

   void aretesExternes(ArrayList<Point>  lp, ArrayList<Point> env){
      // recherche des cotés extremes :
      // ceux tels que tous les points sont du même coté
      int nb = 0;
      env.clear();
      // enumération des cotés
      for( int i = 0; i < lp.size(); ++i)
         for( int j = i+1; j < lp.size(); ++j){
             // tous les points sont ils du même coté
             int k=0;
             double s = surface( lp, i, j, 0 );
             // des points sur le coté
             // sont considérés indifféremment d'un coté ou de l'autre
             int cote = s < 0 ?  -1 : s == 0 ? 0 : 1;
             ++nb;
             for(  k = 1; k < lp.size(); ++k){
                 s = surface( lp, i, j, k );
                 int signe = s < 0 ?  -1 : s == 0 ? 0 : 1;
                 if(cote == 0) cote = signe;
                 if(cote != signe && signe != 0) break;
                 ++nb;
             }
             if( k == lp.size() ) {
               env.add(lp.get(i));
               env.add(lp.get(j));
             }
         }
   }

Estimation

Soit n le nombre de points. Evaluons le nombre d’appels de la méthode surface :

Ce nombre est au maximum : =

haut de la page