flash on 2012-5-10
Delaunay三角分割サンプル
@author termat(http://termat.sakura.ne.jp/)
/**
* Copyright indakung ( http://wonderfl.net/user/indakung )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/h5u2
*/
// forked from termat's Delaunay三角分割
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 {
var lx:int = int(e.stageX / 10) * 10;
var ly:int = int(e.stageY / 10) * 10;
var size:int = 30 + int(Math.random() * 5) * 10;
addNode(lx,ly);
addNode(lx + size, ly );
addNode(lx, ly + size );
addNode(lx + size, ly + size );
/*
addRect( 0, 0, 500, 500 );
addRect( 10, 10, 40, 40 );
addRect( */
}
private function addRect( lx:int, ly:int, lw:int, lh:int ):void{
addNode(lx,ly);
addNode(lx + lw, ly );
addNode(lx, ly + lh );
addNode(lx + lw, ly + lh );
}
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 = 0x000000;//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, 0x000000);
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;
}
}
}
}
}