Enveloppe convexe

Algorithme d'enveloppe convexe

Problème rencontré en dessinant l'ombre portée d'un cube : la liste de coordonnées à deux dimensions de l'ombre (obtenue depuis la liste des vertex du cube projetés sur un plan) ne suit aucune logique dans l'ordre de ses points. Dans cet article, nous allons résoudre ce problème et comprendre comment déduire une forme enveloppant un nuage de points à partir de ces points.

Nous allons donc calculer l'enveloppe convexe d'après une liste de points disposés aléatoirement. Notre article décrit l'algorithme en ActionScript 3 qui résout ce problème.

Enveloppe convexe
Exemple d'enveloppe convexe.

Nous devons trouver les points faisant partie de l'enveloppe convexe. La manière qui semble la plus simple pour les trouver serait de :

  1. choisir un point membre de cette enveloppe ;
  2. partir de ce point pour parcourir un à un les points de cette enveloppe dans le sens des aiguilles d'une montre ;
  3. une fois que l'on a fait le tour de l'enveloppe (quand on retrouve notre premier point) on stoppe notre progression.

Prenons un point A. Nous devons déduire le point B, qui fait partie de notre enveloppe et qui suit le point A. Pour cela nous allons calculer les angles de tous les points par rapport à A. Si l'on prend l'angle le plus grand ou l'angle le plus petit, on obtient un point de l'enveloppe qui suit le point A.

Enveloppe convexe
Angle radian.

Pour calculer un angle radian, la méthode Math.atan2(y:Number, x:Number):Number nous mâche le travail. Celle-ci permet de calculer un angle radian à partir de coordonnées cartésiennes.

Dans notre exemple, nous partons du point situé le plus à gauche de tous nos points. Nous allons ensuite suivre l'enveloppe dans le sens des aiguilles d'une montre. Nous calculons l'angle radian de tous nos points par rapport au premier. Prendre un point plus élevé et plus à droite de notre point revient à choisir l'angle radian le plus élevé situé en dessous de PI. Il faut recommencer cette opération jusqu'à arriver au point situé le plus haut. Après celui-ci, nous ne trouverons plus de point au-dessus, donc pas d'angle supérieur à 0 par rapport à ce point.

Nous cherchons donc l'angle radian le plus élevé situé entre 0 et -PI. Ceci nous permet de choisir le point le plus haut à droite de notre point. Cela nous emmène progressivement au point le plus à droite puis au point le plus bas.

Enveloppe convexe
Récupération de la liste de points, étape 1.

À partir du point le plus bas, il nous faudra recommencer notre première étape : chercher l'angle le plus élevé situé entre 0 et PI. Nous ne pourrons nous arrêter qu'une fois que nous aurons atteint le premier point de notre enveloppe (le point le plus à gauche).

Voilà, après avoir enregistré notre suite de points dans l'ordre, nous obtenons l'enveloppe convexe de notre nuage de points !

// Fonction de convertion d'un nuage de point à une enveloppe convexe
// Vector.< Number > pour pouvoir être passé dans la méthode drawPath()
// de la classe Graphicsflash.display.Graphics
// chaque couple de nombre correspond aux coordonées d'un point
function convertToConvexForm(inPath:Vector.< Number >):Vector.< Number >
{
  // initialisation des variables dont une liste d'objets Point, plus simple pour les calculs
  var i:int, j:int, pt:Point;
  var listPoints:Vector.< Point > = new Vector.< Point >( inPath.length * 0.5, true );

  // passage de notre liste de nombres en une liste de points équivalente
  i = listPoints.length;
  while(--i>-1)
  {
    listPoints[i] = new Point( inPath[i+i], inPath[i+i+1] );
  }

  // notre liste une fois que ses points seront réorganisés
  var outList:Vector.< Point > = new Vector.< Point >(0, false);

  i = listPoints.length;
  while(--i>-1)
  {
    if(outList.length == 0)                    outList[0] = listPoints[i];
    else if(listPoints[i].x > outList[0].x)    outList[0] = listPoints[i];
  }

  // dans l'ordre :
  // state = 0    =>    du point le plus à gauche au point le plus haut
  // state = 1    =>    du point le plus haut au point le plus bas en passant par la droite
  // state = 0    =>    du point le plus bas au point le plus à gauche
  var state:int = 0;
  // une fois que nous ne trouvons plus de points remplissant les conditions
  // la variable "choice" reste à false et nous passons à l'étape suivante.
  var choice:Boolean = false;
  search : while(true)
  {
    j = outList.length - 1;

    if(state == 0)
    {

      choice = false;
      i = listPoints.length;
      while(--i>-1)
      {
        // évite de calculer l'angle à partir du même point
        if( !outList[j].equals(listPoints[i]) )
        {
          if(Math.atan2( listPoints[i].y - outList[j].y, listPoints[i].x - outList[j].x ) > 0)
          {
            if( !choice )
            {
              outList[j+1] = listPoints[i];
              choice = true;
            }
            else if( Math.atan2( listPoints[i].y - outList[j].y, listPoints[i].x - outList[j].x ) <
                     Math.atan2( outList[j+1].y - outList[j].y , outList[j+1].x - outList[j].x ) )
            {
              outList[j+1] = listPoints[i];
              choice = true;
            }
          }
        }
      }

      if(!choice) 
      {
        state++;
      }

    }
    else if(state == 1)
    {

      choice = false;
      i = listPoints.length;
      while(--i>-1)
      {
        if( !outList[j].equals(listPoints[i]) )
        {
          if(Math.atan2( listPoints[i].y - outList[j].y, listPoints[i].x - outList[j].x ) <= 0)
          {
            if( !choice )
            {
              outList[j+1] = listPoints[i];
              choice = true;
            }
            else if( Math.atan2( listPoints[i].y - outList[j].y, listPoints[i].x - outList[j].x ) <
                     Math.atan2( outList[j+1].y - outList[j].y , outList[j+1].x - outList[j].x  ) )
            {
              outList[j+1] = listPoints[i];
              choice = true;
            }
          }
        }
      }

      if(!choice) 
      {
        state--;
      }

    }

    // sortir de la boucle une fois que le point obtenue est le même que le point de départ
    if(outList[outList.length - 1].equals(outList[0])) break search;
  }

  var path:Vector.< Number > = new Vector.< Number >(outList.length * 2, true);

  // récupération de notre nouvelle liste de points pour la passer dans une liste de nombre
  i = outList.length;
  while(--i>-1)
  {
    path[ (i + i) ] = outList[i].x;
    path[ (i + i) + 1 ] = outList[i].y;
  }

  return path;
}