在矩形内均匀随机分配点的算法

Question

我希望将一些点随机放置在矩形中。

生成随机的x、y坐标并不是一个好主意，因为很多时候点主要分布在同一区域而不是覆盖整个矩形。

我不需要一个非常快或最佳覆盖位置的算法，只需要一些能够在简单游戏中运行的东西，可以生成几乎覆盖整个矩形的随机(x,y)。

在我的特定案例中，我正在尝试生成一个简单的天空，所以想在天空矩形中放置大约40/50颗星星。

有人能指导我一些常见的算法来做到这一点吗？

- Philip

---

生成随机的x和y坐标实际上是最好的方法。如果你的随机数生成器没有均匀覆盖整个矩形区域，那么请使用更好的随机数生成器。如果需要更多帮助，请给我们展示你的代码。 - r3mainer

另外，“天空矩形”是什么？也许你的问题是由于纹理被投影到（半球形）天空背景的方式造成的。 - r3mainer

实际代码并没有什么特别之处，只是一个在宽度和高度之间随机生成的Java代码（分别用于x和y坐标）。所谓的“天空矩形”是指笛卡尔空间中的二维矩形。这是一款8位风格的2D游戏，天空大小为288x488。 - Philip

Answer 1

有许多算法可以伪随机填充二维平面。其中之一是泊松盘采样，它会随机放置样本，但然后检查任意两个样本是否太接近。结果看起来会像这样：
您可以查看一些 描述此算法的文章。甚至还有一些 实现可用。

问题在于，得到的分布与实际星空完全不同。但是它提供了一个很好的起点——通过控制泊松半径，我们可以创建非常自然的外观模式。例如，在this文章中，他们使用Perlin Noise来控制泊松盘采样的半径：
您还需要调整星星的亮度，但可以尝试使用均匀随机值或Perlin噪声进行实验。

---

我曾经在一款游戏中采用了完全不同的方法。我从David Nash的HYG数据库中获取星星在笛卡尔坐标系中的真实位置，并将它们转换为我的视角。使用这种方法，甚至可以创建从地球上所处位置可见的精确视图。

我曾经向我想约会的女孩展示过这个数据库，说：“我想向你展示星星……在笛卡尔坐标系中。”

更新：现在已经过去七年了，我们仍然在一起。

- Teivaz

Answer 2

以下是一些可能使你的封面看起来“更加统一”的想法。这些方法不一定提供了一种生成真正统一封面的有效方式，但在你的情况下可能足够好并值得一试。

首先，您可以将原始矩形分成4个（或10个，或100个 - 只要性能允许）子矩形，并单独使用随机点覆盖这些子矩形。通过这样做，您将确保没有子矩形会被遗漏。您可以为每个子矩形生成相同数量的点，但也可以从一个子矩形到另一个子矩形变化点数。例如，对于每个子矩形，您可以首先生成一个随机数num_points_in_subrectangle（可以从某个区间[lower, upper]的均匀随机分布中获得），然后随机填充该子矩形。因此，所有子矩形都将包含随机数量的点，可能看起来不那么“程序生成”。

另一件可以尝试的事情是在原始矩形内生成随机点，并针对每个生成的点检查是否已经存在半径R内的点。如果有这样的点，则拒绝该候选点并生成新的候选点。同样，在这里，您可以通过使R成为一个随机变量来改变从一个点到另一个点的半径。

最后，您可以结合几种方法。生成一些总共需要的随机点数n。首先，将原始矩形分成子矩形，并以这样的方式覆盖它们，以便总共有n / 3个点。然后通过在没有任何限制的情况下选择原始矩形内的随机点来生成接下来的n / 3个点。在此之后，通过检查半径内的邻居随机生成最后的n / 3个点。

- kindanoob

---

非常好的方法，结果简单但看起来完全符合我的要求，非常感谢！ - Philip

Answer 3

使用均匀的X、Y绘制，如果你绘制40个点，所有点都在同一半部分的概率约为万亿分之一（~0.0000000000009）。

- user1196549

---

它如何回答这个问题？ - Teivaz