var MARGIN = 200; var vertices; var hueVal; function setup() { createCanvas(windowWidth, windowHeight); frameRate(30); colorMode(HSB, 360, 100, 100); hueVal = random(50); vertices = []; for (var i = 0; i < 50; i++) { var v = new Vertex(createVector(random(-MARGIN, width + MARGIN), random(-MARGIN, height + MARGIN))); vertices.push(v); } } function resetHue() { hueVal = 180 + random(180); } function drawTriangles() { if (frameCount % 120 === 0) { resetHue(); } background(hueVal, 70, 70); delaunayTriangulation = new DelaunayTriangulation(); for (var i = 0; i < vertices.length; i++) { delaunayTriangulation.add(vertices[i]); } var triangles = delaunayTriangulation.getTriangles(); for (var ti = 0; ti < triangles.length; ti++) { var t = triangles[ti]; var sat = 0; var bri = 0; for(var vi = 0; vi < 3; vi++) { var v = t.vertices[vi]; sat += v.sat; bri += v.bri; } sat /= 3; bri /= 3; fill(hueVal, sat, bri); stroke(hueVal, sat, bri); t.render(); } } function draw() { drawTriangles(); for (var i = 0; i < vertices.length; i++) { vertices[i].update(); } } function DelaunayTriangulation() { this.triangles = []; this.vertices = []; this.superVertices = []; this.render = function() { for(var i = 0; i < this.triangles.length; i++) { this.triangles[i].render(); } } this.add = function(v) { for (var i = 0; i < this.vertices.length; i++) { if(v.loc.x == this.vertices[i].loc.x && v.loc.y == this.vertices[i].loc.y) { return; } } this.vertices.push(v); var nextTriangles = []; var newTriangles = []; for (var ti = 0; ti < this.triangles.length; ti++) { var tri = this.triangles[ti]; if(tri.circumCircle.isInCircle(v.loc)) { newTriangles = newTriangles.concat(tri.divide(v)); } else { nextTriangles.push(tri); } } for (var ti = 0; ti < newTriangles.length; ti++) { var tri = newTriangles[ti]; var isIllegal = false; for (var vi = 0; vi < this.vertices.length; vi++) { if (this.isIllegalTriangle(tri, this.vertices[vi])) { isIllegal = true; break; } } if (!isIllegal) { nextTriangles.push(tri); } } this.triangles = nextTriangles; } this.getTriangles = function() { var ts = []; for (var ti = 0; ti < this.triangles.length; ti++) { var t = this.triangles[ti]; var hasSuperVertex = false; for (var vi = 0; vi < 3; vi++) { if (t.isContain(this.superVertices[vi])) { hasSuperVertex = true; } } if (!hasSuperVertex) { ts.push(t); } } return ts; } this.getTrianglesWithSuperTriangle = function() { return this.triangles; } this.isIllegalTriangle = function(t, v) { if(t.isContain(v)) { return false; } return t.circumCircle.isInCircle(v.loc); } var center = createVector(width / 2, height / 2); var radius = sqrt(sq(width) + sq(height)) / 2; var v1 = new Vertex(createVector(center.x - sqrt(3) * radius, center.y - radius)); var v2 = new Vertex(createVector(center.x + sqrt(3) * radius, center.y - radius)); var v3 = new Vertex(createVector(center.x, center.y + 2 * radius)); var t = new Triangle([v1, v2, v3]); this.superVertices.push(v1); this.superVertices.push(v2); this.superVertices.push(v3); this.vertices.push(v1); this.vertices.push(v2); this.vertices.push(v3); this.triangles.push(t); } function Triangle(vertices) { this.vertices = vertices; var v1 = this.vertices[0].loc; var v2 = this.vertices[1].loc; var v3 = this.vertices[2].loc; var c = 2 * ((v2.x - v1.x) * (v3.y - v1.y) - (v2.y - v1.y) * (v3.x - v1.x)); var x = ((v3.y - v1.y) * (sq(v2.x) - sq(v1.x) + sq(v2.y) - sq(v1.y)) + (v1.y - v2.y) * (sq(v3.x) - sq(v1.x) + sq(v3.y) - sq(v1.y))) / c; var y = ((v1.x - v3.x) * (sq(v2.x) - sq(v1.x) + sq(v2.y) - sq(v1.y)) + (v2.x - v1.x) * (sq(v3.x) - sq(v1.x) + sq(v3.y) - sq(v1.y))) / c; var center = createVector(x, y); var radius = v1.dist(center); this.circumCircle = new Circle(center, radius); this.render = function() { beginShape(); for (var i = 0; i < 3; i++) { var v = this.vertices[i].loc; vertex(v.x, v.y); } endShape(CLOSE); } this.divide = function(v) { var tris = []; for (var i = 0; i < 3; i++) { var j = i == 2? 0: i + 1; tris.push(new Triangle([this.vertices[i], this.vertices[j], v])); } return tris; } this.isContain = function(v) { for (var i = 0; i < 3; i++) { if (this.vertices[i] === v) { return true; } } return false; } } function Circle(center, radius) { this.center = center; this.radius = radius; this.isInCircle = function(v) { return this.center.dist(v) < this.radius; } } function Vertex(loc) { this.loc = loc; var velAng = random(TWO_PI); var velSize = 2.0; this.vel = createVector(velSize * cos(velAng), velSize * sin(velAng)); this.sat = random(50, 100); this.bri = random(30, 100); this.update = function() { this.loc.add(this.vel); if (this.loc.x < -MARGIN || this.loc.x > width + MARGIN) { this.vel.x *= -1; this.loc.x += this.vel.x; } if (this.loc.y < -MARGIN || this.loc.y > height + MARGIN) { this.vel.y *= -1; this.loc.y += this.vel.y; } } }

Delaunay Triangulation