2

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: Voronoi diagram constucted bu coloring pixel of a canvas

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.

Bumhan Yu
  • 2,078
  • 1
  • 10
  • 20
  • A bit more context and a [mcve] of your code so far would be great. Is there a reason not to use [d3](https://github.com/d3/d3-delaunay)? – ggorlen Jun 16 '22 at 16:57
  • In my opinion this is more a question for math StackExchange – Christian Vincenzo Traina Jun 16 '22 at 18:40
  • 1
    I also found [this](https://stackoverflow.com/questions/85275/how-do-i-derive-a-voronoi-diagram-given-its-point-set-and-its-delaunay-triangula). With a bit of math you can derive your vertix points – Christian Vincenzo Traina Jun 16 '22 at 18:48
  • @ggorlen, using d3 looks like a viable option, I'll look into this, that you. Also added code snippet to the post. Still I was thinking I can implement something myself for the sake of learning – Jsutotherel Jun 16 '22 at 18:52

0 Answers0