I'm trying to construct a Voronoi diagram using p5.js
. So far I have managed to create an image representation of it by coloring pixels that belong to the same region, using the algorithm from this video. Here how it looks like:
Here's the code (a bit messy and terribly inefficient)
const h = 512
const w = 512
const scl = 512;
const rez = h / scl;
const tiles = []
let points = []
function randomIntFromInterval(min, max) { // min and max included
return Math.floor(Math.random() * (max - min + 1) + min)
}
function setup() {
createCanvas(w, h);
background(220);
for (let i = 0; i < 12; i++) {
const p = randomIntFromInterval(0, h * h)
points.push(p)
}
for (let y = 0; y < scl; y++) {
for (let x = 0; x < scl; x++) {
tiles.push(0);
const xx = x * rez;
const yy = y * rez;
noFill();
stroke(0);
rect(xx, yy, rez, rez);
const indx = `${x + y * scl}`
if (+indx === points[0] || +indx === points[1] || +indx === points[2]) {
stroke(225, 0, 0)
fill(255, 0, 0)
}
text(indx, xx + rez / 2 - 5, yy + rez / 2 + 5)
}
}
compute(0, scl, scl)
for (const p of points) {
const x = p % scl;
const y = (p - x) / scl;
fill(0)
circle(x * rez, y * rez, 5)
}
}
function compute(x, len, grandLen) {
const corners = getCorners(x, len, grandLen)
const lookup = []
for (const corner of corners) {
const ds = []
for (const point of points) {
ds.push(distance(corner, point, scl));
}
lookup.push(ds)
}
const is = []
for (let i = 0; i < lookup.length; i++) {
const min = Math.min(...lookup[i])
const iMin = lookup[i].indexOf(min);
is.push(iMin);
}
if (is.every((val, i, arr) => val === arr[0])) {
const colorR = map(points[is[0]], 0, h*h, 0, 255)
const colorG = 255 - map(points[is[0]], 0, h*h, 0, 255)
paintRegion(corners[0], len, rez, color(colorR, colorG, 200))
} else {
const rects = divide(corners[0], len)
rects.forEach(r => {
compute(r, len / 2, grandLen)
})
}
}
function paintRegion(a, len, size, color) {
let ax;
let ay;
[ax, ay] = toCoords(a);
fill(color)
noStroke(0);
rect(ax * size, ay * size, size * len, size * len)
}
function toCoords(index) {
const x = index % scl;
const y = Math.floor((index - x) / scl);
return [x, y]
}
function distance(a, b, len) {
let ax;
let ay;
let bx;
let by;
[ax, ay] = toCoords(a);
[bx, by] = toCoords(b);
const p1 = Math.pow(bx - ax, 2);
const p2 = Math.pow(by - ay, 2);
return sqrt(p1 + p2);
}
// l1 is square, l2 is canvas
function getCorners(a, l1, l2) {
const corners = []
corners.push(a);
corners.push(a + l1 - 1);
corners.push(a + (l1 - 1) * l2)
corners.push(a + (l1 - 1) * l2 + (l1 - 1));
return corners
}
function divide(a, len) {
let ax;
let ay;
[ax, ay] = toCoords(a);
const d = len / 2;
const p1 = ax + ay * scl;
const p2 = ax + d + ay * scl;
const p3 = ax + (ay + d) * scl;
const p4 = ax + d + (ay + d) * scl;
return [p1, p2, p3, p4];
}
function draw() {
}
<script src="https://cdn.jsdelivr.net/npm/p5@1.5.0/lib/p5.js"></script>
My problem is, such representation isn't very useful for me. I need get coordinates of regions' edges (including edges of a canvas). I've searched for ways to find edges of a shape on a 2d plane, but I feel like this is a very backwards approach. Is there a way to calculate a Voronoi diagram edges? If not, what's the simplest way to find edges by going over the pixels array?
I know there is quite a few resources on how to do this using numpy or in matlab, but I actually need a javaScript solution, if possible.
UPD: As I was researching the topic further and looking into related question brought up by Cristian in the comments, I came up to a conclusion that Future's algorithms is the best option for getting regions' edges. Fortunately, Wikipedia has links to its implementations. I tried this great implementation by Raymond Hill and it worked out great.