ボロノイ領域分割

離散ボロノイ図の勉強．
離散ボロノイ領域分割を(http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/voronoi-diagram/index.html)を参考に実装したもの．

クリックで点を打って，10個入力したらボロノイ領域を計算．

by Dorara 19 Jan 2011

Tags

ボロノイ
Embed

/**
 * Copyright Dorara ( http://wonderfl.net/user/Dorara )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/xG7M
 */

package 
{
    import flash.display.*;
    import flash.events.*;
    
    [SWF(width="465", height="465")]
    public class Main extends Sprite 
    {
        private var pts:Array; //母点情報
        private var sp:Sprite; //点を表示するsprite
        private var canvas:BitmapData; //領域を表示するBitmapData
        
        public function Main():void 
        {
            if (stage) init();
            else addEventListener(Event.ADDED_TO_STAGE, init);
        }
        
        //ここからはじまれ
        private function init(e:Event = null):void 
        {
            removeEventListener(Event.ADDED_TO_STAGE, init);
            
            this.stage.scaleMode = StageScaleMode.NO_SCALE;
            this.stage.align = StageAlign.TOP_LEFT;
            
            pts = new Array();
            sp = new Sprite();
            this.addChild(sp);
            
            canvas = new BitmapData(this.stage.stageWidth, this.stage.stageHeight, false);
            
            this.stage.addEventListener(MouseEvent.CLICK, onClick);
        }
        
        //マウスクリック時の処理
        private function onClick(e:MouseEvent):void 
        {
            pts.push( { x:mouseX, y:mouseY } );
            trace(mouseX.toString() + "," + mouseY.toString());
            sp.graphics.beginFill(0x0);
            sp.graphics.drawCircle(mouseX, mouseY, 2);
            sp.graphics.endFill();
            
            if (pts.length >= 10) {
                this.stage.removeEventListener(MouseEvent.CLICK, onClick);
                draw();
            }
        }
        
        //母点から(離散)ボロノイ領域を計算する
        private function draw(): void
        {
            //領域の色を決める
            var colormap:Array = new Array();
            for (var l:int = 0; l < pts.length; l++) 
            {
                colormap.push(0xffffff * Math.random());
            }
            
            //すべての点について，最近傍母点を見つける
            trace("draw");
            for (var i:int = 0; i < this.stage.stageHeight; i++) 
            {
                for (var j:int = 0; j < this.stage.stageWidth; j++) 
                {
                    var min_d:Number = Number.MAX_VALUE;
                    var min_id:int = -1;
                    for (var k:int = 0; k < pts.length; k++) 
                    {
                        var dx:Number = pts[k].x - j;
                        var dy:Number = pts[k].y - i;
                        var d:Number = Math.sqrt(dx * dx + dy * dy);
                        if (d < min_d) {
                            min_id = k;
                            min_d = d;
                        }
                        
                    }
                    //色はcolormapで決められた色
                    canvas.setPixel32(j, i, colormap[min_id]);
                }
            }
            trace("finished...");
            this.addChild(new Bitmap(canvas));
            this.setChildIndex(sp, this.numChildren - 1);
        }
    }
    
}