Forked from:: fumix's ドロネー図（分割）

内接円付きドロネー図（分割）

画面を適当にクリックすると3クリック以降、ポイントと線がひかれます。
線は交差すること無くひかれていきます

参照：
ドロネー図
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/ヘロンの公式

fumix

forked:2
favorite:14
lines:198
license : MIT License
modified : 2009-12-07 02:12:54

Embed: Tweet

// forked from fumix's ドロネー図（分割）
/**
画面を適当にクリックすると3クリック以降、ポイントと線がひかれます。
線は交差すること無くひかれていきます

参照：
ドロネー図
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.Graphics;
	import flash.display.Sprite;
	import flash.display.StageQuality;
	import flash.display.StageScaleMode;
	import flash.events.Event;
	import flash.events.MouseEvent;
	import flash.geom.Point;

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

public class Delaunay extends Sprite {

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

/*
		 * コンストラクタ
		 */
		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 stageWidth : Number = stage.stageWidth;
			var stageHeight : Number = stage.stageHeight;

//ドロー用
			_canvas = addChild(new Sprite()) as Sprite;

_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 _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;
			var offset : Number = 0;
			g.clear();
			g.lineStyle(1, 0xffffff);
			
			//三角形群のループ
			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)
								) {
					g.moveTo(tri.node0.point.x + offset, tri.node0.point.y + offset);
					g.lineTo(tri.node1.point.x + offset, tri.node1.point.y + offset);
					g.lineTo(tri.node2.point.x + offset, tri.node2.point.y + offset);
					g.lineTo(tri.node0.point.x + offset, tri.node0.point.y + offset);
					g.beginFill(0xFF0000);
					g.drawCircle(tri.node0.point.x + offset, tri.node0.point.y + offset, 3);
					g.drawCircle(tri.node1.point.x + offset, tri.node1.point.y + offset, 3);
					g.drawCircle(tri.node2.point.x + offset, tri.node2.point.y + offset, 3);
					g.endFill();
					//内接円の描画
					var innerCirclePoint : Point = addInnerCircle(tri);
					g.drawCircle(innerCirclePoint.x, innerCirclePoint.y, addInnerCircleRadius(tri));
				}
			}
		}

/*
		 * 外接円の内か外か
		 */
		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 {
			_points.push(new Node(_points.length, mouseX, mouseY));
		}
		/*
		 * 内接円の中心
		 */
		static function addInnerCircle(tri : Triangle) : Point {
			var x1 : Number = tri.node0.point.x;
			var y1 : Number = tri.node0.point.y;
			var x2 : Number = tri.node1.point.x;
			var y2 : Number = tri.node1.point.y;
			var x3 : Number = tri.node2.point.x;
			var y3 : Number = tri.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);
		}
		/*
		 * 内接円の半径
		 */
		static function addInnerCircleRadius(tri : Triangle) : Number {
			var x1 : Number = tri.node0.point.x;
			var y1 : Number = tri.node0.point.y;
			var x2 : Number = tri.node1.point.x;
			var y2 : Number = tri.node1.point.y;
			var x3 : Number = tri.node2.point.x;
			var y3 : Number = tri.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;
		}
	}
}
class Triangle {
	private var _node0 : Node;
	private var _node1 : Node;
	private var _node2 : Node;
	
	public function Triangle(node0:Node,node1:Node,node2:Node):void {
		_node0 = node0;
		_node1 = node1;
		_node2 = node2;
	}
	
	public function get node0() : Node {
		return _node0;
	}
	
	public function get node1() : Node {
		return _node1;
	}
	
	public function get node2() : Node {
		return _node2;
	}
}
import flash.geom.Point;
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;
	}
}

Code Fullscreen

Preview Fullscreen