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

Algorithme par partition et fusion.

Algorithme

On commence par ordonner les points de l'ensemble par ordre croissant des abcisses, et pour des abcisses égales par ordre croissant des ordonnées.

• Si l'ensemble est constitué de trois points au plus, il est sa propre enveloppe convexe.
• Si l'ensemble a plus de trois points, on le divise en deux ensembles de tailles (à peu près) égales. On calcule récursivement l'enveloppe convexe de ces deux sous-ensembles. Reste alors à fusionner ces deux enveloppes convexes.

Soient E1 et E2 les deux enveloppes convexes qu'on veut fusionner. On commence par choisir le point le plus à droite de E1 et le point le plus à gauche de E2. Le segment qui relie ces deux points va être mis en place, de façon à relier les deux enveloppes convexes. Sur l'exemple ce sont les opérations 1, puis 2, 3, 4, 5 et enfin 6. On fait de la même façon pour relier les deux enveloppes convexes par le bas.

  void partition(ArrayList<Point> lp, ArrayList<Point> env){
     env.clear();
     // ordonner les points par ordre croissant des abcisses       
     Collections.sort(lp, new CompAbcs());
     if(lp.size()<=3) {
        env.addAll(lp); 
        if(  lp.size()==3 &&
           surface(env.get(0), env.get(1), env.get(2))>0){
          Point p = env.get(1);
           env.remove(p); env.add(p);
        }
        return;
     }
     //On divise en deux
     ArrayList<Point> e1 = new ArrayList<Point>();
     ArrayList<Point> e2 = new ArrayList<Point>();
     for(int i = 0; i<lp.size()/2; ++i)         e1.add(lp.get(i));
     for(int i = lp.size()/2; i<lp.size(); ++i) e2.add(lp.get(i));
     // On calcule les enveloppes de chaque morceau
     ArrayList<Point> env1 = new ArrayList<Point>();
     ArrayList<Point> env2 = new ArrayList<Point>();
     partition(e1, env1);
     partition(e2, env2);
     // et on fusionne ! 
     env.addAll( fusion(env1, env2) ); 
  }
    
  ArrayList<Point> fusion(ArrayList<Point> e1, ArrayList<Point> e2){
     // recherche du point d'abcisse le plus grand dans e1;
     int iMax = 0;
     for( int i = 1; i < e1.size(); ++i) if(e1.get(i).x > e1.get(iMax).x) iMax = i;
     // le point d'abcisse le plus petit dans e2 est en 0
     int iMin = 0;
     // le segment du haut
     int ip1 = iMax; 
     int ip2 = iMin;
     boolean b = true;
     while(b){ 
         b = false;
         if(Algs.surface(e2.get(ip2), e1.get(ip1), e1.get((ip1+1)%e1.size()))>0){
            ip1 = (ip1+1)%e1.size();
            b = true;
         }
         if(Algs.surface(e1.get(ip1), e2.get(ip2), e2.get((ip2-1+e2.size())%e2.size()))<0){
            ip2 = (ip2-1+e2.size())%e2.size();
            b = true;
         }
     }
     // le segment du bas
     int im1 = iMax; 
     int im2 = iMin;
     b = true;
     while(b){ 
          b = false;
         if(Algs.surface(e2.get(im2), e1.get(im1), e1.get((im1-1+e1.size())%e1.size()))<0){
            im1 = (im1-1+e1.size())%e1.size();
            b = true;
         }
         if(Algs.surface(e1.get(im1), e2.get(im2), e2.get((im2+1)%e2.size()))>0){
            im2 = (im2+1)%e2.size();
            b = true;
         }
     }
     // fabrication de l'enveloppe
     ArrayList<Point> env = new ArrayList();
     for( int i = 0; i<=im1; ++i)            env.add(e1.get(i));  
     if(ip2==0){
         for( int i = im2; i<e2.size(); ++i) env.add(e2.get(i));
                                             env.add(e2.get(0));
     }
     else
         for( int i = im2;  i<=ip2; ++i)            env.add(e2.get(i));      
     if(ip1!=0) for( int i = ip1; i<e1.size(); ++i) env.add(e1.get(i));

     return env;
  }

Estimation

Le tri de l'ensemble est en n×log(n). La fusion est une opération de coût n. Le coût total est donc en n×log(n).

haut de la page