[Math] Find coordinates of n points uniformly distributed in a rectangle

Question

I have a rectangle R of width W and height H.
I have N points inside this rectangle.
I need to find an algorithm to position my points in the rectangle in the most uniform way possible (no overlaps, max area coverage, uniform density).
So the output of the algorithm should be a list of coordinates.

Here's some examples with different rectangles and points:

Any help?

Answer 1

In the absence of a precise definition of "the most uniform way possible", try this method:

1. Uniformly generate say $100N$ random points in the rectangle. These are the density points.
2. Uniformly generate $N$ random points in the rectangle. These are the sites.
3. Compute an approximate Voronoi diagram of the sites based on the density points. More precisely, assign to each density point the site closest to it.
4. Now, move each site to the barycenter of the density points assigned to it.
5. Repeat steps 3 and 4 say $30$ times (a version of Lloyd's algorithm for approximating a centroidal Voronoi tessellation).

The result is a nicely distributed set of $N$ sites in the rectangle. The images below use $N=100$. Original sites on the left, final sites on the right.