Find coordinates of n points uniformly distributed in a rectangle

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?

• Off-topic here, I am afraid. – Sasha Apr 19 '13 at 14:08
• Oh i'm sorry about that... what's the proper place for this question? – Oneiros Apr 19 '13 at 14:56
• @Sasha: It isn't Off-topic. A question of Graph theory and co-ordinate system. – Inceptio Apr 19 '13 at 15:12
• You can think of it as packing circles into rectangles, where the radius is half the distance between the points. These problems are hard. This is a duplicate of this question which gives some references. – Ross Millikan Apr 19 '13 at 15:23
• @RossMillikan, nice way to think of the problem! +1 – Parth Thakkar Apr 19 '13 at 15:30

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.

• – lhf Jun 13 '14 at 2:31

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.

That is subject to the discipline of graph drawing, and a non-trivial task.

It touches multidimensional optimization with constraints and is often only solvable by heuristics, like force field approach (imagine all dots and walls charged electrically positive and calculate a configuration of the movable dots with minimal potential energy) or genetic optimization.

BTW a graph with only nodes and no edges is still a graph.