平滑圆内随机点的最快方法是什么?

What's the fastest method of smoothing random points within a circle?

我正在开发一个游戏原型,它将涉及从一个非常大的点列表(很容易在十万范围内,因为它将是一个小行星)创建的 Delaunay 三角形生成地图,但是要做到这一点,我需要在一个大圆圈中很好地分布点。

我特别使用 Delaunay 三角形的原因是,通过限制边长来强制三角形的最大尺寸相当容易。对于 Voronoi 单元,我将不得不查看单元占据的区域,该区域要密集得多,而且我真的不知道其他从点生成多边形的好方法。

我知道如何统一放置随机点,使外层包含与其面积成比例的更多点,但是我需要平滑点以确保 Delaunay 集没有大间隙或密集的点簇。我需要的一个很好的例子是 Lloyd's Algorithm,但是我更喜欢一种运行速度尽可能快的方法来实现大致均匀的分布,因为它应该在不超过几分钟的时间内通过所有点平均低端 CPU(假设 2GHz 单核)。

在我看来,确定它大致均匀的一个很好的基线是检查每个点并查看到最近邻居的距离。如果一个点的最小距离至少是最大距离的两倍,则它是不均匀的。

如果需要,如果平滑需要合理的起点,我可以修改我的点分布函数以创建大致均匀的象限分布,或者您可以提供自己的起点。但是,这仅适用于与不这样做相比节省大量时间的情况(我希望如此,因为它减少了最坏的情况)。

最后,一个符合设定半径平滑的答案比一个需要改变结果的答案更有价值,一个可以符合给定径向高度图(通过函数调用角度)的答案是价值更高,因为我已经计划创建一个径向高度图(平坦的行星很无聊)。此外,Java 中的代码示例本质上更有用,因为我将在其中制作我的游戏,但其他代码示例也很好。

关于如何以最大效率解决圆中的平滑点问题有什么建议吗?

从均匀分布开始(从静态均匀分布集中随机挑选)。

为每个点添加一个小振幅的随机高斯噪声。

结束。