Skip to content

Instantly share code, notes, and snippets.

@termat
Last active November 8, 2015 18:16
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save termat/3cf4fcc51926e0349804 to your computer and use it in GitHub Desktop.
Save termat/3cf4fcc51926e0349804 to your computer and use it in GitHub Desktop.
JavaScriptでDelaunay三角形分割クラスを実装する。 ref: http://qiita.com/t-mat/items/1c571926ccaa7ef1577b
/* 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