Voronoi patterns

This applet shows an interactive voronoi pattern. Move your mouse over the applet and see the change in the pattern. Refresh the page to get a new pattern.

Each tiny black circle in the pattern, except the one beneath your mouse, is randomly positioned. Each coloured patch consists of pixels that are closest to the black circle in it. Notice therefore that each edge of a patch is a perpendicular bisector of the line between the two circles on either side of it.

Finding out the closest circle for every pixel is going to be slow if you were to do it pixel by pixel. The algorithm given in this youtube video makes the process much faster. The applet above is an implementation of this algorithm.

Another thing that makes the interactivity responsive when calculating new patterns when the mouse is moved around is that, for the pixel in question, one has to calculate only its distance to the mouse. Its distance to the other black circles does not change.

Here is the entire code:

let _canvas;
let _canvas_div;
let _cnv_w, _cnv_h;
let _ctx;
let _image_data;
let _image_buf, _image_buf8, _image_colrs;
let _max_dist_sq;
//let _cnv_left, _cnv_top;
let _min_sq_dists;
let _seed_indices;
let _pointer_x, _pointer_y;

let _num_seeds;
let _rnd_seeds;
let _rnd_colrs;
const two_pi = 2 * Math.PI;

const rnd = (n1, n2) => Math.floor(Math.random() * (n2 - n1 + 1)) + n1;

function initImgData() {
  for (let x = 0; x < _cnv_w; x++) {
    for (let y = 0; y < _cnv_h; y++) {
      let min_dist_sq = _max_dist_sq;
      let seed_index;
      for (let i = 0; i < _num_seeds; i++) {
        const [px, py] = _rnd_seeds[i];
        const dx = x - px;
        const dy = y - py;
        const d_sq = dx * dx + dy * dy;
        if (d_sq < min_dist_sq) {
          min_dist_sq = d_sq;
          seed_index = i;
        }
      }
      const index = y * _cnv_w + x;
      _image_colrs[index] = _rnd_colrs[seed_index];
      _min_sq_dists[index] = min_dist_sq;
      _seed_indices[index] = seed_index;
    }
  }
}

function cornersCheck(x1, y1, x2, y2) {
  const corners = [
    [x1, y1],
    [x2, y1],
    [x2, y2],
    [x1, y2],
  ];
  let seed_index, first_seed_index;
  let recurse = false;
  for (let corner_index = 0; corner_index < 4; corner_index++) {
    const [cx, cy] = corners[corner_index];
    const index = cy * _cnv_w + cx;
    seed_index = _seed_indices[index];
    const min_dist_sq = _min_sq_dists[index];
    const dx = cx - _pointer_x;
    const dy = cy - _pointer_y;
    const d_sq = dx * dx + dy * dy;
    if (d_sq < min_dist_sq) {
      seed_index = _num_seeds;
    }
    if (corner_index === 0) {
      first_seed_index = seed_index;
      continue;
    }
    if (seed_index !== first_seed_index) {
      recurse = true;
      break;
    }
  }
  if (recurse) {
    const pix_w_by2 = (x2 - x1 + 1) / 2;
    const pix_h_by2 = (y2 - y1 + 1) / 2;
    cornersCheck(x1, y1, x1 + pix_w_by2 - 1, y1 + pix_h_by2 - 1);
    cornersCheck(x1 + pix_w_by2, y1, x2, y1 + pix_h_by2 - 1);
    cornersCheck(x1, y1 + pix_h_by2, x1 + pix_w_by2 - 1, y2);
    cornersCheck(x1 + pix_w_by2, y1 + pix_h_by2, x2, y2);
  } else {
    const colr = _rnd_colrs[seed_index];
    for (let x = x1; x <= x2; x++) {
      for (let y = y1; y <= y2; y++) {
        _image_colrs[y * _cnv_w + x] = colr;
      }
    }
  }
}

const draw = () => {
  _ctx.putImageData(_image_data, 0, 0);
  for (const [cx, cy] of _rnd_seeds) {
    _ctx.beginPath();
    _ctx.arc(cx, cy, 2, 0, two_pi);
    _ctx.stroke();
  }
  _ctx.beginPath();
  _ctx.arc(_pointer_x, _pointer_y, 2, 0, two_pi);
  _ctx.stroke();
};

function onPointerMove(e) {
  if (!e.isPrimary) {
    return;
  }
  e.preventDefault();
  _pointer_x = e.offsetX;
  _pointer_y = e.offsetY;
  cornersCheck(0, 0, _cnv_w - 1, _cnv_h - 1);
  _image_data.data.set(_image_buf8);
  requestAnimationFrame(draw);
}

/*
function onTouchMove(e) {
  e.preventDefault();
  _rnd_seeds[0][0] = e.touches[0].clientX - _cnv_left;
  _rnd_seeds[0][1] = e.touches[0].clientY - _cnv_top;
  cornersCheck(0, 0, _cnv_w - 1, _cnv_h - 1);
  _image_data.data.set(_image_buf8);
  requestAnimationFrame(draw);
}
*/

const init = () => {
  _canvas = document.getElementById('canvas');
  _canvas_div = document.getElementById('canvas_div');
  _canvas.addEventListener('pointermove', onPointerMove);
  //_canvas.addEventListener('mousemove', onMouseMove);
  //_canvas.addEventListener('touchmove', onTouchMove);
  onResize();
};

function onResize() {
  _canvas.width = _canvas_div.clientWidth;
  _canvas.height = _canvas_div.clientHeight;
  _cnv_w = _canvas.width;
  _cnv_h = _canvas.height;
  //const { x, y } = _canvas.getBoundingClientRect();
  //_cnv_left = x;
  //_cnv_top = y;
  _ctx = _canvas.getContext('2d');
  _image_data = _ctx.getImageData(0, 0, _cnv_w, _cnv_h);
  _max_dist_sq = _cnv_w * _cnv_w + _cnv_h * _cnv_h;

  _image_buf = new ArrayBuffer(_image_data.data.length);
  _image_buf8 = new Uint8ClampedArray(_image_buf);
  _image_colrs = new Uint32Array(_image_buf);

  _min_sq_dists = new Uint32Array(new ArrayBuffer(4 * _cnv_w * _cnv_h));
  _seed_indices = new Uint8Array(new ArrayBuffer(_cnv_w * _cnv_h));

  _num_seeds = _cnv_w === 512 ? 50 : 24;
  _rnd_colrs = new Uint32Array(new ArrayBuffer(4 * (_num_seeds + 1)));
  _rnd_seeds = [];
  for (let i = 0; i < _num_seeds; i++) {
    _rnd_seeds[i] = [rnd(0, _cnv_w - 1), rnd(0, _cnv_h - 1)];
    _rnd_colrs[i] =
      (255 << 24) | (rnd(0, 255) << 16) | (rnd(0, 255) << 8) | rnd(0, 255);
  }
  _rnd_colrs[_num_seeds] =
    (255 << 24) | (rnd(0, 255) << 16) | (rnd(0, 255) << 8) | rnd(0, 255);
  initImgData();
  _image_data.data.set(_image_buf8);
  draw();
}

window.addEventListener('load', init);
window.addEventListener('resize', onResize, false);
window.addEventListener('orientationchange', onResize, false);