Algorithm for distributing points evenly but randomly in a rectangle

Question

I want to place some points in a rectangle randomly.

Generating random x, y coordinates it's not a good idea, because many times happens that the points are mainly distributed on the same area instead cover the whole rectangle.

I don't need an algorithm incredibly fast or the best cover position, just something that could run in a simple game that generate random (x, y) that cover almost the whole rectangle.

In my particular case I'm trying to generate a simple sky, so the idea is to place almost 40/50 stars in the sky rectangle.

Could someone point me some common algorithm to do that?

Answer 1

There is a number of algorithms to pseudo-randomly fill a 2d plane. One of them is Poisson Disk Sampling which places the samples randomly, but then checks that any two are not too close. The result would look something like this:

You can check some articles describing this algorithm. And even some implementations are available.

The problem though is that the resulting distribution looks nothing like the actual stars in the sky. But it gives a good tool to start with - by controlling the Poisson radius we can create very naturally looking looking patterns. For example in this article they use Perlin Noise to control the radius of the Poisson Disk Sampling:

You would also want to adjust the brightness of the stars, but you can experiment with uniform random values or Perlin noise.

---

Once I have used a completely different approach for a game. I took real positions of the stars in cartesian system from HYG database by David Nash and transformed them to my viewpoint. With this approach you can even create the exact view that can be seen from where you are on Earth. I once showed this database to the girl I wanted to date, saying "I want to show you the stars… in cartesian coordinate system".

Upd. It’s been over seven years now and we are still together.

Answer 2

Using a uniform drawing of X, Y, if you draw 40 points, the probability of having all points in the same half is about one over a trillion (~0.0000000000009).

Answer 3

Just some ideas which might make your cover to appear "more uniform". These approaches don't necessarily provide an efficient way to generate a truly uniform cover, but they might be good enough and worth looking at in your case.

First, you can divide the original rectangle in 4 (or 10, or 100 - as long as performance allows you) subrectangles and cover those subrectangles separately with random points. By doing so you will make sure that no subrectangle will be left uncovered. You can generate the same number of points for each subrectangle, but you can also vary the number of points from one subrectangle to another. For example, for each subrectangle you can first generate a random number num_points_in_subrectangle (which can come from a uniform random distribution on some interval [lower, upper]) and then randomly fill the subrectangle with this many points. So all subrectangles will contain random number of points and will probably look less "programmatically generated".

Another thing you can try is to generate random points inside the original rectangle and for each generated point check if there already exists a point within some radius R. If there is such point, you reject the candidate and generate the new one. Again, here you can vary the radius from one point to another by making R a random variable.

Finally, you can combine several approaches. Generate some random number n of points you want in total. First, divide the original rectangle in subrectangles and cover those in such a way that there are n / 3 points in total. Then generate next n / 3 points by selecting the random point inside the original rectangle without any restrictions. After this, generate the last n / 3 points randomly with checks for neighbors within the radius.