How to randomly but evenly distribute nodes on a plane

Question

Hi All.

I need to place 1 to 100 nodes (actually 25px dots) on a html5 canvas. I need to make them look randomly distributed so using some kind of grid is out. I also need to ensure these dots are not touching or overlapping. I would also like to not have big blank areas. Can someone tell me what this kind of algorithm is called? A reference to an open source project that does this would also be appreciated.

Thanks all

Guido

Answer 1

The easiest way would be to just generate random (x, y) coordinates for each one, repeating if they are touching or overlapping.

Pseudocode:

do N times
{
start:
  x = rand(0, width)
  y = rand(0, height)
  for each other point, p
    if distance(p.x, p.y, x, y) < radius * 2
      goto start
  add_point(x, y);
}

This is O(n^2), but if n is only going to be 100 then that's fine.

Answer 2

I don't know if this is a named algorithm, but it sounds like you could assign each node a position on a “grid”, then pick a random offset. That would give the appearance of some chaos while still guaranteeing that there are no big empty spaces.

For example:

node.x = node.number / width + (Math.random() - 0.5) * SOME_SCALE;
node.y = node.number % height + (Math.random() - 0.5) * SOME_SCALE;

Answer 3

Maybe you could use a grid of circles and place one 25px-dot in every circle? Wouldn't really be random, but look good. Or you could place dots randomly and then make empty areas attract dots and give dots a limited-range-repulsion, but that is maybe too complicated and takes too much CPU time for this simple task.

Answer 4

The Delaunay triangulation is a standard computer graphics algorithm. It might be what you're after: http://en.wikipedia.org/wiki/Delaunay_triangulation. It is part of the Computational Geometry Algorithms Library: http://www.cgal.org/