スポンサーサイト

-------- | --:--

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[ActionScript 3.0] 点集合の凸包

2007-12-11 | 20:32

凸包の定義とそれを求めるアルゴリズムはこちらを参照。

package
{
    import flash.display.*;
    import flash.geom.*;
    import flash.events.*;
    import flash.utils.*;

    [SWF(width="500", height="500", framerate="30", backgroundColor="#ffffff")]
        public class Convex extends Sprite
        {
            public var vertexes:Array;

            private var balls:Array;

            public function Convex()
            {
                balls = new Array();
                for(var i:int = 0 ; i < 100 ; i++){
                    var b:Ball = new Ball(0xff00, 5);
                    b.x = Math.random()*500;
                    b.y = Math.random()*500;
                    b.vx = Math.random()*3+1;
                    b.vy = Math.random()*3+1;
                    addChild(b);
                    balls.push(b);
                }

                addEventListener(Event.ENTER_FRAME, loop);
            }

            private function loop(event:*):void
            {
                var points:Array = [];
                for each (var b:Ball in balls){
                    b.move();
                    points.push(new Point(b.x,b.y));
                }

                var convex:Array = ConvexHull.getConvexHull(points);
                graphics.clear();
                graphics.beginFill(0xff, 0.2);
                graphics.lineStyle(1, 0xff, 0.5);
                graphics.moveTo(convex[0].x, convex[0].y);
                for(var i:int = 1; i < convex.length ; i++){
                    graphics.lineTo(convex[i].x, convex[i].y);
                }
                graphics.lineTo(convex[0].x, convex[0].y);
                graphics.endFill();
            }
        }
}

import flash.display.*;
internal class Ball extends Sprite{
    public var vx:int = 2;
    public var vy:int = 2;
    public var radius:int;
    public var currentColor:int;
    public function Ball(c:Number=0, radius:Number = 0){
        graphics.lineStyle(1, 0, 0.5);
        graphics.beginFill(c);
        graphics.drawCircle(0,0,radius);
        graphics.endFill();
        this.radius = radius;
    }

    public function set color(c:int):void{
        if(currentColor != c){
            currentColor = c;
            graphics.clear();
            graphics.lineStyle(1, 0, 0.5);
            graphics.beginFill(currentColor);
            graphics.drawCircle(0,0,radius);
            graphics.endFill();
        }
    }

    public function move():void{
        x += vx;
        y += vy;
        if(x < 0 || x > 500)
            vx *= -1;
        if(y < 0 || y > 500)
            vy *= -1;
    }
}

import flash.geom.*;
internal class ConvexHull{
    public static function getConvexHull(points:Array):Array {

        var result:Array = [];
        var index:int;
        var topIndex:int;

        // 先頭のインデックスを求める
        var p1:Point = new Point(-100,-100);
        var p2:Point = new Point(0,-100);
        topIndex = index = getNextIndex(points, p2, p1, -1);

        var cnt:int = 0;
        while(cnt++ <= points.length){
            p1 = p2;
            p2 = points[index];
            result.push(p2);

            index = getNextIndex(points, p2, p1, index);
            if(index == topIndex)
                break;
        }

        return result;
    }

    private static function distance( p1:Point, p2:Point ):Number{
        var dx:Number = p2.x - p1.x;
        var dy:Number = p2.y - p1.y;
        return Math.sqrt( dx*dx+ dy*dy );
    }

    private static function getNextIndex(points:Array, p2:Point, p1:Point, myself:int):int{
        var minIndex:int = 0;
        var min:Number = Math.PI*2;
        var minLen:Number = -1;
        var v1:Point = new Point(p2.x - p1.x, p2.y - p1.y);

        for( var j:int =0; j < points.length; j++ ) {
            if(j != myself){
                var v2:Point = new Point(points[j].x - p2.x, points[j].y - p2.y);

                var rad:Number = getTheta(v1, v2);

                // 角度が同じ場合、近いほうを優先
                if(rad == min){
                    if(distance(points[j], p2) < minLen){
                        minIndex = j;
                        min = rad;
                        minLen = distance(points[j], p2);
                    }
                }else if(rad < min){
                    minIndex = j;
                    min = rad;
                    minLen = distance(points[j], p2);
                }
            }
        }
        return minIndex;
    }

    private static function getTheta(p1:Point, p2:Point):Number{
        var len1:Number =  Math.sqrt(p1.x*p1.x + p1.y*p1.y);
        var len2:Number =  Math.sqrt(p2.x*p2.x + p2.y*p2.y);
        if(len1 == 0 || len2==0)
            return 0;
        p1.x = p1.x/len1;
        p1.y = p1.y/len1;
        p2.x = p2.x/len2;
        p2.y = p2.y/len2;

        var dot:Number = p1.x*p2.x + p1.y*p2.y;
        var theta:Number = Math.acos(dot);
        return theta;
    }
}


スポンサーサイト
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。