/**
まいど同じ画像でスイマセン
mariroomの顔をポリゴン化しちゃいましょう（手動で）

作例：
http://movapic.com/fumix/pic/959331

参照：
ドロネー図
http://ja.wikipedia.org/wiki/ドロネー図
ドロネー図の作図方法
http://homepage3.nifty.com/endou/tips/04/tips33.htm
外接円
http://wonderfl.net/code/ad8b6c5010abdb44d3e34d3a7cd06a200b35175d
.fla2「YuruYurer」（195P）
http://www.amazon.co.jp/dp/4862670717
内接円を求める
http://homepage1.nifty.com/MADIA/delphi/delphi_bbs/200706/200706_07060041.html
ヘロンの公式
http://ja.wikipedia.org/wiki/ヘロンの公式
 */
package {
    import flash.display.Bitmap;
    import flash.display.BitmapData;
    import flash.display.Graphics;
    import flash.display.Loader;
    import flash.display.Sprite;
    import flash.display.StageQuality;
    import flash.display.StageScaleMode;
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.net.URLRequest;
    import flash.system.LoaderContext;

[SWF(width = 465, height = 465, backgroundColor = 0xFFFFFF, frameRate = 60)]

public class Delaunay extends Sprite {

//----------------------------------------
        //CONST

private const IMAGE_URL : String = "http://farm4.static.flickr.com/3639/3538831894_cca4aabd68.jpg";

//----------------------------------------
        //VARIABLES
        
        //点群
        private var _points : Array;
        //三角形の集まり
        private var _triangles : Array;
        //キャンバス
        private var _canvas : Sprite;
        //画像
        private var _image : Bitmap;
        private var _imageData : BitmapData;

//ボタン
        private var _renderButton : Button;
        private var _imageButton : Button;
        //フラグ
        private var _renderFlag : int;

/*
         * コンストラクタ
         */
        public function Delaunay() {
            //初期化
            addEventListener(Event.ADDED_TO_STAGE, _initialize);
        }

/*
         * 初期化
         */
        private function _initialize(event : Event) : void {
            removeEventListener(Event.ADDED_TO_STAGE, _initialize);

stage.scaleMode = StageScaleMode.NO_SCALE;
            stage.quality = StageQuality.LOW;                
            
            //画像の読み込み
            var req : URLRequest = new URLRequest(IMAGE_URL);
            var loader : Loader = new Loader();
            loader.contentLoaderInfo.addEventListener(Event.COMPLETE, loadComplete);    
            loader.load(req, new LoaderContext(true));
        }

/*
         * 画像読み込み終了後
         */
        private function loadComplete(event : Event) : void {

event.target.removeEventListener(Event.COMPLETE, loadComplete);
            
            _image = event.target.loader.content as Bitmap;
            _imageData = _image.bitmapData;
            
            //画像を表示
            addChild(_image);
                    
            //ドロー用
            _canvas = addChild(new Sprite()) as Sprite;
            
            var stageWidth : Number = stage.stageWidth;
            var stageHeight : Number = stage.stageHeight;

//ボタン
            _renderFlag = 0;
            _renderButton = new Button('render', 60);
            _renderButton.addEventListener(MouseEvent.CLICK, onRenderHandler);
            _renderButton.x = stageWidth - 60;
            addChild(_renderButton);

_imageButton = new Button('image', 60);
            _imageButton.addEventListener(MouseEvent.CLICK, onImageHandler);
            _imageButton.x = stageWidth - 60;
            _imageButton.y = _renderButton.height + 1;
            addChild(_imageButton);

_points = new Array();
            _triangles = new Array();
            //_points生成

//ステージの大きさの三角形2つを用意
            _points.push(new Node(0, 0, 0));
            _points.push(new Node(1, stageWidth, 0));
            _points.push(new Node(2, stageWidth, stageHeight));
            _points.push(new Node(3, 0, stageHeight));
            _triangles.push(new Triangle(_points[0], _points[1], _points[2]));
            _triangles.push(new Triangle(_points[0], _points[2], _points[3]));

addEventListener(Event.ENTER_FRAME, _updateHandler);
            stage.addEventListener(MouseEvent.MOUSE_UP, _stageMouseUpHandler);
        }

private function onImageHandler(event : MouseEvent) : void {
            _image.visible = !_image.visible;
        }

private function onRenderHandler(event : MouseEvent) : void {
            _renderFlag ++;
            if(_renderFlag >2){
             _renderFlag = 0;   
            }
        }

/*
         * アップデート
         */
        private function _updateHandler(event : Event) : void {
            _interaction();
            _draw();
        }

/*
         * インタラクション
         */
        private function _interaction() : void {
            //一時保持の三角形群
            var localTriangles : Array = new Array();
            //辺
            var edges : Array;
            //多角形
            var polygon : Array;
            //ポイント群ループ
            for (var k : int = 4;k < _points.length;k++) {
                var node : Node = _points[k];
                localTriangles = new Array();
                edges = new Array();
            
                for (var i : String in _triangles) {
                    //点が外接円
                    var tri : Triangle = _triangles[i];
                    if(inOuterCircle(node.point.x, node.point.y, tri)) {
                        edges.push(new Edge(tri.node0, tri.node1));
                        edges.push(new Edge(tri.node1, tri.node2));
                        edges.push(new Edge(tri.node2, tri.node0));
                    } else {
                        localTriangles.push(tri);                        
                    }                
                }
                //edgesからpolygonを作る（重複辺の削除
                polygon = new Array();
                for (i in edges) {
                    var edge0 : Edge = edges[i];
                    //重複チェック
                    var flg : Boolean = false;
                    for (var j : String in polygon) {
                        var edge1 : Edge = polygon[j];
                        if(judgeEdges(edge0, edge1)) {
                            flg = true;
                            polygon.splice(j, 1);
                            break;                        
                        }
                    }
                    //データが存在しない場合は追加
                    if(!flg) polygon.push(edges[i]);
                }
                //polygonから三角形を作って挿入
                for (i in polygon) {
                    var tri1 : Triangle = new Triangle(polygon[i].node0, polygon[i].node1, node);
                    localTriangles.push(tri1);
                }
                if(localTriangles.length > 1) _triangles = localTriangles;
            }
        }

/*
         * 同じ辺かどうかの判定
         */
        private function judgeEdges(edge : Edge, edge0 : Edge) : Boolean {            
            if(edge.node0.id == edge0.node0.id && edge.node1.id == edge0.node1.id) {
                return true;                
            }
            if(edge.node1.id == edge0.node0.id && edge.node0.id == edge0.node1.id) {
                return true;
            }
            return false;
        }

/*
         * 描画
         */
        private function _draw() : void {
            var g : Graphics = _canvas.graphics;
            g.clear();
            
            //三角形群のループ
            for (var i : int = 0;i < _triangles.length;i++) {
                
                var tri : Triangle = _triangles[i];
                //四隅のポイントを含む三角形は描画しない
                if(!(tri.node0.id == 0 || tri.node1.id == 0 || tri.node2.id == 0 || tri.node0.id == 1 || tri.node1.id == 1 || tri.node2.id == 1 || tri.node0.id == 2 || tri.node1.id == 2 || tri.node2.id == 2 || tri.node0.id == 3 || tri.node1.id == 3 || tri.node2.id == 3)
                                ) {
                    if(_renderFlag == 0) {
                        _noRenderDraw(tri, g);
                    } else if(_renderFlag == 1) {
                        _renderDraw(tri, g);
                    } else {
                        _circleRenderDraw(tri, g);
                    }
                }
            }
        }

private function _renderDraw(tri : Triangle,g : Graphics) : void {
            var fillColor : uint = _imageData.getPixel(tri.innerCirclePoint.x, tri.innerCirclePoint.y);
            g.beginFill(fillColor);
            g.moveTo(tri.node0.point.x, tri.node0.point.y);
            g.lineTo(tri.node1.point.x, tri.node1.point.y);
            g.lineTo(tri.node2.point.x, tri.node2.point.y);
            g.lineTo(tri.node0.point.x, tri.node0.point.y);
            g.endFill();
        }
        private function _circleRenderDraw(tri : Triangle,g : Graphics) : void {
            var fillColor : uint = _imageData.getPixel(tri.innerCirclePoint.x, tri.innerCirclePoint.y);
            g.beginFill(fillColor);
            g.drawCircle(tri.innerCirclePoint.x, tri.innerCirclePoint.y,tri.innerCircleRadius);
            g.endFill();
        }

private function _noRenderDraw(tri : Triangle,g : Graphics) : void {
            g.lineStyle(1, 0xff0000);
            g.moveTo(tri.node0.point.x, tri.node0.point.y);
            g.lineTo(tri.node1.point.x, tri.node1.point.y);
            g.lineTo(tri.node2.point.x, tri.node2.point.y);
            g.lineTo(tri.node0.point.x, tri.node0.point.y);
        }

/*
         * 外接円の内か外か
         */
        static function inOuterCircle(x : Number,y : Number,tri : Triangle) : Boolean {
            var node0 : Node = tri.node0;
            var node1 : Node = tri.node1;
            var node2 : Node = tri.node2;
            
            var d : Number = (node0.point.x * node0.point.x + node0.point.y * node0.point.y - x * x - y * y) * ((node1.point.x - x) * (node2.point.y - y) - (node2.point.x - x) * (node1.point.y - y)) + (node1.point.x * node1.point.x + node1.point.y * node1.point.y - x * x - y * y) * ((node2.point.x - x) * (node0.point.y - y) - (node2.point.y - y) * (node0.point.x - x)) + (node2.point.x * node2.point.x + node2.point.y * node2.point.y - x * x - y * y) * ((node0.point.x - x) * (node1.point.y - y) - (node0.point.y - y) * (node1.point.x - x));
            return ( (node1.point.x - node0.point.x) * (node2.point.y - node0.point.y) - (node1.point.y - node0.point.y) * (node2.point.x - node0.point.x) > 0 ) ? d > 0 : d <= 0;
        }

/*
         * マウスクリック時
         */
        private function _stageMouseUpHandler(event : MouseEvent) : void {
            if((stage.stageWidth - 60) > mouseX) {
                _points.push(new Node(_points.length, mouseX, mouseY));
            }
        }
    }
}

import flash.display.Graphics;
import flash.display.Shape;
import flash.display.SimpleButton;
import flash.display.Sprite;
import flash.geom.Point;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
import flash.text.TextFormat;
import flash.text.TextFormatAlign;

class Triangle {
    private var _node0 : Node;
    private var _node1 : Node;
    private var _node2 : Node;
    private var _innerCirclePoint : Point;
    private var _InnerCircleRadius : Number;

public function Triangle(node0 : Node,node1 : Node,node2 : Node) : void {
        _node0 = node0;
        _node1 = node1;
        _node2 = node2;
        _innerCirclePoint = addInnerCirclePoint();
        _InnerCircleRadius = addInnerCircleRadius();
    }

/*
     * 内接円の中心
     */
    private function addInnerCirclePoint() : Point {
        var x1 : Number = node0.point.x;
        var y1 : Number = node0.point.y;
        var x2 : Number = node1.point.x;
        var y2 : Number = node1.point.y;
        var x3 : Number = node2.point.x;
        var y3 : Number = node2.point.y;
        var a : Number = Math.sqrt((x3 - x2) * (x3 - x2) + (y3 - y2) * (y3 - y2));
        var b : Number = Math.sqrt((x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1));
        var c : Number = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
        var px : Number = (1 / (a + b + c)) * (a * x1 + b * x2 + c * x3);
        var py : Number = (1 / (a + b + c)) * (a * y1 + b * y2 + c * y3);
            
        return new Point(px, py);
    }

/*
     * 内接円の半径
     */
    private function addInnerCircleRadius() : Number {
        var x1 : Number = node0.point.x;
        var y1 : Number = node0.point.y;
        var x2 : Number = node1.point.x;
        var y2 : Number = node1.point.y;
        var x3 : Number = node2.point.x;
        var y3 : Number = node2.point.y;
        var a : Number = Math.sqrt((x3 - x2) * (x3 - x2) + (y3 - y2) * (y3 - y2));
        var b : Number = Math.sqrt((x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1));
        var c : Number = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
        var s : Number = (a + b + c) * 0.5;
        var ss : Number = Math.sqrt(s * (s - a) * (s - b) * (s - c));
        var r : Number = 2 * ss / (a + b + c);
            
        return r;
    }

public function get node0() : Node {
        return _node0;
    }

public function get node1() : Node {
        return _node1;
    }

public function get node2() : Node {
        return _node2;
    }

public function get innerCirclePoint() : Point {
        return _innerCirclePoint;
    }

public function get innerCircleRadius() : Number {
        return _InnerCircleRadius;
    }
}

class Node {
    private var _id : int;
    private var _point : Point;

public function Node(id : int,x : Number,y : Number) {
        _id = id;
        _point = new Point(x, y);
    }

public function get id() : int {
        return _id;
    }

public function get point() : Point {
        return _point;
    }
}

class Edge {
    private var _node0 : Node;
    private var _node1 : Node;

public function Edge(node0 : Node,node1 : Node) : void {
        _node0 = node0;
        _node1 = node1;
    }

public function get node0() : Node {
        return _node0;
    }

public function get node1() : Node {
        return _node1;
    }
}

class Button extends SimpleButton {

public function Button(label : String, width : int = 0) : void {
        var up : Sprite = _buildImage(label, 0x0, width);
        var over : Sprite = _buildImage(label, 0x333333, width);
        var down : Sprite = _buildImage(label, 0x333333, width);
        down.y = 1;
        super(up, over, down, up);
    }

private static function _buildImage(label : String, color : int, width : int = 0) : Sprite {
        var text : TextField = new TextField();
        text.defaultTextFormat = new TextFormat('Verdana', 10, 0xffffff, true, null, null, null, null, TextFormatAlign.CENTER);
        text.autoSize = TextFieldAutoSize.LEFT;
        text.selectable = false;
        text.text = label;
        text.x = (width - text.width) >> 1;
        text.y = 5;
        var base : Shape = new Shape();
        var g : Graphics = base.graphics;
        g.beginFill(color);
        g.drawRect(0, 0, width, text.height + 10);
        g.endFill();
        var sp : Sprite = new Sprite();
        sp.addChild(base);
        sp.addChild(text);
        return sp;
    }
}

ポリゴンmariroom