生成具有定义的最小和最大距离的随机点

Question

我需要算法思路来在2D空间中生成点,并在点之间定义最小和最大可能距离.

Bassicaly,我想找到一种在填充点的2D空间中插入点的好方法,使点具有随机位置,但也比MINIMUM_DISTANCE_NUM多,并且距离最近点小于MAXIMUM_DISTANCE_NUM.

我需要它用于游戏,所以它应该很快,而不是取决于随机概率.

Answer 1

将点集存储在Kd 树中。随机生成一个新点，然后检查其最近的邻居，这些邻居可以在 Kd 树中快速查找。如果该点被接受（即 MIN_DIST < 最近邻居 < MAX_DIST），则将其添加到树中。

我应该注意到，这在点不太紧密排列的情况下效果最好，即 MIN * N << L 其中 N 是点的数量，L 是您将它们放入的盒子的尺寸。如果这是不正确，那么大多数新点将被拒绝。但想一想，在这个限制下，你将弹珠装入一个盒子中，并且在一定密度以上，排列不可能非常“随机”。

Answer 2

您可以使用点的二维规则网格（P0，P1，P2，P3，...，P（m * n），当m是该网格的宽度，n是该网格的高度）

每个点都与 1) 一个布尔值相关联，表示该网格点是否被使用，以及 2) 从该网格位置的“移位”以避免过多的规律性。（或者您可以将点+移位坐标放入网格中）

然后，当您需要新点时，只需在网格中随机选择一个未使用的点，将该点声明为“已使用”，然后在游戏中使用点+移位。

根据您的 2D 空间的 n、m、宽度/高度以及您要使用的点数，这可能就很好。