Skip to content

Instantly share code, notes, and snippets.

@carrotflakes

carrotflakes/voronoi.html

Created April 9, 2024 17:27
Show Gist options
  • Save carrotflakes/b27873224a9dfed5608339c6f5164e8f to your computer and use it in GitHub Desktop.
Save carrotflakes/b27873224a9dfed5608339c6f5164e8f to your computer and use it in GitHub Desktop.
Download ZIP
voronoi
Raw
voronoi.html
<!DOCTYPE html>
<html>
<head></head>
<body style="background: black;">
<canvas id="canvas" width="500" height="500"></canvas>
<script>
const el = document.getElementById("canvas");
// ctx.fillRect(0, 0, 500, 500);
const vertexes = [
{x: 100, y: 100, c: [0, 0, 1]},
{x: 110, y: 300, c: [0, 1, 0]},
{x: 400, y: 480, c: [0, 1, 1]},
{x: 200, y: 310, c: [1, 0, 0]},
{x: 410, y: 200, c: [1, 0, 1]},
];
let showLine = true;
draw();
let drag = null;
let dragged = false;
el.onmousedown = (e) => {
const bbox = el.getBoundingClientRect();
const x = e.clientX - bbox.x;
const y = e.clientY - bbox.y;
let vertex = vertexes.find((v) => Math.sqrt((v.x - x) ** 2 + (v.y - y) ** 2) < 10);
if (!vertex) {
vertex = {x, y, c: [Math.random(), Math.random(), Math.random()]};
vertexes.push(vertex);
dragged = true;
} else {
if (e.ctrlKey) {
vertex = {x, y, c: vertex.c};
vertexes.push(vertex);
dragged = true;
} else {
dragged = false;
}
}
drag = vertex;
draw();
}
window.onmousemove = (e) => {
if (drag) {
const bbox = el.getBoundingClientRect();
const x = e.clientX - bbox.x;
const y = e.clientY - bbox.y;
drag.x = x;
drag.y = y;
draw();
dragged = true;
}
}
window.onmouseup = (e) => {
if (drag && !dragged) {
vertexes.splice(vertexes.indexOf(drag), 1);
draw();
}
drag = null;
}
window.onkeydown = (e) => {
if (e.key === "l") {
showLine = !showLine;
draw();
}
}
function draw() {
for (const v of vertexes)
v.cs = []
const ctx = el.getContext("2d");
ctx.clearRect(0, 0, 500, 500);
const circles = [];
for (let i = 0; i < vertexes.length; ++i) {
for (let j = i + 1; j < vertexes.length; ++j) {
for (let k = j + 1; k < vertexes.length; ++k) {
const circle = circumscribedCircle(vertexes[i], vertexes[j], vertexes[k]);
if (!circle)
continue;
if (vertexes.find((v, l) => ![i, j, k].includes(l) && Math.sqrt((v.x - circle.x) ** 2 + (v.y - circle.y) ** 2) < circle.r))
continue;
circle.c = [
(vertexes[i].c[0] + vertexes[j].c[0] + vertexes[k].c[0]) / 3,
(vertexes[i].c[1] + vertexes[j].c[1] + vertexes[k].c[1]) / 3,
(vertexes[i].c[2] + vertexes[j].c[2] + vertexes[k].c[2]) / 3,
];
vertexes[i].cs.push(circle);
vertexes[j].cs.push(circle);
vertexes[k].cs.push(circle);
circles.push(circle);
}
}
}
// console.log(circles)
// if (true) {
// for (const circle of circles) {
// ctx.strokeStyle = "orange";
// ctx.beginPath();
// ctx.arc(circle.x, circle.y, circle.r, 0, Math.PI * 2);
// ctx.stroke();
// }
// }
// for (let y = 0; y < 500; y += 10) {
// for (let x = 0; x < 500; x += 10) {
// const p = {x, y};
// for (let circle of circles) {
// f(circle.ps[0], circle.ps[1], circle, p)
// f(circle.ps[1], circle.ps[2], circle, p)
// f(circle.ps[2], circle.ps[0], circle, p)
// }
// }
// }
const bsize = 9;
function f(p1, p2, p3, p) {
const t = triangleArea(p1, p2, p3);
const t1 = triangleArea(p3, p2, p);
const t2 = triangleArea(p1, p3, p);
const t3 = triangleArea(p1, p2, p);
const ta = t1+t2+t3;
if (ta - 0.001 < t) {
const r = 255 * (p1.c[0] * t1 + p2.c[0] * t2 + p3.c[0] * t3) / ta | 0;
const g = 255 * (p1.c[1] * t1 + p2.c[1] * t2 + p3.c[1] * t3) / ta | 0;
const b = 255 * (p1.c[2] * t1 + p2.c[2] * t2 + p3.c[2] * t3) / ta | 0;
ctx.fillStyle = `rgb(${r},${g},${b})`
ctx.fillRect(p.x, p.y, bsize, bsize);
}
}
const circleToCircle = [];
const circleToPoint = [];
for (const c1 of circles) {
for (let i = 0; i < 3; ++i) {
const v1 = c1.ps[i];
for (let j = i + 1; j < 3; ++j) {
const v2 = c1.ps[j];
const cs = v1.cs.filter((c) => v2.cs.includes(c));
if (cs.length === 2) {
// const g = ctx.createLinearGradient(v1.x, v1.y, v2.x, v2.y);
// g.addColorStop(0, v1.c);
// g.addColorStop(1, v2.c);
// ctx.fillStyle = g;
// ctx.beginPath();
// ctx.moveTo(v1.x, v1.y);
// ctx.lineTo(cs[0].x, cs[0].y);
// ctx.lineTo(v2.x, v2.y);
// ctx.lineTo(cs[1].x, cs[1].y);
// ctx.fill();
circleToCircle.push({c1: cs[0], c2: cs[1], v1, v2});
} else {
const v3 = c1.ps.find(v => v !== v1 && v !== v2);
const cx = (v1.x + v2.x) / 2;
const cy = (v1.y + v2.y) / 2;
const d = Math.sqrt((c1.x - cx) ** 2 + (c1.y - cy) ** 2);
let x = cx - (c1.x - cx) / d * 500;
let y = cy - (c1.y - cy) / d * 500;
if (sideOfLine(v1, v2, c1) !== sideOfLine(v1, v2, v3)) {
x = cx + (c1.x - cx) / d * 500;
y = cy + (c1.y - cy) / d * 500;
}
// const g = ctx.createLinearGradient(v1.x, v1.y, v2.x, v2.y);
// g.addColorStop(0, v1.c);
// g.addColorStop(1, v2.c);
// ctx.fillStyle = g;
// ctx.beginPath();
// ctx.moveTo(v1.x, v1.y);
// ctx.lineTo(c1.x, c1.y);
// ctx.lineTo(v2.x, v2.y);
// ctx.lineTo(x, y);
// ctx.fill();
circleToPoint.push({c: c1, p: {x, y, c: c1.c}, v1, v2});
}
}
}
}
// for (let y = 0; y < 500; y += 10) {
// for (let x = 0; x < 500; x += 10) {
// const p = {x, y};
// let nearest = null;
// for (const v of vertexes) {
// const d = distance2(v, p);
// if (!nearest || d < nearest.d) {
// nearest = {v, d};
// }
// }
// ctx.fillStyle = `rgb(${nearest.v.c[0] * 255},${nearest.v.c[1] * 255},${nearest.v.c[2] * 255})`;
// ctx.fillRect(p.x, p.y, bsize, bsize);
// for (let cc of circleToCircle) {
// const int = intersect(cc.c1, cc.c2, cc.v1, cc.v2);
// if (int) {
// int.c = [
// (cc.v1.c[0] + cc.v2.c[0]) / 2,
// (cc.v1.c[1] + cc.v2.c[1]) / 2,
// (cc.v1.c[2] + cc.v2.c[2]) / 2,
// ];
// f(cc.c1, int, cc.v1, p);
// f(cc.c1, int, cc.v2, p);
// f(cc.c2, int, cc.v1, p);
// f(cc.c2, int, cc.v2, p);
// } else {
// f(cc.c1, cc.c2, cc.v1, p);
// f(cc.c1, cc.c2, cc.v2, p);
// }
// }
// for (let cp of circleToPoint) {
// const int = intersect(cp.c, cp.p, cp.v1, cp.v2);
// if (int) {
// int.c = [
// (cp.v1.c[0] + cp.v2.c[0]) / 2,
// (cp.v1.c[1] + cp.v2.c[1]) / 2,
// (cp.v1.c[2] + cp.v2.c[2]) / 2,
// ];
// f(cp.c, int, cp.v1, p);
// f(cp.c, int, cp.v2, p);
// f(cp.p, int, cp.v1, p);
// f(cp.p, int, cp.v2, p);
// } else {
// f(cp.c, cp.p, cp.v1, p);
// f(cp.c, cp.p, cp.v2, p);
// }
// }
// }
// }
for (let y = 0; y < 500; y += 10) {
for (let x = 0; x < 500; x += 10) {
const p = {x, y};
let nearest = null;
for (const v of vertexes) {
const d = distance2(v, p);
if (!nearest || d < nearest.d) {
nearest = {v, d};
}
}
ctx.fillStyle = `rgb(${nearest.v.c[0] * 255},${nearest.v.c[1] * 255},${nearest.v.c[2] * 255})`;
ctx.fillRect(p.x, p.y, bsize, bsize);
for (const c2p of circleToPoint) {
if (intersect(c2p.v1, c2p.v2, c2p.c.ps.find(p => c2p.v1 !== p && c2p.v2 !== p), p)) {
const sign = sideOfLine(c2p.c, c2p.p, c2p.v2) ? 1 : -1;
const r = sign * distanceToLine(c2p.c, c2p.p, p) / distance(c2p.v1, c2p.v2) + 0.5;
if (0 < r && r < 1) {
ctx.fillStyle = `rgb(${
(c2p.v1.c[0] + (c2p.v2.c[0] - c2p.v1.c[0]) * r) * 255
},${
(c2p.v1.c[1] + (c2p.v2.c[1] - c2p.v1.c[1]) * r) * 255
},${
(c2p.v1.c[2] + (c2p.v2.c[2] - c2p.v1.c[2]) * r) * 255
})`;
ctx.fillRect(p.x, p.y, bsize, bsize);
}
}
}
for (const circle of circles) {
f(circle.ps[0], circle.ps[1], circle.ps[2], p)
}
}
}
if (showLine) {
for (const cc of circleToCircle) {
drawLine(cc.c1, cc.c2, "white");
}
for (const cp of circleToPoint) {
drawLine(cp.c, cp.p, "gray");
}
}
function drawLine(p1, p2, c) {
ctx.strokeStyle = "black";
ctx.lineWidth = 4;
ctx.beginPath();
ctx.moveTo(p1.x, p1.y);
ctx.lineTo(p2.x, p2.y);
ctx.stroke();
ctx.strokeStyle = c;
ctx.lineWidth = 2;
ctx.beginPath();
ctx.moveTo(p1.x, p1.y);
ctx.lineTo(p2.x, p2.y);
ctx.stroke();
}
for (const v of vertexes) {
ctx.fillStyle = "white";
ctx.fillStyle = `rgb(${v.c[0]*255},${v.c[1]*255},${v.c[2]*255})`;
ctx.strokeStyle = "black";
ctx.beginPath();
ctx.arc(v.x, v.y, 5, 0, Math.PI * 2);
ctx.fill();
ctx.stroke();
}
}
function distance2(p1, p2) {
return (p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2;
}
function distance(p1, p2) {
return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
}
function triangleArea(p1, p2, p3) {
return Math.abs((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x)) / 2
}
function circumscribedCircle(p1, p2, p3) {
const c = 2 * ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x));
if (c === 0)
return null;
const a = p2.x ** 2 - p1.x ** 2 + p2.y ** 2 - p1.y ** 2;
const b = p3.x ** 2 - p1.x ** 2 + p3.y ** 2 - p1.y ** 2;
const x = ((p3.y - p1.y) * a + (p1.y - p2.y) * b) / c;
const y = ((p1.x - p3.x) * a + (p2.x - p1.x) * b) / c;
const r2 = (p1.x - x) ** 2 + (p1.y - y) ** 2;
const r = Math.sqrt(r2);
return {
x, y, r, r2,
ps: [p1, p2, p3],
}
}
function intersectSegment(p1, p2, p3, p4) {
const d = (p1.x - p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x - p4.x);
if (d === 0)
return null;
const x = ((p1.x * p2.y - p1.y * p2.x) * (p3.x - p4.x) - (p1.x - p2.x) * (p3.x * p4.y - p3.y * p4.x)) / d;
const y = ((p1.x * p2.y - p1.y * p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x * p4.y - p3.y * p4.x)) / d;
const p = {x, y};
if (distance2(p, p1) > distance2(p1, p2) || distance2(p, p2) > distance2(p1, p2))
return null;
if (distance2(p, p3) > distance2(p3, p4) || distance2(p, p4) > distance2(p3, p4))
return null;
return p;
}
function intersect(p1, p2, p3, p4) {
return sideOfLine(p1, p2, p3) !== sideOfLine(p1, p2, p4)
}
function sideOfLine(p1, p2, p3) {
const vx1 = p2.x - p1.x;
const vy1 = p2.y - p1.y;
const vx2 = p3.x - p1.x;
const vy2 = p3.y - p1.y;
return vx1 * vy2 > vy1 * vx2;
}
function distanceToLine(p1, p2, p3) {
const vx1 = p2.x - p1.x;
const vy1 = p2.y - p1.y;
const vx2 = p3.x - p1.x;
const vy2 = p3.y - p1.y;
return (vx1 * vy2 - vy1 * vx2) / Math.sqrt(vx1 ** 2 + vy1 ** 2);
}
function animate() {
for (const v of vertexes) {
const r = Math.sqrt((v.x - 250) ** 2 + (v.y - 250) ** 2);
const da = 0.02 * r / 250;
const a = Math.atan2(v.y - 250, v.x - 250) + da;
v.x = Math.cos(a) * r + 250;
v.y = Math.sin(a) * r + 250;
}
draw();
requestAnimationFrame(animate);
}
// animate();
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment