Skip to content

Instantly share code, notes, and snippets.

@termat

termat/delaunay-diagram.markdown

Created February 28, 2019 13:14
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/e49c6452ad0241f2be594575f53a03bf to your computer and use it in GitHub Desktop.
Save termat/e49c6452ad0241f2be594575f53a03bf to your computer and use it in GitHub Desktop.
Download ZIP
Delaunay diagram
Raw
index.html
<html>
<head>
<title>Delaunay分割</title>
</head>
<body>
<table border="1"><tr><td>
<canvas id="canvas" width="480" height="480"></canvas>
</td></tr></table>
</body>
</html>
Raw
script.js
var 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=new Array();
this.node=new Array();
this.elem=new Array();
this.map=new Array();
this.stack=new Array();
this.boundary=new Array();
this.boundaryID=new Array();
this.node.push(new Point(-1.23,-0.5));
this.node.push(new Point(2.23,-0.5));
this.node.push(new Point(0.5,2.5));
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=new Array();
this.node=new Array();
this.elem=new Array();
this.map=new Array();
this.stack=new Array();
this.boundary=new Array();
this.boundaryID=new Array();
this.node.push(new Point(-1.23,-0.5));
this.node.push(new Point(2.23,-0.5));
this.node.push(new Point(0.5,2.5));
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=new Array();
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=new Array();
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=new Array();
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=new Array();
var tp=new Array();
for(var i=0;i<et.length;i++){
var m=this.map[i];
if(et[i]!=-1){
for(var j=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;
}
Delaunay2D.prototype.getTriangle=function(){
var et=new Array();
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=new Array();
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){
var xx=(x-this.minX)/this.width;
var yy=(y-this.minY)/this.height;
return new Point(xx,yy);
}
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);
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);
}
}
Delaunay.getMinMaxXY=function(node){
var minX=1e12;
var minY=1e12;
var maxX=-1e12;
var maxY=-1e12;
var n=node.length;
for(var i=0;i<n;i++){
var pos=node[i];
if(minX>pos[0])minX=pos[0];
if(maxX<pos[0])maxX=pos[0];
if(minY>pos[1])minY=pos[1];
if(maxY<pos[1])maxY=pos[1];
}
return new Array(minX,minY,maxX,maxY);
}
var Point=function(px,py){
this.x=px;
this.y=py;
}
Point.prototype.distance=function(p) {
var mx=(p.x-this.x);
var my=(p.y-this.y);
return Math.sqrt(mx*mx+my*my);
}
Point.prototype.toString=function(){
return "("+this.x+","+this.y+")";
}
var ctx;
var list=new Array();
var num=400;
var del;
$(document).ready(function() {
var canvas = document.getElementById('canvas');
ctx=canvas.getContext('2d');
ctx.clearRect(0, 0, 480, 480);
ctx.fillStyle = "rgb(255, 50, 50)";
ctx.lineWidth=1;
del = new Delaunay(-100,-100,680,680);
var timer = setInterval("update()", 50)
});
function update(){
del.clear();
ctx.clearRect(0, 0, 480, 480);
if(list.length<num)list.push(new Vert());
for(var i=0;i<list.length;i++){
var p=list.shift();
p.x +=p.vx;
p.y +=p.vy;
if(!(p.x<-100||p.x>580||p.y<-100||p.y>580))list.push(p);
}
for(var i=0;i<list.length;i++){
var x=list[i].x;
var y=list[i].y;
del.insert(new Point(x,y));
ctx.beginPath();
ctx.arc(x, y, 3, 0, 2 * Math.PI, true);
ctx.fill();
}
var al=del.getTriangle();
ctx.strokeStyle = "rgb(255, 50, 50)";
for(var i=0;i<al.length;i++){
var p1=al[i][0];
var p2=al[i][1];
var p3=al[i][2];
ctx.beginPath();
ctx.moveTo(p1.x,p1.y);
ctx.lineTo(p2.x,p2.y);
ctx.lineTo(p3.x,p3.y);
ctx.stroke();
}
}
function Vert(){
this.x=240;
this.y=240;
this.vx=Math.random()*10-5;
this.vy=Math.random()*10-5;
}
Raw
scripts
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment