mercredi 22 septembre 2021

Preventing overlap of random points

Ok hear me out, I'm looking for non-brute force way of generating random coordinates that don't overlap. I know these types of questions have been asked before and the solutions offered are usually something brute force-y like this. I'm looking for something more efficient if possible.

What I have is a function that generates random Points in C# in a way that I generally like (the points are denser in the center and become less dense in outer regions of the 'circle'):

public static IPoint[] GeneratePointsAsCircle(int maxPoints, float scale, float radius=26)
{
    IPoint[] points = new IPoint[maxPoints];
    int count = 0;

    while (count < maxPoints)
    {
        double r = rdm.NextDouble();  // rdm declared outside function, in class
        double theta = rdm.NextDouble() * 2.0 * Math.PI;
        double phi = rdm.NextDouble() * Math.PI;
        double cosTheta = Math.Sin(theta);
        double sinPhi = Math.Sin(phi);
        double cosPhi = Math.Cos(phi);

        double x = r * cosPhi;
        double y = r * sinPhi * cosTheta;

        IPoint point = new Point(x * scale, y * scale);

        /* Here is where people usually suggest a for-loop that checks the overlap
           by calculating the distance to see if its range of the radius (see function args),
           and then finding a new point if it does overlap. Problem is, its inefficient for larger number of points.

        example in pseudo-code:
        overlapping = false;
        foreach(other in points) {
            distance = GetDistance(point, other);
            if (distance < (radius*scale) + (radius*scale))
                 overlapping = true;
                 break;
        }

        if (!overlapping)... */
        points[count++] = point;

        // let run x-amount of times before breaking the loop to prevent a forever loop.

    }

    return points;
}

Now, technically, if the point is on screen has a radius of one, I don't think there is overlap. However in Unity (ugh yes I know, everyone uses it now), I have a UI Image with a radius of 32. So is there away to efficiently account for the radius so it doesn't overlap in the way I've been able to generate the randomized points?

Alternatively, is there a Poisson Disc type of algorithms for circle shapes rather than a grid? ALTERNATIVELY alternatively, what other ways can I prevent overlapping of random points in a circle that is not brute-force (again if possible)?

I know its a lot but any suggestions are appreciated.




Aucun commentaire:

Enregistrer un commentaire