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

Maybe you should create a library of pleasing patterns to choose from. The easiest are rectangular grids. Choose one that has enough dots (maybe a few too many) and aspect ratio close to the rectangle you have to put the dots in. Say your rectangle is $1 \times 3$ and you want $20$ dots. You could make a grid of $2 \times 10$ or $4 \times 5$ but they don't fit very well, so maybe you use $3 \times 7$ with one left out. In this case, if your grid is $n \times m$, you have $n-1$ full spaces between thee dots and 2 half spaces between the dots and the edge, so that gives you the spacing.

A little harder is the pattern on the far right. This would be a nice idea for $20$ dots. You can put the dots on the corners of equilateral triangles, for example.