Delaunay三角分割

Delaunay三角分割サンプル

@author termat(http://termat.sakura.ne.jp/)

forked:2
favorite:15
lines:472
license : MIT License
modified : 2010-01-19 02:37:01

Embed: Tweet

package
{
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.MouseEvent;
    import flash.text.TextField;
    import flash.text.TextFieldAutoSize;
    /**
	 *	Delaunay三角分割サンプル
	 *
     * @author termat(http://termat.sakura.ne.jp/)
     */
	[SWF(framerate="30",width="480",height="480",backgroundColor="0x000000")]
	public class Practice05 extends Sprite
	{
		private var list:Vector.<Circle>;
		private var del:Del
		
		public function Practice05():void {
			graphics.lineStyle(2,0xaaaaaa);
			graphics.drawRect(0,0,480,480);
			list = new Vector.<Circle>();
			del = new Del(list);
			addChild(del);
			stage.addEventListener(MouseEvent.CLICK, onClick);
			stage.addEventListener(Event.EXIT_FRAME,update);
		}
		
		private function onClick(e:MouseEvent):void {
			addNode(e.stageX,e.stageY);
		}
		
		private function addNode(x:Number,y:Number):void{
			var vx:Number = Math.random() * 12 - 6;
			if (Math.abs(vx) < 1e-2) vx=1.0;
			var vy:Number = Math.random() * 12 - 6;
			if (Math.abs(vy) < 1e-2) vy=1.0;
			var velo:Number = vx * vx + vy * vy;
			var c:int = Math.floor(Math.random() * 0xffffff);
			var p:Circle = new Circle(x,y,2,c,vx,vy);
			addChild(p);
			list.push(p);
		}	
		private function update(e:Event):void {
			if(this.numChildren<80){
				var xx:Number=Math.random()*480;
				var yy:Number=Math.random()*480;
				addNode(xx,yy);
			}
			for each(var c:Circle in list ) {
				c.update();
			}
			del.update();
		}
	}

}

import flash.display.MovieClip;
import flash.display.Shape;
import flash.display.Sprite;
import flash.geom.Matrix;
import flash.geom.Point;
import flash.display.GradientType;

class Circle extends MovieClip {
	private var vx:Number;
	private var vy:Number;
	private var color:uint;
	
	public function Circle(x:int, y:int, r:int, c:uint, vx:int, vy:int) {
		this.vx = vx;
		this.vy = vy;
		this.x = x;
		this.y = y;
		color = c;
		graphics.lineStyle(2, color) ;
		graphics.beginFill(c);
		graphics.drawCircle(0, 0, r);
		graphics.endFill();
		this.alpha = 0.5;
	}
	
	public function getLineColor():uint {
		return color;
	}
	
	public function update():void {
		var div:Number;
		if (x + vx < 0) {
			div = Math.abs((x + vx)/vx);
			vx *= -1;
			x = x + vx * div;
		}else if (x + vx > 480) {
			div= Math.abs((x + vx - 480) / vx);
			vx *= -1;
			x = x + vx * div;
		}else {
			x += vx;
		}
		if (y + vy < 0) {
			div = Math.abs((y + vy)/vy);
			vy *= -1;
			y = y + vy * div;
		}else if (y + vy > 480) {
			div= Math.abs((y + vy-480)/vy);
			vy *= -1;
			y = y + vy * div;
		}else {
			y += vy;
		}
	}
}

class Del extends Sprite {
	private var list:Vector.<Circle>;
	private var del:Delaunay;
	private var matrix:Matrix=new Matrix();
	
	public function Del(l:Vector.<Circle>):void {
		list = l;
		del = new Delaunay(0, 0, 480, 480);
	}
	
	public function update():void {
		while(this.numChildren > 0) removeChildAt(this.numChildren - 1);
		del.clear();
		for each(var c:Circle in list) {
			var p:Point = new Point(c.x, c.y);
			del.insert(p);
		}
		var n:Vector.<Point> = del.getNode();
		var e:Vector.<Array> = del.getElem();
		for each(var ee:Array in e) {
			addChild(
				getLines(n[ee[0]], n[ee[1]], n[ee[2]],
					list[ee[0]].getLineColor(),list[ee[1]].getLineColor(),list[ee[2]].getLineColor()));
		}
	}
	
	private function getLines(p0:Point, p1:Point, p2:Point, c0:uint, c1:uint, c2:uint):Shape {
		var ret:Shape = new Shape();
		ret.graphics.lineStyle(1, 0x444444);
		ret.graphics.moveTo(p0.x, p0.y);
		var tp:Number = Math.min(20 / dist(p0, p1), 1.0);
		ret.graphics.lineGradientStyle(GradientType.LINEAR, [c0,c1], [tp,tp], [0, 255], updateMatrix(p0,p1)); 
		ret.graphics.lineTo(p1.x, p1.y);
		tp = Math.min(20 / dist(p1, p2), 1.0);
		ret.graphics.lineGradientStyle(GradientType.LINEAR, [c1,c2], [tp,tp], [0, 255], updateMatrix(p1,p2)); 
		ret.graphics.lineTo(p2.x, p2.y);
		tp = Math.min(20 / dist(p2, p0), 1.0);
		ret.graphics.lineGradientStyle(GradientType.LINEAR, [c2, c0], [tp, tp], [0, 255], updateMatrix(p2,p0)); 
		ret.graphics.lineTo(p0.x, p0.y);
		return ret;
	}
	
	private function dist(p0:Point,p1:Point):Number {
		var xx:Number = p0.x - p1.x;
		var yy:Number = p0.y - p1.y;
		return Math.sqrt(xx*xx+yy*yy);
	}
	
	private function updateMatrix(p0:Point, p1:Point):Matrix {
		matrix.createGradientBox(p1.x - p0.x, p1.y - p0.y, 0, p0.x, p0.y);
		return matrix;
	}
}
import flash.geom.Point;
import flash.geom.Rectangle;
	
class Delaunay
{
	private var EPS:Number = 1e-16;
	private var rect:Rectangle;
	private var min:Number;
	private var max:Number;
	private var data:Vector.<Point>;
	private var node:Vector.<Point>;
	private var elem:Array;
	private var map:Array;
	private var stack:Array;
	private var boundary:Array;
	private var boundaryID:Array;
	private var ids:int;
	private var bs:int;
		
	public function Delaunay(x:Number, y:Number, w:Number, h:Number ):void {
		rect= new Rectangle(x, y, w, h);
		min = Math.min(x,y,x+w,y+h);
		max = Math.max(x,y,x+w,y+h);
		data=new Vector.<Point>();
		node=new Vector.<Point>();
		elem=new Array();
		map=new Array();
		stack=new Array();
		boundary=new Array();
		boundaryID=new Array();
		node.push(new Point(-1.23,-0.5));
		node.push(new Point(2.23,-0.5));
		node.push(new Point(0.5,2.5));
		elem.push(new Array(0,1,2));
		map.push(new Array(-1,-1,-1));
		ids=0;
		bs=1;
	}
		
	public function clear():void {
		data=new Vector.<Point>();
		node=new Vector.<Point>();
		elem=new Array();
		map=new Array();
		stack=new Array();
		boundary=new Array();
		boundaryID=new Array();
		node.push(new Point(-1.23,-0.5));
		node.push(new Point(2.23,-0.5));
		node.push(new Point(0.5,2.5));
		elem.push(new Array(0,1,2));
		map.push(new Array( -1, -1, -1));
		ids=0;
		bs=1;
	}
		
	private function getTriangleById():Array {
		var et:Array=new Array();
		var id:int=0;
		for(var i:int=0;i<elem.length;i++){
			if(!checkBounds(i)){
				et.push(-1);
			}else if(!checkBoundaryState(i)){
				et.push(-1);
			}else{
				et.push(id++);
			}
		}
		var ee:Array=new Array();
		for(i=0;i<et.length;i++){
			var e:Array=this.elem[i];
			if(et[i]!=-1){
				ee.push(new Array(e[0]-3,e[1]-3,e[2]-3));
			}
		}
		return ee;
	}
	private function getTriangleMapById():Array {
		var et:Array=new Array();
		var id:int=0;
		for(var i:int=0;i<elem.length;i++){
			if(!checkBounds(i)){
				et.push(-1);
			}else if(!this.checkBoundaryState(i)){
				et.push(-1);
			}else{
				et.push(id++);
			}
		}
		var ee:Array=new Array();
		var tp:Array=new Array();
		for(i=0;i<et.length;i++){
			var m:Array=map[i];
			if(et[i]!=-1){
				for(var j:int=0;j<m.length;j++){
					if(m[j]==-1){
						tp[j]=-1;
					}else{
						tp[j]=et[m[j]];
					}
				}
				ee.push(new Array(tp[0],tp[1],tp[2]));
			}
		}
		return ee;
	}
	
	private function isLeft(a:Point,b:Point,p:Point):Number{
		var v0:Number=(a.y-p.y)*(b.x-p.x);
		var v1:Number=(a.x-p.x)*(b.y-p.y);
		if(Math.abs(v1-v0)<this.EPS){
			return 0;
		}else{
			return (v1-v0);
		}
	}

public function getLocation(id:int, p:Point):int {
		var e:Array=elem[id];
		for(var i:int=0;i<e.length;i++){
			var a:Point=node[e[i]];
			var b:Point=node[e[(i+1)%3]];
			if(isLeft(a,b,p)<0){
				var n:int=map[id][i];
				if(n==-1){
					return -1;
				}
				return getLocation(n,p);
			}
		}
		return id;
	}
	
	private function checkBoundaryState(id:int):Boolean {
		if(bs>1){
			if(!checkBounds(id))return false;
		}
		var e:Array=elem[id];
		for (var i:int = 0; i < e.length; i++) {
			if(typeof boundaryID[e[i]]=="undefined")continue;
			var b0:int = boundaryID[e[i]];
			if(typeof boundaryID[e[(i + 1) % 3]]=="undefined")continue;
			var b1:int = boundaryID[e[(i + 1) % 3]];
			if (b0 - b1 == 0) {
				if(typeof boundary[e[(i + 1) % 3]]=="undefined")continue;
				var v0:int = boundary[e[(i + 1) % 3]];
				if(v0==e[i]){
					return false;
				}
			}
		}
		return true;
	}
	
	private function edge(elemId:int, targetId:int, mp:Array ):int {
		var j:Array=mp[elemId];
		for(var i:int=0;i<j.length;i++){
			if(j[i]==targetId)return i;
		}
		return -1;
	}

private function isSwap(aId:int , bId:int, cId:int, pId:int):Boolean {
		var x13:Number=node[aId].x-node[cId].x;
		var y13:Number=node[aId].y-node[cId].y;
		var x23:Number=node[bId].x-node[cId].x;
		var y23:Number=node[bId].y-node[cId].y;
		var x1p:Number=node[aId].x-node[pId].x;
		var y1p:Number=node[aId].y-node[pId].y;
		var x2p:Number=node[bId].x-node[pId].x;
		var y2p:Number=node[bId].y-node[pId].y;
		var cosa:Number=x13*x23+y13*y23;
		var cosb:Number=x2p*x1p+y1p*y2p;
		if(cosa>=0&&cosb>=0){
			return false;
		}else if(cosa<0&&cosb<0){
			return true;
		}else{
			var sina:Number=x13*y23-x23*y13;
			var sinb:Number=x2p*y1p-x1p*y2p;
			if((sina*cosb+sinb*cosa)<0){
				return true;
			}else{
				return false;
			}
		}
	}

public function getNode():Vector.<Point> {
		return data;
	}
	
	public function getElem():Vector.<Array> {
		var ret:Vector.<Array> = new Vector.<Array>();
		for each(var e:Array in elem) {
			if(e[0]<3||e[1]<3||e[2]<3){
				continue;
			}else{
				ret.push(new Array(e[0]-3, e[1]-3, e[2]-3));
			}
		}
		return ret;
	}

private function normalize(x:Number, y:Number):Point {
		var xx:Number = (x - min) / (max - min);
		var yy:Number = (y - min) / (max - min);
		return new Point(xx,yy);
	}

private function checkBounds(id:int):Boolean {
		var e:Array=elem[id];
		if(e[0]<3||e[1]<3||e[2]<3){
			return false;
		}else{
			return true;
		}
	}

public function insert(pos:Point):Boolean {
		if (!rect.containsPoint(pos)) return false;
		var p:Point=normalize(pos.x,pos.y);
		ids = getLocation(ids, p);
		if(ids==-1){
			ids=0;
			return false;
		}else {
			if (checkBoundaryState(ids)) {
				data.push(pos);
				node.push(p);
				process(ids, node.length - 1);
				return true;
			}else {
				return false;
			}
		}
	}

public function addBoundary(arg:Array,isClose:Boolean):void {
		var sz:int= node.length;
		for(var i:int=0;i<arg.length;i++){
			var p:Point=normalize(arg[i].x,arg[i].y);
			ids=getLocation(ids,p);
			if(ids==-1){
				ids=0;
				continue;
			}
			if(checkBoundaryState(ids)){
				data.push(arg[i]);
				node.push(p);
				if(i>0){
					boundary[sz+i-1]=sz+i;
					boundaryID[sz+i-1]=bs;
				}
				process(ids,node.length-1);
			}
		}
		if(isClose){
			boundary[node.length-1]=sz;
			boundaryID[node.length-1]=bs;
		}
		bs++;
	}
	
	private function isBoundary(nodeId0:int , nodeId1:int):Boolean {
		var p:int=boundary[nodeId0];
		if(!(typeof boundary[nodeId0]=="undefined")&&p==nodeId1)return true;
		p=boundary[nodeId1];
		if(!(typeof boundary[nodeId1]=="undefined")&&p==nodeId0){
			return true;
		}else{
			return false;
		}	
	}

private function process(elemId:int, nodeId:int):void {
		var nn:int=elem.length;
		var em:Array=elem[elemId];
		var te:Array=new Array(em[0],em[1],em[2]);
		var e0:Array=new Array(nodeId,em[0],em[1]);
		var e1:Array=new Array(nodeId,em[1],em[2]);
		var e2:Array=new Array(nodeId,em[2],em[0]);
		em[0]=e0[0];em[1]=e0[1];em[2]=e0[2];
		elem.push(e1);
		elem.push(e2);
		var jm:Array=map[elemId];
		var tmp:Array=new Array(jm[0],jm[1],jm[2]);
		var j0:Array=new Array(nn+1,jm[0],nn);
		var j1:Array=new Array(elemId,jm[1],nn+1);
		var j2:Array=new Array(nn,jm[2],elemId);
		jm[0]=j0[0];jm[1]=j0[1];jm[2]=j0[2];
		map.push(j1);
		map.push(j2);
		if(tmp[0]!=-1){
			if(!isBoundary(te[0],te[1]))stack.push(elemId);
		}
		if(tmp[1]!=-1){
			var ix:int=edge(tmp[1],elemId,map);
			map[tmp[1]][ix]=nn;
			if(!isBoundary(te[1],te[2]))stack.push(nn);
		}
		if(tmp[2]!=-1){
			ix=edge(tmp[2],elemId,map);
			map[tmp[2]][ix]=nn+1;
			if(!isBoundary(te[2],te[0]))stack.push(nn+1);
		}
		while (stack.length > 0) {
			var il:int=stack.pop();
			var ir:int=map[il][1];
			var ierl:int=edge(ir,il,map);
			var iera:int=(ierl+1)%3;
			var ierb:int=(iera+1)%3;
			var iv1:int=elem[ir][ierl];
			var iv2:int=elem[ir][iera];
			var iv3:int=elem[ir][ierb];
			if(isSwap(iv1,iv2,iv3,nodeId)){
				var ja:int=map[ir][iera];
				var jb:int=map[ir][ierb];
				var jc:int=map[il][2];
				elem[il][2]=iv3;
				map[il][1]=ja;
				map[il][2]=ir;
				var picElem:Array=elem[ir];
				picElem[0]=nodeId;picElem[1]=iv3;picElem[2]=iv1;
				picElem=map[ir];
				picElem[0]=il;picElem[1]=jb;picElem[2]=jc;
				if(ja!=-1){
					ix=edge(ja,ir,map);
					map[ja][ix]=il;
					if(!isBoundary(iv2,iv3))stack.push(il);
				}
				if(jb!=-1){
					if(!isBoundary(iv3,iv1))stack.push(ir);
				}
				if(jc!=-1){
					ix=edge(jc,il,this.map);
					map[jc][ix]=ir;
				}
			}
		}
	}
}

Code Fullscreen

Preview Fullscreen