Incremental Delaunay Triangulation Demo

Developer
Chris Johnson
Size
8,204 Kb
Views
20,240
  1. Incremental Delaunay Triangulation Demo Previews
  2. Incremental Delaunay Triangulation Demo HTML Codes
  3. Incremental Delaunay Triangulation Demo CSS Codes
  4. Incremental Delaunay Triangulation Demo JS Codes

How do I make an incremental delaunay triangulation demo?

This is a visualization I made to show my math-averse friends why I think stuff like Delaunay triangulation is just freakin cool.. What is a incremental delaunay triangulation demo? How do you make a incremental delaunay triangulation demo? This script and codes were developed by Chris Johnson on 01 October 2022, Saturday.

Incremental Delaunay Triangulation Demo Previews
IQ Test

Incremental Delaunay Triangulation Demo - Script Codes HTML Codes

<!DOCTYPE html>
<html >
<head> <meta charset="UTF-8"> <title>Incremental Delaunay Triangulation Demo</title> <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/normalize/5.0.0/normalize.min.css"> <link rel="stylesheet" href="css/style.css">
</head>
<body>
<svg id="svg" viewBox="0 0 200 200" preserveAspectRatio="xMidYMid meet"> <defs> <linearGradient id="maskGradient" x1="0" y1="0" x2="1" y2="0" spreadMethod="pad"> <stop stop-color="#000000" stop-opacity="0" offset="0%"></stop> <stop stop-color="#71237c" stop-opacity="0.25" offset="93.5%"></stop> <stop stop-color="#c22dd5" stop-opacity="0.6" offset="94.5%"></stop> <stop stop-color="#d68adf" stop-opacity="0.85" offset="95%"></stop> <stop stop-color="#c22dd5" stop-opacity="0.6" offset="95.5%"></stop> <stop stop-color="#000000" stop-opacity="0" offset="96.5%"></stop> </linearGradient> </defs> <g id="scanline"> <rect id="revealMaskRect" x="-15%" y="-100%" width="15%" height="300%" fill="url(#maskGradient)"></rect> </g> <g id="triangles"></g> <g id="points"></g>
</svg> <script src='https://cdnjs.cloudflare.com/ajax/libs/stats.js/r16/Stats.min.js'></script>
<script src='https://cdnjs.cloudflare.com/ajax/libs/dat-gui/0.6.1/dat.gui.min.js'></script> <script src="js/index.js"></script>
</body>
</html>

Incremental Delaunay Triangulation Demo - Script Codes CSS Codes

html, body { width: 100%; height: 100%;
}
body { overflow: hidden; background: #121318; background-image: -webkit-linear-gradient(rgba(255, 255, 255, 0.05) 1px, transparent 1px), -webkit-linear-gradient(left, rgba(255, 255, 255, 0.05) 1px, transparent 1px), -webkit-radial-gradient(ellipse, #090a0c, #121318); background-image: linear-gradient(rgba(255, 255, 255, 0.05) 1px, transparent 1px), linear-gradient(90deg, rgba(255, 255, 255, 0.05) 1px, transparent 1px), radial-gradient(ellipse, #090a0c, #121318); background-size: 40px 40px, 40px 40px, 100% 100%; background-position: -1px -1px, -1px -1px, center center;
}
svg { width: 100%; height: 100%;
}
#scanline { opacity: 0; -webkit-transition: opacity 800ms; transition: opacity 800ms;
}
#scanline.show { opacity: 1;
}
#points circle { stroke: none; fill: #fff; opacity: 0;
}
#points circle.show { opacity: 1;
}
@-webkit-keyframes flashOpacity { 0% { opacity: 0; } 7% { opacity: 1; } 100% { opacity: 0; }
}
@keyframes flashOpacity { 0% { opacity: 0; } 7% { opacity: 1; } 100% { opacity: 0; }
}
@-webkit-keyframes flashStroke { 0% { stroke: rgba(254, 133, 0, 0.9); } 100% { stroke: rgba(251, 252, 252, 0.65); }
}
@keyframes flashStroke { 0% { stroke: rgba(254, 133, 0, 0.9); } 100% { stroke: rgba(251, 252, 252, 0.65); }
}
.triangleGroup { opacity: 0;
}
.triangleGroup .circumference, .triangleGroup .center { stroke: rgba(248, 250, 250, 0.04); stroke-width: 2; fill: transparent; -webkit-transition: stroke 500ms; transition: stroke 500ms;
}
.triangleGroup .triangle { stroke: rgba(251, 252, 252, 0.65); stroke-width: 2; stroke-linejoin: bevel; fill: transparent; -webkit-transition: stroke 500ms; transition: stroke 500ms;
}
.triangleGroup.flash { -webkit-animation: flashOpacity 1200ms cubic-bezier(0.215, 0.61, 0.355, 1) 1; animation: flashOpacity 1200ms cubic-bezier(0.215, 0.61, 0.355, 1) 1;
}
.triangleGroup.flash .circumference, .triangleGroup.flash .center { opacity: 0;
}
.triangleGroup.temporary .triangle { stroke-dasharray: 20 30;
}
.triangleGroup.candidate { opacity: 1; -webkit-transition: opacity 800ms; transition: opacity 800ms;
}
.triangleGroup.candidate.temporary { opacity: 0.5;
}
.triangleGroup.candidate .triangle { stroke: rgba(0, 170, 94, 0.7);
}
.triangleGroup.candidate .circumference { stroke: rgba(17, 102, 57, 0.45);
}
.triangleGroup.candidate .center { stroke: rgba(17, 102, 57, 0.25);
}
.triangleGroup.rejected { opacity: 0; -webkit-transition: opacity 1600ms cubic-bezier(0.215, 0.61, 0.355, 1); transition: opacity 1600ms cubic-bezier(0.215, 0.61, 0.355, 1);
}
.triangleGroup.rejected .triangle { stroke: rgba(230, 35, 37, 0.9); -webkit-transition: stroke 200ms; transition: stroke 200ms;
}
.triangleGroup.rejected .circumference { stroke: rgba(131, 35, 30, 0.65); -webkit-transition: stroke 200ms; transition: stroke 200ms;
}
.triangleGroup.rejected .center { stroke: rgba(131, 35, 30, 0.25); -webkit-transition: stroke 200ms; transition: stroke 200ms;
}
.triangleGroup.locked { opacity: 1;
}
.triangleGroup.locked .triangle { -webkit-animation: flashStroke 800ms cubic-bezier(0.215, 0.61, 0.355, 1) 1 forwards; animation: flashStroke 800ms cubic-bezier(0.215, 0.61, 0.355, 1) 1 forwards;
}

Incremental Delaunay Triangulation Demo - Script Codes JS Codes

var opts;
var svg;
//////////////////////////////
// Helper Functions
//////////////////////////////
var EPSILON = 1.0 / 1048576.0;
// Finds the circumcircle for the three specified points
function calcTriangleInfo(i, j, k) { var yDiffIJ = Math.abs(i.y - j.y), yDiffJK = Math.abs(j.y - k.y), xCenter, yCenter, s1, s2, xMidIJ, xMidJK, yMidIJ, yMidJK, xDiff, yDiff; // bail condition if(yDiffIJ < EPSILON && yDiffJK < EPSILON) throw new Error("Can't get circumcircle since all 3 points are y-aligned. Halt and catch fire."); // solve for circumcircle (center x/y, radius) s1 = -((j.x - i.x) / (j.y - i.y)); s2 = -((k.x - j.x) / (k.y - j.y)); xMidIJ = (i.x + j.x) / 2.0; xMidJK = (j.x + k.x) / 2.0; yMidIJ = (i.y + j.y) / 2.0; yMidJK = (j.y + k.y) / 2.0; xCenter = (yDiffIJ < EPSILON) ? xMidIJ : (yDiffJK < EPSILON) ? xMidJK : (s1 * xMidIJ - s2 * xMidJK + yMidJK - yMidIJ) / (s1 - s2); yCenter = (yDiffIJ > yDiffJK) ? s1 * (xCenter - xMidIJ) + yMidIJ : s2 * (xCenter - xMidJK) + yMidJK; xDiff = j.x - xCenter; yDiff = j.y - yCenter; return {i: i, j: j, k: k, id: 't-'+i.id+'-'+j.id+'-'+k.id, x: xCenter, y: yCenter, radiusSquared: xDiff * xDiff + yDiff * yDiff};
}
// Removes edges with matching endpoints (leaves no copies)
function removeCommonEdges(edges) { for(var j = edges.length; j--; ) for(var i = j; i--; ) if((edges[j].a === edges[i].a && edges[j].b === edges[i].b) || (edges[j].a === edges[i].b && edges[j].b === edges[i].a)) { edges.splice(j--, 1); edges.splice(i, 1); break; }
}
function generateRandomPoint(w, h) { var x,y; do { x = (Math.random() - 0.5) * 0.95; y = (Math.random() - 0.5) * 0.95; } while (x*x + y*y > 0.25); return {x: (x+0.5)*w, y: (y+0.5)*h};
}
function createTriangleDrawing(tri, w, h) { var group = document.createElementNS('http://www.w3.org/2000/svg','g'); group.id = tri.id; group.classList.add('triangleGroup'); if (tri.id.indexOf('st') !== -1) group.classList.add('temporary'); if (tri.final) group.classList.add('final'); // performance is really bad for the shapes with supertriangle verts, // so don't draw full thing if touches supertriangle vertex if (tri.i.supertriangle || tri.j.supertriangle || tri.k.supertriangle) { // shuffle points so math works out nicer var t; var swapVerts = function() { if (tri.i.id === 'st2') { t = tri.i; tri.i = tri.j; tri.j = t; swapVerts(); } else if (tri.i.id === 'st3') { t = tri.i; tri.i = tri.k; tri.k = t; swapVerts(); } if (tri.j.id === 'st1') { t = tri.j; tri.j = tri.i; tri.i = t; swapVerts(); } else if (tri.j.id === 'st3') { t = tri.j; tri.j = tri.k; tri.k = t; swapVerts(); } if (tri.k.id === 'st1') { t = tri.k; tri.k = tri.i; tri.i = t; swapVerts(); } else if (tri.k.id === 'st2') { t = tri.k; tri.k = tri.j; tri.j = t; swapVerts(); } } swapVerts(); // create lines var triangleLine; if (!tri.i.supertriangle) { // I -> J triangleLine = document.createElementNS('http://www.w3.org/2000/svg','line'); triangleLine.classList.add('triangle'); triangleLine.setAttribute('x1', tri.i.x); triangleLine.setAttribute('y1', tri.i.y); if (tri.j.supertriangle) { // draw partial triangleLine.setAttribute('x2', ((tri.j.x-tri.i.x)*(2*h-tri.i.y)/(tri.j.y-tri.i.y)) + tri.i.x); triangleLine.setAttribute('y2', 2*h); } else { // draw full triangleLine.setAttribute('x2', tri.j.x); triangleLine.setAttribute('y2', tri.j.y); } group.appendChild(triangleLine); } if (!tri.j.supertriangle) { // J -> K triangleLine = document.createElementNS('http://www.w3.org/2000/svg','line'); triangleLine.classList.add('triangle'); triangleLine.setAttribute('x1', tri.j.x); triangleLine.setAttribute('y1', tri.j.y); if (tri.k.supertriangle) { // draw partial triangleLine.setAttribute('x2', 2*w); triangleLine.setAttribute('y2', ((tri.k.y-tri.j.y)*(2*w-tri.j.y)/(tri.k.x-tri.j.x)) + tri.j.y); } else { // draw full triangleLine.setAttribute('x2', tri.k.x); triangleLine.setAttribute('y2', tri.k.y); } group.appendChild(triangleLine); } if (!tri.k.supertriangle) { // K -> I triangleLine = document.createElementNS('http://www.w3.org/2000/svg','line'); triangleLine.classList.add('triangle'); triangleLine.setAttribute('x1', tri.k.x); triangleLine.setAttribute('y1', tri.k.y); if (tri.i.supertriangle) { // draw partial triangleLine.setAttribute('x2', -1*w); triangleLine.setAttribute('y2', ((tri.i.y-tri.k.y)*(-1*w-tri.k.y)/(tri.i.x-tri.k.x)) + tri.k.y); } else { // draw full triangleLine.setAttribute('x2', tri.i.x); triangleLine.setAttribute('y2', tri.i.y); } group.appendChild(triangleLine); } } else { // normal triangle var circOuter = document.createElementNS('http://www.w3.org/2000/svg','circle'); circOuter.classList.add('circumference'); circOuter.setAttribute('cx', tri.x); circOuter.setAttribute('cy', tri.y); circOuter.setAttribute('r', Math.sqrt(tri.radiusSquared)); group.appendChild(circOuter); var circCenter = document.createElementNS('http://www.w3.org/2000/svg','circle'); circCenter.classList.add('center'); circCenter.setAttribute('cx', tri.x); circCenter.setAttribute('cy', tri.y); circCenter.setAttribute('r', 1); group.appendChild(circCenter); var polyTriangle = document.createElementNS('http://www.w3.org/2000/svg','polygon'); polyTriangle.classList.add('triangle'); polyTriangle.setAttribute('points', [tri.i.x, tri.i.y, tri.j.x, tri.j.y, tri.k.x, tri.k.y].join(',')); group.appendChild(polyTriangle); } return group;
}
//////////////////////////////
// Triangulation Functions
//////////////////////////////
function getDelaunayTriangulation(points, w, h) { var candidates, locked, edges, triangles, steps, add, remove, lock, i, p, t, currentPoint, xDiff, yDiff; candidates = []; // triangles/circumcircles for evaluation locked = []; // triangles/circumcircles that are "locked" triangles = {}; // map of all triangles used in triangulation process steps = []; // list of which triangles are added/removed/locked at each scan step // fake supertriangle vertices (will remove these verts at the end) t = calcTriangleInfo( {x: 0.5 * w - 10 * w - 10 * h, y: -0.5 * h, id: 'st1', supertriangle: true}, {x: 0.5 * w, y: 0.5 * h + 10 * w + 10 * h, id: 'st2', supertriangle: true}, {x: 0.5 * w + 10 * w + 10 * h, y: -0.5 * h, id: 'st3', supertriangle: true} ); candidates.push(t); triangles[t.id] = t; steps.push({add: [t.id], remove: [], lock: [], point: 'setup'}); // add each vertex incrementally for(p = points.length; p--; ) { currentPoint = points[p]; edges = []; add = []; remove = []; lock = []; // check each "candidate" triangle for(i = candidates.length; i--; ) { // vertex is beyond right side of circumcircle, so we can lock this tri xDiff = currentPoint.x - candidates[i].x; if(xDiff > 0.0 && xDiff * xDiff > candidates[i].radiusSquared) { if (!candidates[i].i.supertriangle && !candidates[i].j.supertriangle && !candidates[i].k.supertriangle) { t = candidates.splice(i, 1)[0]; locked.push(t); lock.push(t.id); } continue; } // vertex outside circumcircle, skip yDiff = currentPoint.y - candidates[i].y; if(xDiff*xDiff + yDiff*yDiff > candidates[i].radiusSquared) continue; // vertex inside circumcircle, break up triangle and add edges to edge list remove.push(candidates[i].id); edges.push( {a: candidates[i].i, b: candidates[i].j}, {a: candidates[i].j, b: candidates[i].k}, {a: candidates[i].k, b: candidates[i].i} ); candidates.splice(i, 1); } // create new candidate triangles from orphaned edges and current point removeCommonEdges(edges); for(i = edges.length; i--; ) { t = calcTriangleInfo(edges[i].a, edges[i].b, currentPoint); candidates.push(t); triangles[t.id] = t; add.push(t.id); } // store steps executed this iteration (demo purposes only) steps.push({add: add, remove: remove, lock: lock, point: currentPoint}); } // remove triangles touching supertriangle verts and lock remaining tris remove = []; lock = []; for (i = candidates.length; i--; ) { if (candidates[i].i.supertriangle || candidates[i].j.supertriangle || candidates[i].k.supertriangle) { remove.push(candidates[i].id); } else { candidates[i].final = true; lock.push(candidates[i].id); } } for (i = locked.length; i--; ) { locked[i].final = true; } steps.push({add: [], remove: remove, lock: lock, point: 'finalize'}); return { triangles: triangles, steps: steps };
}
//////////////////////////////
// Demo Functions
//////////////////////////////
var demoTriangles, processSteps, activeAnimation;
var svgWidth, svgHeight;
function runDemo() { // set up demo svgWidth = window.innerWidth; svgHeight = window.innerHeight; // between 8-40 points (based on window size) // don't try much more b/c this algorithm is inefficient and this demo stores each step in memory var i, r1, r2, n = Math.min(40, Math.max(8,Math.floor(svgWidth * svgHeight / 27000))); console.log('Running demo with '+n+' random points.'); var points = new Array(n); // reset SVG svg.main.setAttribute('viewBox', '0 0 '+svgWidth+' '+svgHeight); // set up points for (i = 0; i < n; i++) { points[i] = generateRandomPoint(svgWidth, svgHeight); points[i].id = i + 1; } // sort by x-position points.sort(function(a, b) { return b.x - a.x; }); // draw points for (i = 0; i < n; i++) { var circle = document.createElementNS('http://www.w3.org/2000/svg','circle'); circle.setAttribute('cx', points[i].x); circle.setAttribute('cy', points[i].y); circle.setAttribute('r', 3); r1 = Math.floor(Math.random() * 500) + 400; // random fade duration r2 = (points[i].x / svgWidth) * 1000 + 100; // fade delay based on x-position circle.style.transition = 'opacity '+r1+'ms '+r2+'ms'; circle.style.webkitTransition = 'opacity '+r1+'ms '+r2+'ms'; svg.points.appendChild(circle); points[i].svg = circle; } setTimeout(function() { for (var i = points.length; i--; ) points[i].svg.classList.add('show'); }, 10); var triangulation = getDelaunayTriangulation(points, svgWidth, svgHeight); demoTriangles = triangulation.triangles; processSteps = triangulation.steps; // add triangles to DOM for (i in demoTriangles) { if (demoTriangles.hasOwnProperty(i)) { demoTriangles[i].svg = createTriangleDrawing(demoTriangles[i], svgWidth, svgHeight); svg.triangles.appendChild(demoTriangles[i].svg); } } setTimeout(function() { for (i in demoTriangles) if (demoTriangles.hasOwnProperty(i)) if (demoTriangles[i].final) demoTriangles[i].svg.classList.add('flash'); setTimeout(playDemo, 1000); }, 1200);
}
function playDemo() { // reset for (i in demoTriangles) if (demoTriangles.hasOwnProperty(i)) demoTriangles[i].svg.classList.remove('locked', 'rejected', 'candidate', 'flash'); svg.scanline.classList.remove('show'); if (activeAnimation) { window.cancelAnimationFrame(activeAnimation); } // animate steps var nextStep = 0; var processNextStep = function() { // add/lock/remove tris processSteps[nextStep].add.forEach(function(triId) { demoTriangles[triId].svg.classList.add('candidate'); }); processSteps[nextStep].remove.forEach(function(triId) { demoTriangles[triId].svg.classList.remove('candidate'); demoTriangles[triId].svg.classList.add('rejected'); }); processSteps[nextStep].lock.forEach(function(triId) { demoTriangles[triId].svg.classList.remove('candidate'); demoTriangles[triId].svg.classList.add('locked'); }); // advance if (nextStep < processSteps.length - 1) nextStep += 1; else nextStep = -1; }; var lastScanlineTick; var scanlinePosition = 0; var tickScanline = function(time) { // update position var deltaTime; if (!lastScanlineTick) { scanlinePosition = 0.0075*svgWidth; } else { deltaTime = time - lastScanlineTick; scanlinePosition += 0.00002 * opts.speed * deltaTime * svgWidth; } svg.scanline.style.transform = 'translateX('+scanlinePosition+'px)'; lastScanlineTick = time; // check for ticking next step if (nextStep === -1 || processSteps[nextStep].point === 'finalize' && scanlinePosition > svgWidth) { processNextStep(); svg.scanline.classList.remove('show'); } else if (processSteps[nextStep].point === 'setup') { svg.scanline.classList.add('show'); processNextStep(); activeAnimation = window.requestAnimationFrame(tickScanline); } else { if (scanlinePosition >= processSteps[nextStep].point.x) { processNextStep(); } activeAnimation = window.requestAnimationFrame(tickScanline); } }; activeAnimation = window.requestAnimationFrame(tickScanline);
}
function resetDemo() { while (svg.triangles.hasChildNodes()) { svg.triangles.removeChild(svg.triangles.lastChild); } while (svg.points.hasChildNodes()) { svg.points.removeChild(svg.points.lastChild); } svg.scanline.classList.remove('show'); if (activeAnimation) { window.cancelAnimationFrame(activeAnimation); } // restart runDemo();
}
var Options = function() { this.speed = 3; this.playAgain = () => { playDemo(); }; this.randomizePoints = () => { resetDemo(); };
};
function init() { // stats var stats = new Stats(); stats.domElement.style.position = 'absolute'; stats.domElement.style.left = '0'; stats.domElement.style.top = '0'; document.body.appendChild(stats.domElement); requestAnimationFrame(function updateStats(){ stats.update(); requestAnimationFrame(updateStats); }); // dat gui opts = new Options(); gui = new dat.GUI(); gui.add(opts, 'randomizePoints'); gui.add(opts, 'speed', 0.5, 10); gui.add(opts, 'playAgain'); // DOM queries svg = { main: document.getElementById('svg'), triangles: document.getElementById('triangles'), scanline: document.getElementById('scanline'), points: document.getElementById('points'), } runDemo();
}
init();
Incremental Delaunay Triangulation Demo - Script Codes
Incremental Delaunay Triangulation Demo - Script Codes
Home Page Home
Developer Chris Johnson
Username jhnsnc
Uploaded October 01, 2022
Rating 4.5
Size 8,204 Kb
Views 20,240
Do you need developer help for Incremental Delaunay Triangulation Demo?

Find the perfect freelance services for your business! Fiverr's mission is to change how the world works together. Fiverr connects businesses with freelancers offering digital services in 500+ categories. Find Developer!

Chris Johnson (jhnsnc) Script Codes
Name
Tesselation Transition
Headlander Title Animation
Wobbly Star
Colorized Perlin Noise Generator
Text Effect - Optimist
Bluemix Logo Scratch Animation
Shader Template
Text Effect - Mystique
Vector Star Eye
Text Effect - Radius
Create amazing art & images with AI!

Jasper is the AI Content Generator that helps you and your team break through creative blocks to create amazing, original content 10X faster. Discover all the ways the Jasper AI Content Platform can help streamline your creative workflows. Start For Free!