# How to effectively distribute points on plane

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?

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.

-
I feel any such reasonable algorithm will work for large number of points. for small number of points (say the first 10), encode the distribution explicitly – magguu Mar 4 '13 at 10:07
@magguu okay, but i'd like to be as responsive as possible, use %? – Kamil Mar 4 '13 at 10:09
i do not get you. Let me reiterate. I am saying that for some low numbers say upto 10, work out the distribution explicitly on by one. for larger numbers - use some reasonable strategy as you have devised. – magguu Mar 4 '13 at 10:23
@magguu i think i do get you, but i don't know how to do it, because resolution may change everytime and i'd like to know how to do it on any screen resolution / planes with various widths and heights. For example with 3 points: how do i know if it will be triangle or in one line? Or use intervals? – Kamil Mar 4 '13 at 10:29
Somehow i feel that a solution could have a connection to the construction of voronoi diagrams. One Issue is that the soultion must noch be unique (at least for a square. What exactly do you mean with same distance from each other and the boundary? every distance from every point to another point and the boundary shall be equal or every point has a distance $d$ to any other point and a distance $e$ to the boundary – Quickbeam2k1 Mar 4 '13 at 10:45

The question is a bit vague, but the first idea that came to my mind would be to use a low-discrepancy sequence such as a Halton sequence or a Sobol sequence. Here are examples of 256 points distributed on the plane using each of them, with a random distribution for comparison:

From left to right: Halton sequence, Sobol sequence, random sequence. Images by Jheald / Wikimedia Commons, licensed under the CC-By-SA 3.0 license.

At least, you could use these sequences as starting configurations for a local optimization algorithm, which might e.g. repeatedly move each point a small distance away from its nearest neighbor until the configuration stabilizes.

-

First of all, thanks to everybody for suggestions which helped me to define my problem better and to find best solution to my problem.

Now I am using Centroidal Voronoi tessellation which according to Wikipedia: "In geometry, a centroidal Voronoi tessellation (CVT) is a special type of Voronoi tessellation or Voronoi diagrams. A Voronoi tessellation is called centroidal when the generating point of each Voronoi cell is also its mean (center of mass). It can be viewed as an optimal partition corresponding to an optimal distribution of generators."

Its very fast and there is implementation in D3js library for javascript which I am using.

-