Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 Maraz 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 Maraz 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

2 Answers 2

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:

Halton sequence Sobol sequence Random sequence
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.

share|improve this answer
up vote 0 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.