22 février
Enveloppe d’une forme convexe en Action Script
Aujourd’hui voici un petit tutoriel sur la création d’une enveloppe d’une forme convexe.
notre forme sera un polygone constitué d’une nombre indéfinis de points.Le code présenté est inspiré de l’algorithme du parcours de Graham
on crée un tableau enveloppe qui stockera les points à relier. Le tableau d’objet points à au départ 2 propriétés : X et Y
var enveloppe:Array = []; //Recherche du point le plus bas var bas:Object = points.sortOn("y",Array.NUMERIC)[points.length-1]; points.pop();
Puis on affecte une propriété angle définies par rapport au point le plus bas
//Tri du reste du nuage en fonction des angles par rapport au point le plus bas sens_trigo( bas,points ) ; points.sortOn("angle",Array.NUMERIC); enveloppe.push(bas); points.push(bas);
enfin , nous pouvons créer l’enveloppe :
while(points.length > 0) { //On retire le premier point du nuage et on le place dans l'enveloppe enveloppe.push(points.shift() ) ; } var spr:Shape = new Shape(); spr.graphics.lineStyle(group.@weight,group.@color); spr.graphics.beginFill(group.@color); for (var incS:int = 0; incS < enveloppe.length ; incS++) { if(incS == 0) { spr.graphics.moveTo(enveloppe[incS].x,enveloppe[incS].y+20); } else { var deltaX:Number = enveloppe[incS].x-enveloppe[incS-1].x; var deltaY:Number = enveloppe[incS].y-enveloppe[incS-1].y; if(deltaX > 0) spr.graphics.curveTo(enveloppe[incS].x-deltaX/2,enveloppe[incS].y+Math.abs(deltaY),enveloppe[incS].x+20,enveloppe[incS].y); else spr.graphics.curveTo(enveloppe[incS].x-deltaX/2,enveloppe[incS].y-Math.abs(deltaY),enveloppe[incS].x-20,enveloppe[incS].y); } } spr.graphics.endFill();
Méthode sens_trigo :
private function sens_trigo(bas:Object,points:Array):void { for each(var p:Object in points) { var angleRadian:Number = Math.atan2(bas.x - p.x, bas.y - p.y); var angleDegree:Number = angleRadian * (180 / Math.PI); p.angle = angleDegree; } }
Pour rappel le pseudo code du parcours de Graham est celui ci :
Trouver le pivot P; Trier les points par angle (les points d'angle égal seront triés par rapport à leur abscisse); # Points[1] est le pivot, Points[longueur] aussi (fin du circuit) Pile.empiler(Points[1]); Pile.empiler(Points[2]); POUR i = 3 A Points.longueur TANT QUE (Pile.hauteur >= 2) ET (Produit_vectoriel(Pile.second, Pile.haut, Points[i]) <= 0) Pile.dépiler; FIN TANT QUE Pile.empiler(Points[i]); FIN POUR FONCTION Produit_vectoriel(p1, p2, p3) RENVOYER(p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y); FIN FONCTION