jeudi 16 septembre 2021

"Uniformly random" distribution of 2D points over given time

I am looking for an optimal algorithm to solve the following problem:

On a two-dimensional plane, a set of N points with X and Y coordinates is given. These points need to be "lit" during a cycle of length t in such a way that for each discrete step of length t/N, one point is "lit". The distribution of points by steps should not be truly random, but look "uniformly random" to a person. Thus, each taken several points in a row should be at a sufficient distance from each other.

At the moment, I propose to implement the following algorithm:

  1. Divide the plane into several regions with a (different) number of points.
  2. Fill each of them with "fake" points up to the number of N.
  3. Each of the regions is then shuffled using Fisher-Yates.
  4. Then the shuffled points of each region are evenly distributed over time t with N steps.
  5. Then, for each step, we take one point from each region in random order, discarding the "fake" ones and adding the existing ones to the ordered array.
  6. The position of the point in the resulting array is the desired step number.

Will this approach lead to a distribution that will seem "randomly uniform" to people? Perhaps there is a simpler implementation? Markov chains? Something like dithering?




Aucun commentaire:

Enregistrer un commentaire