Last active
November 8, 2015 18:16
-
-
Save termat/3cf4fcc51926e0349804 to your computer and use it in GitHub Desktop.
JavaScriptでDelaunay三角形分割クラスを実装する。 ref: http://qiita.com/t-mat/items/1c571926ccaa7ef1577b
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* JavaScript Delaunay triangulation Class , version 0.1 | |
* | |
* Copyright (c) 2015 t.matsuoka | |
* Released under the MIT license | |
* https://github.com/YukinobuKurata/YouTubeMagicBuyButton/blob/master/MIT-LICENSE.txt | |
* | |
* web site: http://termat.hatenablog.com/ | |
* | |
/*--------------------------------------------------------------------------*/ | |
var termat=termat||{}; | |
termat.Delaunay=function(minX,minY,width,height){ | |
var Delaunay2D=function(minX,minY,width,height){ | |
this.EPS=1e-16; | |
this.minX=minX; | |
this.minY=minY; | |
this.width=width; | |
this.height=height; | |
this.data=[]; | |
this.node=[]; | |
this.elem=[]; | |
this.map=[]; | |
this.stack=[]; | |
this.boundary=[]; | |
this.boundaryID=[]; | |
this.node.push({x:-1.23,y:-0.5,z:0}); | |
this.node.push({x:2.23,y:-0.5,z:0}); | |
this.node.push({x:0.5,y:2.5,z:0}); | |
this.elem.push(new Array(0,1,2)); | |
this.map.push(new Array(-1,-1,-1)); | |
this.ids=0; | |
this.bs=1; | |
}; | |
Delaunay2D.prototype.clear=function(){ | |
this.data=[]; | |
this.node=[]; | |
this.elem=[]; | |
this.map=[]; | |
this.stack=[]; | |
this.boundary=[]; | |
this.boundaryID=[]; | |
this.node.push({x:-1.23,y:-0.5,z:0}); | |
this.node.push({x:2.23,y:-0.5,z:0}); | |
this.node.push({x:0.5,y:2.5,z:0}); | |
this.elem.push(new Array(0,1,2)); | |
this.map.push(new Array(-1,-1,-1)); | |
this.ids=0; | |
this.bs=1; | |
}; | |
Delaunay2D.prototype.getTriangleById=function(){ | |
var et=[]; | |
var id=0; | |
for(var i=0;i<this.elem.length;i++){ | |
if(!this.checkBounds(i)){ | |
et.push(-1); | |
}else if(!this.checkBoundaryState(i)){ | |
et.push(-1); | |
}else{ | |
et.push(id++); | |
} | |
} | |
var ee=[]; | |
for(var i=0;i<et.length;i++){ | |
var e=this.elem[i]; | |
if(et[i]!==-1){ | |
ee.push(new Array(e[0]-3,e[1]-3,e[2]-3)); | |
} | |
} | |
return ee; | |
}; | |
Delaunay2D.prototype.getTriangleMapById=function(){ | |
var et=[]; | |
var id=0; | |
for(var i=0;i<this.elem.length;i++){ | |
if(!this.checkBounds(i)){ | |
et.push(-1); | |
}else if(!this.checkBoundaryState(i)){ | |
et.push(-1); | |
}else{ | |
et.push(id++); | |
} | |
} | |
var ee=[]; | |
var tp=[]; | |
for(var i=0;i<et.length;i++){ | |
var e=this.map[i]; | |
if(et[i]!==-1){ | |
for(var j=0;j<e.length;j++){ | |
if(e[j]===-1){ | |
tp[j]=-1; | |
}else{ | |
tp[j]=et[e[j]]; | |
} | |
} | |
ee.push(new Array(tp[0],tp[1],tp[2])); | |
} | |
} | |
return ee; | |
}; | |
Delaunay2D.prototype.getTriangle=function(){ | |
var et=[]; | |
var id=0; | |
for(var i=0;i<this.elem.length;i++){ | |
if(!this.checkBounds(i)){ | |
et.push(-1); | |
}else if(!this.checkBoundaryState(i)){ | |
et.push(-1); | |
}else{ | |
et.push(id++); | |
} | |
} | |
var ee=[]; | |
for(var i=0;i<et.length;i++){ | |
var e=this.elem[i]; | |
if(et[i]!==-1){ | |
var p0=this.data[e[0]-3]; | |
var p1=this.data[e[1]-3]; | |
var p2=this.data[e[2]-3]; | |
ee.push(new Array(p0,p1,p2)); | |
} | |
} | |
return ee; | |
}; | |
Delaunay2D.prototype.isLeft=function(a,b,p){ | |
var v0=(a.y-p.y)*(b.x-p.x); | |
var v1=(a.x-p.x)*(b.y-p.y); | |
if(Math.abs(v1-v0)<this.EPS){ | |
return 0; | |
}else{ | |
return (v1-v0); | |
} | |
}; | |
Delaunay2D.prototype.getLocation=function(id,p){ | |
var e=this.elem[id]; | |
for(var i=0;i<e.length;i++){ | |
var a=this.node[e[i]]; | |
var b=this.node[e[(i+1)%3]]; | |
if(this.isLeft(a,b,p)<0){ | |
var n=this.map[id][i]; | |
if(n===-1){ | |
return -1; | |
} | |
return this.getLocation(n,p); | |
} | |
} | |
return id; | |
}; | |
Delaunay2D.prototype.checkBoundaryState=function(id){ | |
if(this.bs>1){ | |
if(!this.checkBounds(id))return false; | |
} | |
var e=this.elem[id]; | |
for(var i=0;i<e.length;i++){ | |
var b0=this.boundaryID[e[i]]; | |
var b1=this.boundaryID[e[(i+1)%3]]; | |
if(b0-b1===0){ | |
var v0=this.boundary[e[(i+1)%3]]; | |
if(v0===e[i]){ | |
return false; | |
} | |
} | |
} | |
return true; | |
}; | |
Delaunay2D.prototype.isBoundary=function(nodeId0,nodeId1){ | |
var p=this.boundary[nodeId0]; | |
if(p===nodeId1)return true; | |
var p=this.boundary[nodeId1]; | |
if(p===nodeId0){ | |
return true; | |
}else{ | |
return false; | |
} | |
}; | |
Delaunay2D.prototype.edge=function(elemId,targetId,mp){ | |
var j=mp[elemId]; | |
for(var i=0;i<j.length;i++){ | |
if(j[i]===targetId)return i; | |
} | |
return -1; | |
}; | |
Delaunay2D.prototype.isSwap=function(aId,bId,cId,pId){ | |
var x13=this.node[aId].x-this.node[cId].x; | |
var y13=this.node[aId].y-this.node[cId].y; | |
var x23=this.node[bId].x-this.node[cId].x; | |
var y23=this.node[bId].y-this.node[cId].y; | |
var x1p=this.node[aId].x-this.node[pId].x; | |
var y1p=this.node[aId].y-this.node[pId].y; | |
var x2p=this.node[bId].x-this.node[pId].x; | |
var y2p=this.node[bId].y-this.node[pId].y; | |
var cosa=x13*x23+y13*y23; | |
var cosb=x2p*x1p+y1p*y2p; | |
if(cosa>=0&&cosb>=0){ | |
return false; | |
}else if(cosa<0&&cosb<0){ | |
return true; | |
}else{ | |
var sina=x13*y23-x23*y13; | |
var sinb=x2p*y1p-x1p*y2p; | |
if((sina*cosb+sinb*cosa)<0){ | |
return true; | |
}else{ | |
return false; | |
} | |
} | |
}; | |
Delaunay2D.prototype.normalize=function(x,y,z){ | |
var xx=(x-this.minX)/this.width; | |
var yy=(y-this.minY)/this.height; | |
return {x:xx,y:yy,z:z}; | |
}; | |
Delaunay2D.prototype.checkBounds=function(id){ | |
var e=this.elem[id]; | |
if(e[0]<3||e[1]<3||e[2]<3){ | |
return false; | |
}else{ | |
return true; | |
} | |
}; | |
Delaunay2D.prototype.insert=function(pos){ | |
var p=this.normalize(pos.x,pos.y,pos.z); | |
this.ids=this.getLocation(this.ids,p); | |
if(this.ids===-1){ | |
this.ids=0; | |
return false; | |
}else{ | |
if(this.checkBoundaryState(this.ids)){ | |
this.data.push(pos); | |
this.node.push(p); | |
this.process(this.ids,this.node.length-1); | |
return true; | |
}else{ | |
return false; | |
} | |
} | |
}; | |
Delaunay2D.prototype.addBoundary=function(arg,isClose){ | |
var sz=this.node.length; | |
for(var i=0;i<arg.length;i++){ | |
var p=this.normalize(arg[i].x,arg[i].y); | |
this.ids=this.getLocation(this.ids,p); | |
if(this.ids===-1){ | |
this.ids=0; | |
continue; | |
} | |
if(this.checkBoundaryState(this.ids)){ | |
this.data.push(arg[i]); | |
this.node.push(p); | |
if(i>0){ | |
this.boundary[sz+i-1]=sz+i; | |
this.boundaryID[sz+i-1]=this.bs; | |
} | |
this.process(this.ids,this.node.length-1); | |
} | |
} | |
if(isClose){ | |
this.boundary[this.node.length-1]=sz; | |
this.boundaryID[this.node.length-1]=this.bs; | |
} | |
this.bs++; | |
}; | |
Delaunay2D.prototype.process=function(elemId,nodeId){ | |
var nn=this.elem.length; | |
var em=this.elem[elemId]; | |
var te=new Array(em[0],em[1],em[2]); | |
var e0=new Array(nodeId,em[0],em[1]); | |
var e1=new Array(nodeId,em[1],em[2]); | |
var e2=new Array(nodeId,em[2],em[0]); | |
em[0]=e0[0];em[1]=e0[1];em[2]=e0[2]; | |
this.elem.push(e1); | |
this.elem.push(e2); | |
var jm=this.map[elemId]; | |
var tmp=new Array(jm[0],jm[1],jm[2]); | |
var j0=new Array(nn+1,jm[0],nn); | |
var j1=new Array(elemId,jm[1],nn+1); | |
var j2=new Array(nn,jm[2],elemId); | |
jm[0]=j0[0];jm[1]=j0[1];jm[2]=j0[2]; | |
this.map.push(j1); | |
this.map.push(j2); | |
if(tmp[0]!==-1){ | |
if(!this.isBoundary(te[0],te[1]))this.stack.push(elemId); | |
} | |
if(tmp[1]!==-1){ | |
var ix=this.edge(tmp[1],elemId,this.map); | |
this.map[tmp[1]][ix]=nn; | |
if(!this.isBoundary(te[1],te[2]))this.stack.push(nn); | |
} | |
if(tmp[2]!==-1){ | |
var ix=this.edge(tmp[2],elemId,this.map); | |
this.map[tmp[2]][ix]=nn+1; | |
if(!this.isBoundary(te[2],te[0]))this.stack.push(nn+1); | |
} | |
while(this.stack.length>0){ | |
var il=this.stack.pop(); | |
var ir=this.map[il][1]; | |
var ierl=this.edge(ir,il,this.map); | |
var iera=(ierl+1)%3; | |
var ierb=(iera+1)%3; | |
var iv1=this.elem[ir][ierl]; | |
var iv2=this.elem[ir][iera]; | |
var iv3=this.elem[ir][ierb]; | |
if(this.isSwap(iv1,iv2,iv3,nodeId)){ | |
var ja=this.map[ir][iera]; | |
var jb=this.map[ir][ierb]; | |
var jc=this.map[il][2]; | |
this.elem[il][2]=iv3; | |
this.map[il][1]=ja; | |
this.map[il][2]=ir; | |
var picElem=this.elem[ir]; | |
picElem[0]=nodeId;picElem[1]=iv3;picElem[2]=iv1; | |
picElem=this.map[ir]; | |
picElem[0]=il;picElem[1]=jb;picElem[2]=jc; | |
if(ja!==-1){ | |
var ix=this.edge(ja,ir,this.map); | |
this.map[ja][ix]=il; | |
if(!this.isBoundary(iv2,iv3))this.stack.push(il); | |
} | |
if(jb!==-1){ | |
if(!this.isBoundary(iv3,iv1))this.stack.push(ir); | |
} | |
if(jc!==-1){ | |
var ix=this.edge(jc,il,this.map); | |
this.map[jc][ix]=ir; | |
} | |
} | |
} | |
}; | |
var del=new Delaunay2D(minX,minY,width,height); | |
this.clear=function(){del.clear();}; | |
this.insert=function(pos){return del.insert(pos);}; | |
this.getTriangleById=function(){return del.getTriangleById();}; | |
this.getTriangleMapById=function(){return del.getTriangleMapById();}; | |
this.getTriangle=function(){return del.getTriangle();}; | |
this.addBoundary=function(arg,isClose){ | |
return del.addBoundary(arg,isClose); | |
}; | |
this.getContourObject=function(){ | |
var ret=termat.Contour(del.node,del.elem); | |
return ret; | |
}; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment