不重叠的随机矩形像素

Question

我想生成随机的矩形，这是一个相当简单的任务。问题在于我需要确保它们不会与任何这些黑点重叠:

为了方便视觉，进行了反转:

现在，我只需告诉它，在生成任何矩形时忽略与任何黑点重叠的部分，但是随着点密度的增加，它会变得像 bogosort 一样低效。是否有更有效的方法来做到这一点？

- GameDungeon

---

也许随着点密度的增加，您可以减小矩形大小。 - David

我已经尝试过了，虽然它改善了一些问题，但并没有解决核心问题。 - GameDungeon

矩形可以重叠吗？ - samgak

可以的。虽然这不是问题的一部分，但在我的情况下，我放置了一个矩形，它的某些部分会创建更多的点，但其余部分可以重叠。 - GameDungeon

Answer 1

您可以使用多个随机生成的四叉树来生成不包含任何点的轴对齐边界框列表，然后对于每个矩形，从列表中随机选择一个AABB，然后在AABB内随机生成一个矩形。

您不需要保留四叉树结构，因为您只对叶节点（即AABB）感兴趣。从一个包含整个2D空间的AABB开始，并编写一个递归函数，接受一个AABB和一个点列表。创建一个空的AABB列表，然后使用顶级边界框和点列表调用该函数。

在函数内部，随机选择一个点作为分割线，并随机选择方向（水平或垂直），或交替使用水平和垂直。使用分割点上下X或Y值之上的点创建两个点列表，并使用点分割AABB参数创建两个AABB，然后递归调用该函数两次。如果使用空点列表调用该函数，则将AABB添加到列表中并停止递归。

如果您从顶层多次调用此函数，则列表中将有一堆重叠的AABB（如果随机选择分割点，则不会有任何明显的伪影），因此您可以随机生成任意数量的矩形。

设置将基于点数的O(N log N)（在平均情况下），而随机矩形生成将为O(1)。

为了使分布更加均匀，您可以计算列表中每个AABB的面积，并根据其大小加权随机选择它的概率。如果使用二叉搜索树将原始随机数映射到加权AABB，则会使随机生成为O(log N)。

- samgak

Answer 2

这是我提出的与其他人所提出的略有不同的想法。以下是算法步骤：

1. 创建两个数组用于点的x和y值。将x和y复制到数组中并按升序排序。
2. 创建随机x和随机y。这将是矩形的左上角。我们称它们为x1和y1。
3. 在x数组中进行二分查找，找到最小的x使得x >= x1。
4. 在y数组中进行二分查找，找到最大的y使得y <= y1。
   • 如果x1 == x or y1 == y: go to step 2 注意：我们不能扩展以创建矩形。
5. 在步骤3中找到的右边界x和左边界y之间创建一个随机的x，两端都不包括。将其称为x2。
6. 在步骤4中找到的下边界y和上边界y之间创建一个随机的y，两端都不包括。将其称为y2。
7. 将(x1, y1)和(x2, y2)保存为矩形的左上角和右下角。
8. 重复步骤2。

这个算法的初始时间复杂度为O(n * log n)，准备阶段的空间复杂度为O(n)，其中n是给定点的数量。每个矩形创建都需要进行一次O(log n)的二分查找。我假设矩形左上角与点之间发生碰撞的概率非常低，因此我们可以忽略它。

这种方法还允许您在对点进行正确的数据结构选择（类似于排序映射、排序列表或类似于特定语言中的名称）的情况下以对数时间更新点。

- user1984

Answer 3

1. 生成随机线段（不经过任何点）（附图中的绿色线段）
2. 找到离矩形每侧最近的点的距离（红线）
3. 选择在红线上属于矩形边的两个随机点（黄点）

- matszwecja

---

这很聪明，但它只是把问题转移到了找到行的链条上，你能包含一个好的方法来解决这个问题吗？虽然这对于更高密度来说是相当大的改进。 - GameDungeon

你甚至可以进一步扩展相同的想法，即选择一个随机点，并检查在撞到点之前你可以向每个方向走多远（虽然与矩形相比，这种情况发生的可能性要小得多），然后选择在这些边界之间的初始线段。 - matszwecja

Answer 4

1. 随机选择一个白点。

2. 找到最近的黑点。这将成为圆的半径。

3. 创建以随机点为中心的圆。

4. 在圆上选择两个点。找到它们的对称点，通过圆心画出4个点的矩形。

P.S. 确保这两个点不是圆的直径...

- David

---

虽然这完全符合我的目的，但我要注意这并不是真正的随机。我不确定，但我认为选择圆内而不是圆外的点会使它再次变得随机。那也会修复PS。 - GameDungeon