mathgraphicsgraphcanvas

How to randomly but evenly distribute nodes on a plane


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.


Solution

  • 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.