Delaunay Triangulation
Page by Murray Bourne, IntMath.com. Last updated: 07 September 2019.
We start with a short introduction to explain what's going on in the math-based artwork below.
Triangulation
Triangulation is a widely-used concept in the fields of computer games and computer graphics generally. Let's look at an example of triangulation.
We have a plane represented by this rectangle, some points on the plane, and we draw triangles using those points. We have "triangulated the plane".
Delaunay Triangulation
A Delaunay Triangulation is a specific type of triangulation such that no triangle's points are inside the circumcircle of any other triangle in the triangulation.Let's see what that means in an example.
We start with a triangle, and calculate its circumcenter, indicated by a pink dot. The circumcenter is the center of the unique circle that passes through the 3 points of the triangle.
Finding the circumcenter
The circumcenter is found by determining the intersection of the perpendicular bisectors of two sides of the triangle. That is:
- Find the midpoints of two of the sides
- Find the equations of the perpendicular lines passing through those midpoints
- Find the intersection of those two lines
Of course, I used code to find the circumcenters in these examples.
Next, we construct the circumcircle and observe it passes through the three points of the triangle.
Next, we construct another triangle off one of the sides of our existing triangle. We calculate its circumcenter (the green dot) and construct the circumcircle.
Note our original pink dot is outside our new circumcircle, and the new green dot is outside the original circumcircle.
We have produced our first (simple) Delaunay Triangulation.
Now to the art...
The following image (coding by Antoinette Janus) is based on Delaunay Triangulation of a plane.
You can change:
- The number of points to be joined by triangles; and
- The color scheme
To save an image as a background for your computer or phone, right click and choose "Save Image".
Enjoy!
(See below for the javascript code involved in producing this canvas.)
Color Schemes
The code
// First, the author gives credits to his sources:
// Thanks to the following:
// https://github.com/ironwallaby/delaunay.git
// http://gradients.io/
// https://uigradients.com
// Set up array variables
let color_group = [], fill_color = [], number_of_triangles = 100;
// Variables for image and resizing
var delWidth = document.getElementById( 'del' ).clientWidth;
var viewPortWidth = window.innerWidth;
var viewPortHeight = window.innerHeight;
var delHeight = Math.min(viewPortHeight-20, Math.min(600, Math.max(300, viewPortHeight-150)));
var viewPortWidthRem = viewPortWidth;
var viewPortHeightRem = viewPortHeight;
// Color gradients used for the triangles
const gradients = [
{
name: 'mimosa',
colors: [
['#D74177', '#FFE98A'],
['#3A1C71', '#D76D77'],
['#e96443', '#904e95'],
['#ff7e5f', '#feb47b']
]},
{
name: 'intmath',
colors: [
['#00A8C5', '#043850'],
['#0cebeb', '#165a71'],
['#007991', '#78ffd6'],
['#1CD8D2', '#93EDC7']
]},
{
name: 'great-good',
colors: [
['#D4145A', '#FBB03B'],
['#C04848', '#480048'],
['#cc2b5e','#753a88'],
['#C33764', '#1D2671']
]},
{
name: 'metal',
colors: [
['#E8CBC0', '#636FA4'],
['#DBE6F6', '#C5796D'],
['#F3904F', '#3B4371'],
['#DAE2F8', '#D6A4A4']
]},
{
name: 'warm-military',
colors: [
['#FFA17F', '#00223E'],
['#556270', '#FF6B6B'],
['#F0C27B', '#1F1C2C'],
['#ff7e5f', '#00223E']
]}
];
// Get a random number between 2 given numbers
function randNum(min, max){
return Math.floor(Math.random() * (max-min + 1)) + min;
}
// Set the dimensions of the image to suit
const resizeCanvas = function(){
const canvas = document.querySelector('canvas');
delWidth = document.getElementById( 'del' ).clientWidth;
//delHeight = document.getElementById( 'del' ).clientHeight;
canvas.width = delWidth;
canvas.height = delHeight;
}
// Construct the random points to be joined
function pointsArray(){
let points = [];
delWidth = document.getElementById( 'del' ).clientWidth;
delHeight = document.getElementById( 'del' ).clientHeight;
while(points.length < number_of_triangles){
points.push([randNum(-50, delWidth), randNum(-50, delHeight)])
}
points.push([0,0], [delWidth, 0], [0, delHeight], [delWidth, delHeight])
return points
}
// Choose the color scheme
const chooseColor = function(value){
var color_choice = gradients.find(function(obj){
return obj.name === value
})
var colors;
if (color_choice) {
colors = color_choice.colors
} else {
colors = gradients[randNum(0, gradients.length-1)].colors;
}
return colors;
}
// Joins the points with triangles
// Delaunay is defined in an external js file
const convertToTriangles = function(value){
color_group = chooseColor(value);
const ctx = document.querySelector( 'canvas' ).getContext('2d');
ctx.fillStyle = color_group[randNum(0, color_group.length-1)][randNum(0,1)];
ctx.fillRect(0, 0, delWidth, delHeight);
var vertices = pointsArray();
var triangles = Delaunay.triangulate(vertices);
for(i = triangles.length; i; ) {
var x_arr = [], y_arr = [];
ctx.beginPath();
--i;
x_arr.push(vertices[triangles[i]][0]);
y_arr.push(vertices[triangles[i]][1]);
ctx.moveTo(vertices[triangles[i]][0], vertices[triangles[i]][1]);
--i;
x_arr.push(vertices[triangles[i]][0]);
y_arr.push(vertices[triangles[i]][1]);
ctx.lineTo(vertices[triangles[i]][0], vertices[triangles[i]][1]);
--i;
x_arr.push(vertices[triangles[i]][0]);
y_arr.push(vertices[triangles[i]][1]);
ctx.lineTo(vertices[triangles[i]][0], vertices[triangles[i]][1]);
ctx.closePath();
var start_x_point = x_arr[randNum(0, x_arr.length - 1)];
x_arr.splice( x_arr.indexOf(start_x_point), 1);
var end_x_point = x_arr[randNum(0, x_arr.length - 1)];
var start_y_point = y_arr[randNum(0, y_arr.length - 1)];
y_arr.splice(y_arr.indexOf( start_y_point ), 1);
var end_y_point = y_arr[randNum(0, y_arr.length - 1)];
var start_point = [start_x_point, start_y_point];
var end_point = [end_x_point, end_y_point];
var points = [start_point, end_point];
fill_color = color_group[randNum(0, color_group.length-1)];
ctx.fillStyle = gradient(ctx, points, fill_color);
ctx.fill();
ctx.strokeStyle = gradient(ctx, points, fill_color);
ctx.stroke();
}
}
// Adds styles to the surrounding siv
function changeLinkColors(index, color1, color2){
del.style.setProperty(('--start-color-'+index), color1);
del.style.setProperty(('--end-color-'+index), color2);
}
// Sets the gardient colors
var gradient = function (ctx, points, color){
let grd = ctx.createLinearGradient(points[0][0],points[0][1],points[1][0],points[1][1]);
grd.addColorStop(0, color[0]);
grd.addColorStop(1, color[1]);
return grd;
}
// Draws the backgrounds
function drawBackground(value){
convertToTriangles(value);
const links = del.querySelectorAll('a');
for (var i = 0; links.length > i; i++){
changeLinkColors(i+1, fill_color[0], fill_color[1]); links[i].addEventListener('mouseenter', function(e){
var index = 0;
while( e.target !== links[index] )
index++;
let hover_color = color_group[randNum(0, color_group.length-1)];
while(hover_color[0] === fill_color[0]){
hover_color = color_group[randNum(0, color_group.length-1)];
}
changeLinkColors(index+1, hover_color[0], hover_color[1]);
});
links[i].addEventListener('mouseleave', function(e){
var index = 0;
while( e.target !== links[index] )
index++;
changeLinkColors(index+1, fill_color[0], fill_color[1])
})
}
}
// This fires off the whole thing
window.onload = function(){
resizeCanvas();
drawBackground( document.querySelector( '#color-schemes :checked' ));
var inputs = document.querySelectorAll('input');
for(var i = 0; inputs.length > i; i++){
inputs[i].addEventListener('change', function(e){
number_of_triangles = document.getElementById( 'triangle_count' ).value;
drawBackground( document.querySelector( '#color-schemes :checked' ).id );
});
}
}
// Redraw everything when resized (e.g. rotate phone)
window.addEventListener('resize', resizeThrottler, false);
var resizeTimeout;
function resizeThrottler() {
if (!resizeTimeout) {
resizeTimeout = setTimeout(function() {
resizeTimeout = null;
if(typeof(actualResizeHandler) == 'function') {
actualResizeHandler();
}
}, 200);
}
}
function actualResizeHandler() {
viewPortWidth = window.innerWidth;
viewPortHeight = window.innerHeight;
if( viewPortWidth != viewPortWidthRem || Math.abs(viewPortHeightRem - viewPortHeight) > 50) {
resizeCanvas();
drawBackground( document.querySelector('#color-schemes :checked') );
viewPortWidthRem = viewPortWidth;
viewPortHeightRem = viewPortHeight;
}
}
"Real world" example
St. George Bank, an Australian company, makes use of Delaunay triangulation on the St. George homepage, as follows.
Credits
The script is by Antoinette Janus, source: CodePen.
From the original script:
This is a generator using Delaunay's Triangulation concept in the form of IronWallaby's library
The gradients were taken from UIGradients and Gradients.io