Delaunay三角分割法とは？
Delaunay三角分割法とは、任意に設定された節点群を対象に、対象領域を三角形に分割する方法の一つです。
全ての三角要素について、その外接円内に他の三角要素の節点を含まないという幾何学的特徴を有するため、有限要素法等の要素分割に利用されています。
三角要素群は、数値解析や地形図CG、コンター図生成に利用できるなど、非常に便利なので、昔、Javaで実装していたものを、JavaScriptに移植してみました。
実行サンプル、参考文献等は、はてなブログで紹介しています。
アルゴリズム
ローソン法と呼ばれる方法で実装しています。手順は以下のとおり。
1.節点を含む要素を探査する（図1～4）。
2.探査した要素を３分割する（図5）。
3.分割された各要素について、外接円内に他の要素が含まれる場合は、その要素の辺を付け替える（図6,7）
4.分割・辺付け替えを行った要素全てについて上記の処理を行う。
5.上記の処理が完了したら、分割処理完了。
ソースコードは以下のとおり。→こちらでも配布してます。
なお、2010年頃にActionScript版をWonderflに投稿しています。→こちら(もう動かないかも）
termat.delaunay.0.1.js
/* 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;
};
};