précédent | suivant | table des matières
L'enveloppe convexe d'un ensemble de points de l'espace à deux dimensions, est le polygone convexe formé avec des points de l'ensemble, tel que tout point de l'ensemble est sur le polygone ou à l'intérieur du polygone.
Dans un plan, l'enveloppe convexe peut être comparée à la région limitée par un élastique qui englobe tous les points qu'on relâche jusqu'à ce qu'il se contracte au maximum. L'idée est la même dans l'espace avec un ballon qui se dégonflerait jusqu'à être en contact avec tous les points qui sont à la surface de l'enveloppe convexe.
Surface de triangle
Les algorithmes précédents utilisent tous une méthode de calcul de surface pour les triangles. Si les trois sommets du triangle sont les points P0, P1 et P2 :
double surface(Point p0, Point p1, Point p2){
// retourne la surface
// négatif si on tourne dans le sens contraire des aiguilles d'une montre
// positif sinon
return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y))/2.;
Plus que la surface ce qui nous intéresse, c'est le fait que cette surface est posirive ou négative, qui indique que le point P2 se trouve d'un coté ou de l'autre par rapport au segment P0P1.
Point p0 = new Point(0, 0); Point p1 = new Point(10, 0); Point p2 = new Point(10, 10); System.out.println(surface(p0, p1, p2)); System.out.println(surface(p0, p2, p1)); Affiche à la console : 50.0 -50.0 |