public static function boundingCircle2(points:Array):Circle { //FIRST PASS: find 4 minima/maxima points var xmin:Point = new Point(1e+10, 0); var ymin:Point = new Point(0, 1e+10); var xmax:Point = new Point(-1e+10, 0); var ymax:Point = new Point(0, -1e+10); var i:uint, k:uint = points.length, p:Point; for (i = 0; i < k; i++) { p = points[i]; if (p.x < xmin.x) xmin = p; //New xminimum point if (p.x > xmax.x) xmax = p; if (p.y < ymin.y) ymin = p; if (p.y > ymax.y) ymax = p; } //Set xspan = distance between the 2 points xmin & xmax (squared) var dx:int = xmax.x - xmin.x; var dy:int = xmax.y - xmin.y; var xspan:int = dx * dx + dy * dy; //same for y span dx = ymax.x - ymin.x; dy = ymax.y - ymin.y; var yspan:int = dx * dx + dy * dy; //Set points dia1 & dia2 to the maximally separated pair var dia1:Point = xmin; //assume xspan biggest var dia2:Point = xmax; var maxspan:Number = xspan; if (yspan > maxspan) { maxspan = yspan; dia1 = ymin; dia2 = ymax; } //dia1,dia2 is a diameter of initial circle //calc initial center var cx:int = (dia1.x + dia2.x) >> 1; var cy:int = (dia1.y + dia2.y) >> 1; //calculate initial radius**2 and radius dx = dia2.x - cx; //x component of radius vector dy = dia2.y - cy; //y component of radius vector var rSq:Number = dx * dx + dy * dy; var r:Number = Math.sqrt(rSq); var t0:Number, t1:Number; var dSq:Number, d0:Number, d1:Number; //SECOND PASS: increment current circle for (i = 0; i < k; i++) { //this point is outside of current circle p = points[i]; dx = p.x - cx; dy = p.y - cy; dSq = dx * dx + dy * dy; if (dSq > rSq) //do r**2 test first { d0 = Math.sqrt(dSq); //calc radius of new circle r = (r + d0) >> 1; rSq = r * r; //for next r**2 compare d1 = d0 - r; // calc center of new sphere cx = (r * cx + d1 * p.x) / d0; cy = (r * cy + d1 * p.y) / d0; } } return new Circle(cx, cy, r); }