1. L'intérieur du polygone convexe est défini par des déterminants det(AiAi+1, AiP) tous positifs.

  2. Pour une arête donnée la convexité de Cn entraîne que l'arête AiAi+1 est visible de P, si et seulement si le déterminant det(AiAi+1, AiP) est négatif. Intuitivement, un rayon lumineux partant de P et frappant l'arête pointe alors vers l'intérieur de Cn. Un sommets est éclairé lorsqu'une au moins des arêtes qui le touchent est visible. Il existe alors deux sommets importants, le premier sommet visible et le dernier en suivant le sens positif de rotation (sur la figure A2 et A4).
    Or, on peut fabriquer l'enveloppe convexe de Cn union {P} en supprimant toutes les arêtes visibles de Cn et en ajoutant une arête du premier sommet visible à P suivie d'une arête de P au dernier sommet visible. On obtient alors le polygone.


  3. La méthode consiste à attendre d'avoir trois points (un triangle) et à les ordonner dans le sens positif (det(A0A1, A1A2) > 0). On peut ensuite construire l'enveloppe convexe incrémentalement, selon la question précédente. Une extension peut demander le parcours complet des points de l'enveloppe (si par exemple A0 est le dernier point visible). Le coût est donc au pire quadratique. Il est atteint lorsque tous les points sont dans l'enveloppe convexe. et que les parcours commencent au dernier sommet visible.

  4. Avec des points triés, chaque nouveau point appartient nécessairement à l'enveloppe convexe construite et au tour suivant ce point sera nécessairement éclairé. On peut alors trouver le dernier point éclairé en tournant dans le sens trigonométrique et le premier point éclairé en tournant dans l'autre sens. Une liste doublement chaînée permet cette opération. Si on trouve p côtés éclairés, on aura calculé p+2 déterminants (coût en p), et on enlèvera p-1 points (opération en coût constant). Un point donné est ajouté une fois et enlevé au plus une fois. L'algorithme est linéaire, car on peut associer un coût constant à chaque point (un déterminant si le point est enlevé, deux déterminants et une modification de la liste des sommets au moment de l'ajout).

    <<<<<<< index.tex
  5. Voici le code d'une classe Convexe qui réalise le calcul incrémental de l'enveloppe convexe. Les sommets de l'enveloppes sont dans le champ cvx sous forme d'une liste bouclée de points. Cette structure de donnée délicate à manipulér est ici indiquée. En effet, une telle liste ressemble fortement aux dessins des enveloppes : des points reliés par des flèches.
    class Convexe {
      
    PointList cvx ; // Liste des sommets. Attention, c'est une liste bouclée

      
    // Travail sur l'enveloppe convexe.

      
    // Renvoie un entier r 
      
    //    - r < 0  -> q est à droite du vecteur p1 p2
      
    //    - r > 0  -> q est à gauche du vecteur p1 p2
      
    //    - r == 0 -> q p1 p2 alignés


      
    static private int det(PointList q, PointList p1, PointList p2) {
        
    int r =
          (q.y - p1.y) * (p2.x - p1.x) - (q.x - p1.x) * (p2.y - p1.y) ;
        
    return r ;
      }


      
    // Fabrication d'un triangle comme liste bouclée de trois points
      
    static private PointList triangle (PointList p1, PointList p2, PointList p3) {
        
    PointList r3 = new PointList(p3.x, p3.y, null) ;
        
    PointList r2 = new PointList(p2.x, p2.y, r3) ;
        
    PointList r1 = new PointList(p1.x, p1.y, r2) ;
        r3.next = r1 ;
        
    return r1 ;
      }

      
    // Étendre l'enveloppe convexe (liste bouclée cvx)
      
    // Le point ajouté est le premier de l'argument p
      
    // etendre renvoie un booléen, qui indique un changement de l'enveloppe.


     
    boolean etendre(PointList p) {
        
    if (cvx == null) {
          
    PointList p1 = p ;
          
    if (p1.next == null)  return false ;
          
    PointList p2 = p1.next ;
          
    if (p2.next == nullreturn false ;
          
    PointList p3 = p2.next ;
          
    if (det(p1, p2, p3) < 0) {
            cvx = triangle(p1,p2,p3) ;
          } 
    else {
            cvx = triangle(p1,p3,p2) ;
          }
          
    return true ;
        } 
    else {
          
    PointList first = null , last = null ;
          
    PointList q ;
          
    int prev = NONE ;
          
    int edge ;

          
    // Recherche des transitions entre ombre et lumière
          q = cvx ;
          
    do {
            
    if (det(p, q, q.next) >= 0) {
              edge = LIGHT ;
              
    if (prev == SHADOW) first = q ;
            } 
    else {
              edge = SHADOW ;
              
    if (prev == LIGHT) last = q ;
            }
            prev = edge ;
            q = q.next ;
          } 
    while (q != cvx) ;
          
    // Examen de l'arc issu du premier point
          
    if (det(p, q, q.next) >= 0) {
            
    if (prev == SHADOW) first = q ;
          } 
    else {
            
    if (prev == LIGHT) last = q ;
          }

          
    // Le point ajouté est à l'intérieur
          
    if (last == nullreturn false ;

          
    // Suppression des sommets éclairés, et ajout du nouveau point
          cvx = 
    new PointList(p.x, p.y, last) ;
          first.next = cvx ;
          
    return true ;
        }
      }
    }


  6. L'extension de l'enveloppe convexe est en fait correctement traitée. Un côté est considéré éclairé par un point aligné. Si le point P est situé sur le côte strico-sensu, l'effet sera d'ajouter un point inutile à l'enveloppe convexe. Sinon un point devenu inutile sera enlevé.

    En revanche la collecte des trois premiers points doit être changée pour devenir celle des trois premiers points non-alignés.