3D Voronoi & Delaunay in the Browser

const W = 400, H = 400, N = 32; const canvas = document.getElementById('voronoi'); const ctx = canvas.getContext('2d'); const imgData = ctx.createImageData(W, H); // Generate N random seeds with random colours const seeds = Array.from({ length: N }, () => ({ x: Math.random() * W, y: Math.random() * H, r: Math.random() * 200 | 0, g: Math.random() * 200 | 0, b: Math.random() * 200 | 0, })); for (let py = 0; py < H; py++) { for (let px = 0; px < W; px++) { let minDist = Infinity, closest = 0; for (let i = 0; i < seeds.length; i++) { const dx = px - seeds[i].x, dy = py - seeds[i].y; const d2 = dx * dx + dy * dy; if (d2 < minDist) { minDist = d2; closest = i; } } const { r, g, b } = seeds[closest]; const idx = (py * W + px) * 4; imgData.data[idx] = r; imgData.data[idx+1] = g; imgData.data[idx+2] = b; imgData.data[idx+3] = 255; } } ctx.putImageData(imgData, 0, 0);

function circumcircle(a, b, c) { const ax = a.x - c.x, ay = a.y - c.y; const bx = b.x - c.x, by = b.y - c.y; const D = 2 * (ax * by - ay * bx); if (Math.abs(D) < 1e-10) return null; // degenerate const ux = (by * (ax*ax + ay*ay) - ay * (bx*bx + by*by)) / D; const uy = (ax * (bx*bx + by*by) - bx * (ax*ax + ay*ay)) / D; const cx2 = ux + c.x, cy2 = uy + c.y; const r2 = ux*ux + uy*uy; return { x: cx2, y: cy2, r2 }; } function bowyer(points) { // Super triangle containing all points const M = 1e6; const st = [ { x: 0, y: -M*3 }, { x: -M*3, y: M*3 }, { x: M*3, y: M*3 }, ]; let triangles = [{ verts: [...st], cc: circumcircle(...st) }]; for (const p of points) { const bad = []; const good = []; for (const tri of triangles) { const { x, y, r2 } = tri.cc; const dx = p.x - x, dy = p.y - y; if (dx*dx + dy*dy < r2) bad.push(tri); else good.push(tri); } // Boundary polygon of bad triangles (edges not shared) const edgeCount = new Map(); for (const tri of bad) { const [a, b, c] = tri.verts; for (const edge of [[a,b],[b,c],[c,a]]) { const key = [edge[0],edge[1]].sort((x,y)=>x.x-y.x||x.y-y.y) .map(v=>`${v.x},${v.y}`).join('|'); edgeCount.set(key, (edgeCount.get(key)||0)+1); } } const boundary = [...edgeCount.entries()] .filter(([,n])=>n===1).map(([k])=>{ const [a,b] = k.split('|').map(s=>{const[x,y]=s.split(',');return{x:+x,y:+y};}); return [a,b]; }); triangles = good; for (const [a,b] of boundary) { const verts = [a, b, p]; const cc = circumcircle(a, b, p); if (cc) triangles.push({ verts, cc }); } } // Remove triangles sharing super-triangle vertices return triangles.filter(t => t.verts.every(v => st.every(s => !(Math.abs(v.x-s.x)<1 && Math.abs(v.y-s.y)<1)) )); }

function voronoiCells(seeds, triangles) { const cells = new Map(seeds.map(s => [s, []])); for (const tri of triangles) { const { x, y } = tri.cc; // circumcentre = Voronoi vertex for (const seed of tri.verts) { if (cells.has(seed)) cells.get(seed).push({ x, y }); } } // Sort each cell's vertices in a consistent winding order for (const [seed, pts] of cells) { pts.sort((a, b) => Math.atan2(a.y - seed.y, a.x - seed.x) - Math.atan2(b.y - seed.y, b.x - seed.x)); } return cells; // Map: seed → ordered polygon vertices }

import * as THREE from 'https://cdn.jsdelivr.net/npm/three@0.160/build/three.module.js'; const scene = new THREE.Scene(); const camera = new THREE.PerspectiveCamera(60, innerWidth/innerHeight, 0.1, 2000); camera.position.set(0, 200, 400); function buildCell(polygon, depth) { const shape = new THREE.Shape(); shape.moveTo(polygon[0].x, polygon[0].y); for (let i = 1; i < polygon.length; i++) shape.lineTo(polygon[i].x, polygon[i].y); shape.closePath(); const geo = new THREE.ExtrudeGeometry(shape, { depth, bevelEnabled: false, }); const hue = Math.random(); const mat = new THREE.MeshStandardMaterial({ color: new THREE.Color().setHSL(hue, .7, .45), roughness: .4, metalness: .1, }); return new THREE.Mesh(geo, mat); } const cells = voronoiCells(seeds, triangles); for (const [, polygon] of cells) { if (polygon.length < 3) continue; const mesh = buildCell(polygon, 10 + Math.random() * 60); // Centre the cell in XZ plane mesh.rotation.x = -Math.PI / 2; scene.add(mesh); }

function centroid(polygon) { let ax = 0, ay = 0, area = 0; const n = polygon.length; for (let i = 0, j = n - 1; i < n; j = i++) { const cross = polygon[j].x * polygon[i].y - polygon[i].x * polygon[j].y; ax += (polygon[j].x + polygon[i].x) * cross; ay += (polygon[j].y + polygon[i].y) * cross; area += cross; } area /= 2; return { x: ax / (6 * area), y: ay / (6 * area) }; } function lloyd(seeds, bounds, iterations = 5) { for (let iter = 0; iter < iterations; iter++) { const triangles = bowyer(seeds); const cells = voronoiCells(seeds, triangles); seeds = seeds.map(s => { const cell = cells.get(s); if (!cell || cell.length < 3) return s; const c = centroid(cell); // Clamp to bounding box return { x: Math.max(bounds.x0, Math.min(bounds.x1, c.x)), y: Math.max(bounds.y0, Math.min(bounds.y1, c.y)), }; }); } return seeds; }

// Animate: slowly rotate the map const clock = new THREE.Clock(); function animate() { requestAnimationFrame(animate); scene.rotation.y = clock.getElapsedTime() * 0.1; renderer.render(scene, camera); } animate(); // Colour cells by their extrusion depth (terrain-toned) function elevationColor(depth, maxDepth) { const t = depth / maxDepth; if (t < 0.15) return new THREE.Color(0x1a6aa0); // deep water if (t < 0.25) return new THREE.Color(0x3a9ad9); // shallow water if (t < 0.40) return new THREE.Color(0xd4b483); // beach if (t < 0.70) return new THREE.Color(0x4a7c40); // grass if (t < 0.85) return new THREE.Color(0x7a6a55); // rock return new THREE.Color(0xfafafa); // snow }