Random points inside a circle: denser in the center, but avoiding overlap-CodePudding

I have 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 sinTheta = Math.Sin(theta);
        double sinPhi = Math.Sin(phi);
        double cosPhi = Math.Cos(phi);

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

        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;
}

If the point on screen has a radius of one, I don't think there is overlap. However in Unity, I have a UI Image with a radius of 32. So is there a way 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? Also, alternatively, what other ways can I prevent overlapping of random points in a circle that is not brute-force (if possible)? (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.)

CodePudding user response：

what other ways can I prevent overlapping of random points in a circle that is not brute-force

Sure, use Delauney triangulation. As I remember there's even a handy library, script, someone wrote delauney in c# for Unity. Enjoy!

as everyone has said, use the existing random functions to simply choose random points in a circle
regarding the video link you posted, it is so long I couldn't find the technique the guy is using! what is his technique? just pure brute force?
be aware that brute force is incredibly quick. you dont bother doing the actual distance, just box 'em (like manhattan distance), the vast majority get eliminated on one axis anyway
if you muck about with www stuff, D3 has everything you need, eg

https://observablehq.com/@d3/force-directed-graph

a reminder too that the processing involved is trivial, don't waste too much time optimizing!

If (for some reason) performance truly matters:

the best you can do is just use spatial hashing.

(Which is nothing more than "brute force" - ie check them all - but you cut the surface or volume up in to boxes. Then you know you need only check the items in that or adjacent boxes.)

Mathematically it's just a Kd tree.

There's no faster way.

In fact someone already gave such an answer:

https://stackoverflow.com/a/9070925/294884

Every single video game you've ever played, is doing spatial hashing a zillion times a second!

CodePudding user response：

Why not just use poisson disk ?

OP you mention you like using poisson disk sampling:

https://www.jasondavies.com/poisson-disc/

All you do is do it in a square, and, throw away items outside the circle. That's a tiny inefficiency and no problem.