How to effectively distribute points on plane

Question

I have a plane (screen) with its width and height (monitor resolution, not square). And I'd like to distribute points on that plane with the (approximately) same distance from each other.

For example:

• 1 point will be in the middle,
• 2 points will be in the middle of y axis, and x axis will be divided by 3
• 3 points may be like triangle, but if sceen is wide enough, thay can be alighned in same y
• 4 like second part of above, or as rectangle..
• etc to 8 points max

Is there any algorithm for this?

Thank you for your time!

EDIT: same distance from each other and from plane border

EDIT2: I compute centers of mass for groups of objects on which behavior I simulate on plane.

Answer 1

Depending on the precision you want:

• You can get a stochasticaly correct answer by Poisson disk sampling. Specifically, a Poisson disk sampling is a random sampling such that no points are closer than a specified radius. Such thing can be efficiently (linear time) implemented in high dimension - e.g. : the c++ code from Robert Bridson : http://www.cs.ubc.ca/~rbridson/download/curlnoise.tar.gz implementing his paper http://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf

• You can really optimize for the position of the points. This leads to Lloyd algorithms and similar optimization procedures : Compute the Voronoi diagram of an initial set of points, and move these points the the centroid of their Voronoi cell. This can also be done very efficiently, and can be sped up by using a Newton's method rather than a Lloyd iteration. Ultimately, if your domain is a square, you should obtain an hexagonal grid (which minimizes the function above).

If you only need approximate results, I'd suggest the first approach which should be much faster.

Answer 2

If you have lots of points, the result is going to look like an hexagonal grid:

http://people.sc.fsu.edu/~jburkardt/m_src/hex_grid/hex_grid.html

Otherwise it gets more complicated. One algorithm that works very nicely (but is probably overkill), is to do a physics simulation where points are particles that repel each other. Check out this video that does the same on a sphere for an example.