Skip to content

Instantly share code, notes, and snippets.

@termat

termat/index.html

Created February 28, 2019 13:10
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/2acb791a38e0c4f6a94cb5a7cc703bcf to your computer and use it in GitHub Desktop.
Save termat/2acb791a38e0c4f6a94cb5a7cc703bcf to your computer and use it in GitHub Desktop.
Download ZIP
Voronoi
Raw
index.html
<html xmlns="http://www.w3.org/1999/xhtml" lang="ja" xml:lang="ja">
<head>
<title>Voronoi.js</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 ctx;
var list=new Array();
var num=400;
var vor;
var timer;
$(document).ready(function() {
var canvas = document.getElementById('canvas');
ctx=canvas.getContext('2d');
ctx.clearRect(0, 0, 480, 480);
ctx.fillStyle = "rgb(0, 0, 0)";
ctx.lineWidth=1;
vor = new Voronoi();
var timer=setInterval(update,50);
setTimeout(function(){
clearInterval(timer);
}, 1000000);
});
var update=function(){
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<0||p.x>480||p.y<0||p.y>480))list.push(p);
}
for(var i=0;i<list.length;i++){
var x=list[i].x;
var y=list[i].y;
vor.addNode(x,y);
ctx.beginPath();
ctx.arc(x, y, 3, 0, 2 * Math.PI, true);
ctx.fill();
}
var al=vor.exec();
ctx.strokeStyle = "rgb(255, 0, 0)";
for(var i=0;i<al.length;i++){
var p1=al[i].P1;
var p2=al[i].P2;
ctx.beginPath();
ctx.moveTo(p1.x,p1.y);
ctx.lineTo(p2.x,p2.y);
ctx.stroke();
}
}
function Vert(){
this.x=240;
this.y=240;
this.vx=Math.random()*10-5;
this.vy=Math.random()*10-5;
}
var Voronoi=function(){
this.points=new Array();
this.events=new Array();
this.out=new Array();
this.root=null;
this.tmpX=0;
}
Voronoi.prototype.exec=function(){
while(this.out.length>0)this.out.pop();
if(this.points.length==0)return this.out;
this.root=null;
this.setBoundingBox();
this.points.sort(function(a,b){return (a.x==b.x) ? a.y-b.y : a.x-b.x;});
while(this.points.length>0){
if(this.events.length>0 && this.events[0].x <= this.points[0].x){
this.process_event();
}else{
var p=this.points.shift();
this.front_insert(p);
}
}
while(this.events.length>0) this.process_event();
this.finish_edges();
return this.output();
}
Voronoi.prototype.finish_edges=function(){
var l= this.X1 + (this.X1-this.X0) + (this.Y1-this.Y0);
for(var i=this.root; i.next!=null; i=i.next){
if(i.s1!=null) i.s1.finish(this.intersection(i.p, i.next.p, l*2));
}
}
Voronoi.prototype.output=function(){
var ret=new Array();
for(var i=0;i<this.out.length;i++){
var p1=this.out[i].start;
var p2=this.out[i].end;
ret.push(new Edge(p1,p2));
}
return ret;
}
Voronoi.prototype.addNode=function(x,y){
var p=new Point(x,y);
this.points.push(p);
}
Voronoi.prototype.setBoundingBox=function(){
this.X0=1e16;
this.X1=-1e16;
this.Y0=1e16;
this.Y1=-1e16;
for(var i=0;i<this.points.length;i++){
var p=this.points[i];
this.X0=Math.min(this.X0,p.x);
this.X1=Math.max(this.X1,p.x);
this.Y0=Math.min(this.Y0,p.y);
this.Y1=Math.max(this.Y1,p.y);
}
var dx=(this.X1-this.X0+1.0)/5.0;
var dy=(this.Y1-this.Y0+1.0)/5.0;
this.X0 -=dx;
this.X1 +=dx;
this.Y0 -=dy;
this.Y1 +=dy;
}
Voronoi.prototype.front_insert=function(p){
if(this.root==null){
this.root = new Arc(p,null,null);
return;
}
for(var i=this.root;i!=null;i=i.next){
var z=new Point(0.0,0.0);
var zz=new Point(0.0,0.0);
if(this.intersect(p,i,z)){
if(i.next!=null && !this.intersect(p,i.next, zz)) {
i.next.prev=new Arc(i.p,i,i.next);
i.next=i.next.prev;
}else{
i.next=new Arc(i.p,i,null);
}
i.next.s1=i.s1;
i.next.prev=new Arc(p,i,i.next);
i.next=i.next.prev;
i=i.next;
i.prev.s1=i.s0=new Seg(z,this.out);
i.next.s0=i.s1=new Seg(z,this.out);
this.check_circle_event(i, p.x);
this.check_circle_event(i.prev, p.x);
this.check_circle_event(i.next, p.x);
return;
}
}
var i;
for(i=this.root;i.next!=null;i=i.next){};
i.next=new Arc(p,i,null);
i.s1=i.next.s0=new Seg(
new Point(this.X0,(i.next.p.y+i.p.y)/2.0),this.out);
}
Voronoi.prototype.process_event=function(){
var e=this.events.shift();
if(e.valid){
var s=new Seg(e.p,this.out);
var a=e.arc;
if(a.prev!=null) {
a.prev.next=a.next;
a.prev.s1=s;
}
if(a.next!=null){
a.next.prev = a.prev;
a.next.s0 = s;
}
if(a.s0!=null) a.s0.finish(e.p);
if(a.s1!=null) a.s1.finish(e.p);
if(a.prev!=null) this.check_circle_event(a.prev, e.x);
if(a.next!=null) this.check_circle_event(a.next, e.x);
}
}
Voronoi.prototype.intersect=function(p,i,r){
if(i.p.x==p.x)return false;
var a=0.0;
var b=0.0;
if(i.prev!=null)a=this.intersection(i.prev.p, i.p, p.x).y;
if(i.next!=null)b=this.intersection(i.p,i.next.p, p.x).y;
if((i.prev==null||a<=p.y)&&(i.next==null || p.y <= b)){
r.y = p.y;
r.x = (i.p.x*i.p.x+(i.p.y-r.y)*(i.p.y-r.y)-p.x*p.x)/(2.0*i.p.x-2.0*p.x);
return true;
}
return false;
}
Voronoi.prototype.intersection=function(p0,p1,l){
var p=p0;
var r=new Point(0,0);
if(p0.x==p1.x){
r.y=(p0.y+p1.y)/2.0;
} else if (p1.x == l){
r.y=p1.y;
} else if(p0.x ==l){
r.y = p0.y;
p = p1;
} else {
var ll=l*l;
var z0=2.0*(p0.x - l);
var z1=2.0*(p1.x - l);
var a=1.0/z0 - 1.0/z1;
var b=-2.0*(p0.y/z0 - p1.y/z1);
var c=(p0.y*p0.y + p0.x*p0.x - ll)/z0-(p1.y*p1.y+p1.x*p1.x-ll)/z1;
r.y =(-b-Math.sqrt(b*b-4.0*a*c))/(2.0*a);
}
r.x=(p.x*p.x+(p.y-r.y)*(p.y-r.y)-ll)/(2.0*p.x-2.0*l);
return r;
}
Voronoi.prototype.check_circle_event=function(i,x0){
if(i.evt!=null&&i.evt.x != x0)i.evt.valid=false;
i.evt=null;
if(i.prev==null || i.next==null)return;
var o=new Point(0,0);
if(this.circle(i.prev.p,i.p,i.next.p, o) && this.tmpX > x0){
i.evt=new Evt(this.tmpX, o,i);
this.events.push(i.evt);
this.events.sort(function(a,b){return a.x-b.x;});
}
}
Voronoi.prototype.circle=function(a,b,c,o){
if((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y) > 0.0)return false;
var A = b.x - a.x;
var B = b.y - a.y;
var C = c.x - a.x;
var D = c.y - a.y;
var E = A*(a.x+b.x) + B*(a.y+b.y);
var F = C*(a.x+c.x) + D*(a.y+c.y);
var G = 2*(A*(c.y-b.y)-B*(c.x-b.x));
if(Math.abs(G)<0.000001)return false;
o.x = (D*E-B*F)/G;
o.y = (A*F-C*E)/G;
this.tmpX = o.x + Math.sqrt( Math.pow(a.x - o.x, 2.0) + Math.pow(a.y - o.y, 2.0) );
return true;
}
function Point(x,y){
this.x=x;
this.y=y;
}
function Arc(p,prev,next){
this.p=p;
this.next=next;
this.prev=prev;
this.s0=null;
this.s1=null;
this.evt=null;
}
function Seg(p,array){
this.start=p;
this.end=new Point(0.0,0.0);
this.done=false;
array.push(this);
}
Seg.prototype.finish=function(p){
if(this.done)return;
this.end=p;
this.done=true;
}
function Evt(x,p,a){
this.x=x;
this.p=p;
this.arc=a;
this.valid=true;
}
function Edge(a,b){
this.P1=a;
this.P2=b;
}
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