How to randomly generate a bunch of sites on a 2D plane that have roughly the same amount of space between them?

Question

I use JavaFX to display the sites, but you shouldn't need to understand JavaFX to answer my question. I wanted to include a full working code-example so you can run it yourself. However, to help me out, you probably only need to look at the randomlyChooseSites() method at the bottom of my example.

In this code I generate a bunch of randomized points on a 2D plane. I would like them to be more equal in distance from each-other without being perfectly equal in distance.

How can I randomly generate points on a 2D plane and have them be closer to equal in distance from each-other than they are now, without being perfectly equal in distance?

public class MCVE extends Application {

private final static int WIDTH = 400;
private final static int HEIGHT = 500;

private final static int AMOUNT_OF_SITES = 50;

private final static SplittableRandom RANDOM = new SplittableRandom();

@Override
public void start(Stage primaryStage) {

   // Create the canvas
   Canvas canvas = new Canvas(WIDTH, HEIGHT);
   GraphicsContext gc = canvas.getGraphicsContext2D();
   drawShapes(gc);

   // Add the canvas to the window
   Group root = new Group();
   root.getChildren().add(canvas);
   primaryStage.setScene(new Scene(root));

   // Show the window
   primaryStage.setTitle("Sweep-Line Test");
   primaryStage.show();
}

/**
 * Draws shapes on the Canvas object.
 *
 * @param gc
 */
private void drawShapes(GraphicsContext gc) {

   gc.setFill(Color.BLACK); // sites should be black

   // create random sites
   ArrayList<int[]> siteSet = randomlyChooseSites();

   // add the random sites to the displayed window
   for(int[] i : siteSet) {
      gc.fillRect(i[0], i[1], 5, 5);
   }

}

/**
 * Randomly chooses sites and returns them in a ArrayList
 * @return
 */
private ArrayList<int[]> randomlyChooseSites() {
   // create an ArrayList to hold the sites as two-value int[] arrays.
   ArrayList<int[]> siteList = new ArrayList<>();

   int[] point; // holds x and y coordinates
   for(int i = 0; i < AMOUNT_OF_SITES; i++) {
      // randomly choose the coordinates and add them to the HashSet
      point = new int[] {RANDOM.split().nextInt(WIDTH), RANDOM.split().nextInt(HEIGHT)};
      siteList.add(point);
   }

   return siteList;
}

}

Answer 1

(Actually, expressing the question more exactly would help you find the answer.)

This is a possible solution, in case if you are looking for the same average distance between neighboring points (along each axis):

So for this solution, divide the plane into equal size rectangles, each one will contain one point. Place the point randomly in the rectangle, and do this for all rectangles. Then the average distance between all neighboring points will be the same... along each axis.

I used a perfect square grid, with both sides the same. Then find the smallest perfect square grid that will fit that number of sites, and remove the extra areas in the corners. (For 50 sites it's 8x8 (64)).

Modify the randomlyChooseSites function like this:

private ArrayList<int[]> randomlyChooseSites() {
    // create a HashSet to hold the sites as two-value int[] arrays.
    ArrayList<int[]> siteList = new ArrayList<>();

    class SiteArea
    {
        boolean is_used; // if false, ignore this area (and the point in it)

        int point_x; // absolute coordinates of point generated in this area
        int point_y;
    }

    int gridsize = (int)Math.ceil (Math.sqrt (AMOUNT_OF_SITES));
    int empty_areas = gridsize * gridsize - AMOUNT_OF_SITES; // we want the empty areas in the corners

    int area_size_x = WIDTH / gridsize;
    int area_size_y = HEIGHT / gridsize;

    SiteArea areas[][] = new SiteArea [gridsize][gridsize];

    // initialize all areas on the grid
    for (int i = 0, imax = gridsize * gridsize; i < imax; i++)
    {
        int x_ = (i % gridsize), x = x_ * area_size_x;
        int y_ = (i / gridsize), y = y_ * area_size_y;

        SiteArea a = areas[x_][y_] = new SiteArea ();
        a.is_used = true; // set all areas as used initially

        // generate the point somewhere within this area
        a.point_x = x + RANDOM.split().nextInt(area_size_x);
        a.point_y = y + RANDOM.split().nextInt(area_size_y);

        // to see the grid, create a drawRect() function that draws an un-filled rectangle on gc, with the other params being: top left corner x, y and rectangle width, height
        //drawRect (gc, x, y, area_size_x, area_size_y);
    }

    // disable some of the areas in case if the grid has more rectangles than AMOUNT_OF_SITES
    // cut away at the four corners, by setting those areas to is_used = false
    class Corner { int x; int y; int xdir; int ydir; Corner (int a,int b,int c,int d) { x=a;y=b;xdir=c;ydir=d; } }
    int z = gridsize-1; Corner corners[] = { new Corner (0,0,1,1), new Corner (z,0,-1,1), new Corner (0,z,1,-1), new Corner (z,z,-1,-1) };
    for (int i = 0, imax = empty_areas; i < imax; i++)
    {
        Corner c = corners[i % 4]; // cycle over the corners
        int x = c.x, y = c.y, offset = (i + 4) / 8, xo = offset, yo = offset;
        if (i % 8 > 3)
        {   // cut x
            xo = 0;
        }
        else
        {   // cut y
            yo = 0;
        }
        areas[x + xo * c.xdir][y + yo * c.ydir].is_used = false;
    }

    // export the generated points to siteList
    for (int i = 0, imax = gridsize * gridsize; i < imax; i++)
    {
        int x_ = (i % gridsize);
        int y_ = (i / gridsize);
        SiteArea a = areas[x_][y_];
        if (a.is_used)
        {
            siteList.add (new int[] { a.point_x, a.point_y });
        }
    }



    return siteList;
}

Some points will be very close, this can be avoided by adding a change to generate the points closer to the center of each rectangle.