境界ボックス

赤い点を囲むように青い線が引かれていますが、 青い線は赤い点を全て含み面積ができるだけ小さくなるような矩形です。 赤い点はマウスドラッグで移動できます。その都度境界ボックスは再計算されます。

３Dの場合のアルゴリズムはこの本に載っていました。このプログラムはそれを元に２Dに直したものです。

package {
    import flash.display.*;
    import flash.events.*;
    import flash.utils.*;
    import flash.ui.Keyboard;
    import flash.geom.*;
    import flash.filters.*;


    [SWF(width="500", height="500", frameRate="10", backgroundColor="#ffffff")]
        public class Volume extends Sprite{
            private var balls:Array = [];
            public function Volume():void
            {
                var points:Array = [{x:100,y:200}, {x:200,y:100}
                , {x:300,y:400}, {x:400,y:300}
                , {x:250,y:300}, {x:300,y:100}
                ];
                for(var i:int = 0 ; i < points.length ; i++){
                    var b:Ball = new Ball(0xff0000, 10);
                    balls.push(b);
                    addChild(b);
                    b.x = points[i].x;
                    b.y = points[i].y;

                    b.addEventListener( MouseEvent.MOUSE_DOWN, pickup );
                    b.addEventListener( MouseEvent.MOUSE_UP, place );
                    b.addEventListener( MouseEvent.MOUSE_MOVE, function(e:*):void{
                            calcVolume();
                            });
                }

                calcVolume();
            }

            private function pickup( event:MouseEvent ):void {
                // ドラッグ処理を開始して、影フィルターをつける
                event.target.startDrag( );
                event.target.filters = [ new DropShadowFilter( ) ];
                // 最前面に表示されるようにする
                setChildIndex( DisplayObject( event.target ), numChildren - 1 );
            }

            private function place( event:MouseEvent ):void {
                // ドラッグ処理を終了して影フィルターをオフ
                event.target.stopDrag( );
                event.target.filters = null;

                calcVolume();
            }

            private function calcVolume():void{

                var tx:Number = 0;
                var ty:Number = 0;

                for each(var p:Ball in balls){
                    tx += p.x;
                    ty += p.y;
                }

                // 平均位置
                var avg:Point = new Point(tx/balls.length, ty/balls.length);

                // 共分散行列
                var n11:Number=0, n12:Number=0, n21:Number=0, n22:Number=0;
                for each(p in balls){
                    n11 += Math.pow((p.x - avg.x), 2);
                    n12 += (p.x - avg.x)*(p.y - avg.y);
                    n22 += Math.pow((p.y - avg.y), 2);
                }
                n11 /= balls.length;
                n22 /= balls.length;
                n12 /= balls.length;
                n21 = n12;

                // 固有値
                var lambda1:Number, lambda2:Number;
                var temp:Number =  Math.sqrt((n11+n22)*(n11+n22) - 4 * (n11*n22-n12*n21));
                lambda1 = ((n11+n22) + temp)/2;
                lambda2 = ((n11+n22) - temp)/2;

                // 固有ベクトルの(xを1とした時の)y要素
                var y1:Number = (n12 != 0) ? (lambda1 - n11)/n12 : n21/(lambda1 - n22);
                var y2:Number = (n12 != 0) ? (lambda2 - n11)/n12 : n21/(lambda2 - n22);

                // 固有ベクトル
                var v1:Point = new Point(1, y1);
                var v2:Point = new Point(1, y2);

                // 固有ベクトルの正規化
                v1.x = 1/Math.sqrt(1+y1*y1);
                v1.y = v1.y/Math.sqrt(1+y1*y1);
                v2.x = 1/Math.sqrt(1+y2*y2);
                v2.y = v2.y/Math.sqrt(1+y2*y2);

                // 各点と固有ベクトルとの内積の最大/最小値
                var v1min:Number, v1max:Number;
                var v2min:Number, v2max:Number;
                for each(p in balls){
                    var dot1:Number = v1.x*p.x + v1.y*p.y;
                    var dot2:Number = v2.x*p.x + v2.y*p.y;
                    if(isNaN(v1min) || v1min > dot1)
                        v1min = dot1;
                    if(isNaN(v1max) || v1max < dot1)
                        v1max = dot1;
                    if(isNaN(v2min) || v2min > dot2)
                        v2min = dot2;
                    if(isNaN(v2max) || v2max < dot2)
                        v2max = dot2;
                }

                graphics.clear();
                graphics.lineStyle(4,0xff,0.5);

                graphics.moveTo(v1.x*v1min + v2.x*v2min, v1.y*v1min + v2.y*v2min);
                graphics.lineTo(v1.x*v1max + v2.x*v2min, v1.y*v1max + v2.y*v2min);
                graphics.lineTo(v2.x*v2max + v1.x*v1min + (v1.x*v1max - v1.x*v1min),
                        v2.y*v2max + v1.y*v1min + (v1.y*v1max - v1.y*v1min));
                graphics.lineTo(v2.x*v2max + v1.x*v1min, v2.y*v2max + v1.y*v1min);
                graphics.lineTo(v1.x*v1min + v2.x*v2min, v1.y*v1min + v2.y*v2min);
            }
        }
}
import flash.display.*;

internal class Ball extends Sprite{
        public function Ball(color:int, radius:int){
                graphics.beginFill(color);
                graphics.drawCircle(0,0,radius);
                graphics.endFill();
        }
}