Solution du TD d'informatique No. 2 :
Calcul d'enveloppe convexe

Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr

Lundi 20 novembre 2000

import java.io.* ;
import java.lang.* ;
import java.util.* ;

class enveloppe_convexe {
    // Variables globales = disponibles dans toute la classe
    static int max ;    // max donne le nombre de points dont on cherche l'enveloppe convexe.
    static Point[] P ;  // P est le tableau des points.
    
    // Fonction d'initialisation aleatoire
    static void Initialise() {
 for (int i = 0 ; i < max ; ++i) {
     P[i] = new Point() ;
     P[i].h = (short)(Math.random() * 200) ;
     P[i].v = (short)(Math.random() * 200) ;
 }
    }
    
    // Fonction d'initialisation a la main
    static void Initialise_souris() {
 for (int i = 0 ; i < max ; ++i) {
     P[i] = new Point() ;
     MacLib.WaitClickDown() ;
     MacLib.GetMouse(P[i]) ;
     MacLib.PaintCircle(P[i].h, P[i].v, 2) ;
 }
    }
    
    // Echange de deux points dans le tableau
    static void Echange(int a, int b) {
 Point p = P[a] ;
 P[a] = P[b] ;
 P[b] = p ;
    }
    
    // Recherche du point d'ordonnee minimale
    static int TrouveOrdonneeMinimum() {
 int min = 0 ;
 for (int i = 0 ; i < max ; ++i)
     if (P[i].v < P[min].v)
  min = i ;
 return min ;
    }
    
    // Calcul de l'angle entre deux points et l'horizontale
    static double Angle(Point p, Point q) {
 double angle = Math.atan2(q.v - p.v, q.h - p.h) ;
 if (angle < 0)
     angle += 2.0 * Math.PI ;
 return 180.0 * angle / Math.PI ;
    }
    
    // Calcul de l'enveloppe convexe par l'algorithme du cordeau
    static int Wrap() {
 int min = TrouveOrdonneeMinimum() ;
 // place une sentinelle
 P[max]= P[min] ;
 double angle = 0.0 ;
 for (int j = 0 ; j < max ; ++j) {
     Echange(j, min) ;
     min = max ;
     double am = angle ;
     angle = 360.0 ;
     for (int k = j + 1 ; k <= (j == 0 ? max - 1 : max) ; ++k)
  if (Angle(P[j], P[k]) >= am)
      if (Angle(P[j], P[k]) < angle) {
   min = k ;
   angle = Angle(P[j], P[k]) ;
      }
     if (min == max)
  return j ;
 }
 return max ;
    }

    // Tri du tableau par selection en fonction des angles
    static void Tri_Tableau() {
 for (int i = 1 ; i < max - 1 ; ++i) {
     int m = i ;
     for (int j =  i + 1 ; j < max ; ++j) {
  if (Angle(P[0], P[m]) > Angle(P[0], P[j]))
      m = j ;
     }
     Echange(i, m) ;
 }
    }

    // Calcul de l'enveloppe convexe par le balayage de Graham
    static int[] Graham() {
 // Recherche du point d'ordonnee minimale et tri du tableau selon les angles
 int min = TrouveOrdonneeMinimum() ;
 Echange(min, 0) ;
 Tri_Tableau() ;

 // Parcours du tableau avec creation d'un tableau auxiliaire
 int [] tableau = new int[max + 1] ;
 for (int i = 0 ; i < max ; ++i) 
     tableau[i] = -1 ;
 tableau[0] = 0 ;
 tableau[1] = 1 ;
 int m = 2, n = 2 ;
 while (m < max) {
     tableau[n] = m ;
     while (Angle(P[tableau[n - 1]], P[tableau[n]]) < Angle(P[tableau[n - 2]], P[tableau[n - 1]])) {
  tableau[n - 1] = tableau[n] ;
  tableau[n] = -1 ;
  n-- ;
     }
     m++ ;
     n++ ;
 }
 System.out.println(m) ;
 tableau[n] = 0 ;
 return tableau ;
    }
    
    // Intialisation du graphique
    static void Init_graphique() {
 MacLib.InitQuickDraw() ;
 MacLib.ShowDrawing() ;
 Rect r = new Rect() ;
 r. top = 100 ;
 r.left = 100 ;
 r.bottom = 350 ;
 r.right = 350 ;
 MacLib.SetDrawingRect(r) ;
    }
    
    // Affichage des points et de l'enveloppe calculee par le cordeau
    static void Affichage(int nb) {
 for (int i = 0 ; i < max ; ++i)
     MacLib.PaintCircle(P[i].h, P[i].v, 2) ;
 MacLib.MoveTo(P[0].h, P[0].v) ;
 for (int j = 1 ; j <= nb ; ++j)
     MacLib.LineTo(P[j].h, P[j].v) ;
 MacLib.LineTo(P[0].h, P[0].v) ;
 MacLib.WaitClickDown();
 System.exit(0) ;
    }    
    
    // Affichage des points et de l'enveloppe calculee par balayage
    static void Afficher(int[] tableau) {
 for (int i = 0 ; i < max ; ++i)
     MacLib.PaintCircle(P[i].h, P[i].v, 2) ;
 MacLib.MoveTo(P[0].h, P[0].v) ;
 int j = 1 ;
 while (j < max && tableau[j] != -1) {
     MacLib.LineTo(P[tableau[j]].h, P[tableau[j]].v) ;
     ++j ;
 }
 MacLib.LineTo(P[0].h, P[0].v) ;
 MacLib.WaitClickDown();
 System.exit(0) ;
    }    
    
    // La fonction principale
    public static void main(String[] arg) {
 // Determination du nombre max de points
 if (arg.length == 0)
     max = 100 ;
 else if (arg.length == 1)
     max = Integer.valueOf(arg[0]).intValue() ;
 else {
     System.out.println("Utilisation : java enveloppe_convexe nb_points\n") ;
     System.exit(0) ;
 }
 P = new Point[max + 1] ;

 // Initialisation des points
 Init_graphique() ;
 Initialise_souris() ;
 Afficher(Graham()) ;
 
 // Calcul de l'enveloppe
 //Affichage(Wrap()) ;

 
    }
}

This document was translated from L^AT_EX by H^EV^EA.