圆内的随机点：在中心更密集，但避免重叠

Question

我有一个函数可以在 C# 中以我通常喜欢的方式生成随机点； '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;
}

如果屏幕上的点的半径为 1，我认为没有重叠。但是在 Unity 中，我有一个半径为 32 的 UI 图像。那么有没有一种方法可以有效地考虑半径，使其不会以我能够生成随机点的方式重叠？

或者，对于圆形而不是网格，是否有泊松盘类型的算法？另外，还有什么其他方法可以防止非蛮力的圆圈中的随机点重叠（如果可能）？（我知道以前有人问过这些类型的问题，所提供的解决方案通常都是蛮力的，比如 this。如果可能的话，我正在寻找更有效的方法。）

Answer 1

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

当然可以，使用 Delauney 三角剖分。我记得甚至还有一个方便的库、脚本，有人用 c# 为 Unity 编写了 delauney。

大家都说了，利用现有的随机函数，简单的在一个圆圈内选择随机点
关于你发的视频link，好久没找到这家伙用的技术了！他的技术是什么？只是纯粹的蛮力？
请注意，暴力破解的速度非常快。你不必费心去计算实际距离，只需将它们框起来（比如曼哈顿距离），无论如何，绝大多数都会在一个轴上被淘汰
如果你对 www 的东西不屑一顾，D3 有你需要的一切，例如

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

提醒一下，涉及的处理是微不足道的，不要浪费太多时间进行优化！

如果（出于某种原因）性能真的很重要：

你能做的最好的就是使用空间散列。

（这只不过是“蛮力” - 即检查所有 - 但你将表面或体积切割成盒子。然后你知道你只需要检查那个盒子或相邻盒子中的项目。）

在数学上它只是一棵 Kd 树。

没有比这更快的方法了。

其实已经有人给出了这样的答案：

您玩过的每个视频游戏，每秒都在进行无数次空间哈希处理！

Answer 2

为什么不直接使用泊松盘呢？

OP 你提到你喜欢使用泊松圆盘采样：

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

你所要做的就是在一个正方形中进行，然后将圆圈外的物品扔掉。这是一个很小的效率低下问题。

圆内的随机点：在中心更密集，但避免重叠

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

c#

random

procedural-generation

unity3d

如果（出于某种原因）性能真的很重要：

为什么不直接使用泊松盘呢？