不重叠某些像素的随机矩形
Random Rectangles without Overlapping some Pixels
我想生成随机矩形。这是一项非常容易的任务。问题是我需要它们不与这些黑点中的任何一个重叠：
倒置以便于查看：
现在我可以告诉它忽略它生成的任何矩形，如果它与任何黑点重叠，但随着点密度的增加，它会达到 bogosort 级别的低效率。有没有更有效的方法来做到这一点？
- 生成随机线段（不通过任何点）（附图上的绿线）
- 求矩形每边最近点的距离（红线）
- 在属于矩形边的红线上随机选择两个点（黄点）
Select一个随机的白点。
找到最近的黑点。这将是圆的半径
创建一个以随机点为中心的圆。
在圆上选择 2 个点。找到过圆心的对角点，用这4个点画出矩形
P.S。只要确保这两个点不是圆的直径...
这是我的想法，与其他人提出的想法略有不同。这是算法：
- 为点的 x 和 ys 创建 2 个数组。复制 x 和 ys 并逐步对数组进行排序。
- 创建随机 x 和随机 y。这将是矩形的左上角。我们称它们为
x1 和 y1.
- 在 x 数组中进行二分查找，寻找满足
x >= x1. 的最小 x
- 在 y 数组中进行二分查找最大的 y，使得
y <= y1。
- if
x1 == x or y1 == y: go to step 2 注意：我们不能展开创建一个矩形。
- 在第 3 步中找到的
x1 and the right bound x 之间创建一个随机 x，两端互斥。称之为 x2.
- 在您在第 4 步中找到的
y2 and the lower bound y 之间创建一个随机 y，两端互斥。称之为 y2.
- 将
(x1, y1) 和 (x2, y2) 保存为矩形的左上角和右下角。
- 从第 2 步开始重复。
此算法的初始时间复杂度为 O(n * log n)，space 的准备阶段复杂度为 O(n)，其中 n 是给定点的数量。每个矩形创建的二进制搜索时间复杂度为 O(log n)。我假设矩形的左上角和一个点发生碰撞的概率很低，可以忽略不计。
如果您为它们选择了正确的数据结构（类似于排序映射、排序列表或类似的东西，取决于它在特定语言中的名称），这种方法还允许您以对数时间更新点。
您可以使用多个随机生成的四叉树来生成不包含任何点的轴对齐边界框列表，然后对于每个矩形，从列表中随机 select 一个 AABB，然后随机在 AABB 内生成一个矩形。
您不需要保留四叉树结构，因为您只对叶节点（AABB）感兴趣。从包含整个 2D space 的 AABB 开始，然后编写一个接受 AABB 和点列表的递归函数。创建一个空的 AABB 列表，然后使用顶级边界框和点列表调用该函数。
在函数内部，随机 select 一个点用作分割线，随机 select 一个方向（水平或垂直）或水平和垂直交替。创建两个由分裂点的 X 或 Y 值上方和下方的点组成的点列表，并通过使用该点分裂 AABB 参数来创建两个 AABB，然后递归调用该函数两次。如果使用空点列表调用该函数，则将 AABB 添加到您的列表并停止递归。
如果你多次从顶层调用它，你的列表中将有一大堆重叠的 AABB（前提是分裂点是 select随机编辑的），所以不会有任何明显的随机生成的工件。然后，您可以根据需要随机生成任意数量的矩形。
点数的设置为 O(N log N)（在平均情况下），随机矩形生成为 O(1)。
为了使分布更均匀，您可以计算列表中每个 AABB 的面积，并根据其大小对随机 select 分配它的概率进行加权。如果您使用二叉搜索树将您的原始随机数映射到您的加权 AABB，它会使您的随机生成 O(log N)
我想生成随机矩形。这是一项非常容易的任务。问题是我需要它们不与这些黑点中的任何一个重叠：
倒置以便于查看：
现在我可以告诉它忽略它生成的任何矩形，如果它与任何黑点重叠，但随着点密度的增加，它会达到 bogosort 级别的低效率。有没有更有效的方法来做到这一点？
- 生成随机线段（不通过任何点）（附图上的绿线）
- 求矩形每边最近点的距离（红线）
- 在属于矩形边的红线上随机选择两个点（黄点）
Select一个随机的白点。
找到最近的黑点。这将是圆的半径
创建一个以随机点为中心的圆。
在圆上选择 2 个点。找到过圆心的对角点，用这4个点画出矩形
P.S。只要确保这两个点不是圆的直径...
这是我的想法，与其他人提出的想法略有不同。这是算法：
- 为点的 x 和 ys 创建 2 个数组。复制 x 和 ys 并逐步对数组进行排序。
- 创建随机 x 和随机 y。这将是矩形的左上角。我们称它们为
x1和y1. - 在 x 数组中进行二分查找，寻找满足
x >= x1. 的最小 x
- 在 y 数组中进行二分查找最大的 y，使得
y <= y1。- if
x1 == x or y1 == y: go to step 2注意：我们不能展开创建一个矩形。
- if
- 在第 3 步中找到的
x1 and the right bound x之间创建一个随机 x，两端互斥。称之为x2. - 在您在第 4 步中找到的
y2 and the lower bound y之间创建一个随机 y，两端互斥。称之为y2. - 将
(x1, y1)和(x2, y2)保存为矩形的左上角和右下角。 - 从第 2 步开始重复。
此算法的初始时间复杂度为 O(n * log n)，space 的准备阶段复杂度为 O(n)，其中 n 是给定点的数量。每个矩形创建的二进制搜索时间复杂度为 O(log n)。我假设矩形的左上角和一个点发生碰撞的概率很低，可以忽略不计。
如果您为它们选择了正确的数据结构（类似于排序映射、排序列表或类似的东西，取决于它在特定语言中的名称），这种方法还允许您以对数时间更新点。
您可以使用多个随机生成的四叉树来生成不包含任何点的轴对齐边界框列表，然后对于每个矩形，从列表中随机 select 一个 AABB，然后随机在 AABB 内生成一个矩形。
您不需要保留四叉树结构，因为您只对叶节点（AABB）感兴趣。从包含整个 2D space 的 AABB 开始，然后编写一个接受 AABB 和点列表的递归函数。创建一个空的 AABB 列表，然后使用顶级边界框和点列表调用该函数。
在函数内部，随机 select 一个点用作分割线，随机 select 一个方向（水平或垂直）或水平和垂直交替。创建两个由分裂点的 X 或 Y 值上方和下方的点组成的点列表，并通过使用该点分裂 AABB 参数来创建两个 AABB，然后递归调用该函数两次。如果使用空点列表调用该函数，则将 AABB 添加到您的列表并停止递归。
如果你多次从顶层调用它，你的列表中将有一大堆重叠的 AABB（前提是分裂点是 select随机编辑的），所以不会有任何明显的随机生成的工件。然后，您可以根据需要随机生成任意数量的矩形。
点数的设置为 O(N log N)（在平均情况下），随机矩形生成为 O(1)。
为了使分布更均匀，您可以计算列表中每个 AABB 的面积，并根据其大小对随机 select 分配它的概率进行加权。如果您使用二叉搜索树将您的原始随机数映射到您的加权 AABB，它会使您的随机生成 O(log N)