3

我在舞台上的随机位置绘制矩形，我不希望它们重叠。所以对于每个矩形，我需要找一个空白区域来放置它。

我考虑过尝试一个随机位置，验证它是否免费

private function containsRect(r:Rectangle):Boolean {
    var free:Boolean = true;
    for (var i:int = 0; i < numChildren; i++)
        free &&= getChildAt(i).getBounds(this).containsRect(r);
    return free;
}

如果它返回 false，则尝试另一个随机位置。

问题是，如果没有可用空间，我将永远被困在尝试随机位置。

有一个优雅的解决方案吗？

4

7 回答 7

3

您可以通过转换来简化事情。如果您正在寻找放置 LxH 矩形的有效位置，则可以改为将所有先前的矩形 L 个单位向右增长，H 个单位向下增长，然后搜索一个不与其中任何一个相交的点. 该点将是放置新矩形的有效位置的右下角。

接下来应用扫描线扫描算法来查找未被任何矩形覆盖的区域。如果你想要一个均匀的分布，你应该选择一个由自由区域分布加权的随机 y 坐标（假设你向下扫）。然后从您选择的扫描线中的开放段中均匀地选择一个随机 x 坐标。

于 2009-01-28T13:37:08.177 回答
3

设 S 为舞台面积。令 A 为我们要绘制的最小矩形的面积。令 N = S/A

一种可能的确定性方法：

当您在空舞台上绘制一个矩形时，这会将舞台划分为最多 4 个可以适合您的下一个矩形的区域。当您绘制下一个矩形时，一个或两个区域被分成最多 4 个子区域（每个）可以适合一个矩形等。您永远不会创建超过 N 个区域，其中 S 是您的舞台面积，并且A 是最小矩形的面积。保留区域列表（未排序即可），每个区域由其四个角点表示，每个区域都标有其面积，并使用按面积加权的水库采样使用 1 的水库大小选择一个区域，其概率与其面积成正比，最多一次通过列表。然后在该区域的随机位置放置一个矩形。（从该区域的左下角选择一个随机点，该点允许您绘制一个以该点为左下角的矩形，而不会碰到上墙或右墙。）

如果您不是从空白阶段开始，那么只需在 O(N) 中构建可用区域列表（例如，通过以任何顺序在空白阶段重新绘制所有现有矩形），然后再搜索要绘制的第一个点一个新的矩形。

注意：您可以将水库大小更改为 k 以一步选择接下来的 k 个矩形。

注意 2：您也可以将可用区域存储在树中，每个边的权重等于子树中区域面积与舞台面积之和。然后在 O(logN) 中选择一个区域，我们递归地选择具有根区域的概率面积 / S 的根，或者具有概率边缘权重 / S 的每个子树。但是，在重新平衡树时更新权重会很烦人。

    运行时间：O(N)
    空间：O(N)

一种可能的随机方法：

在舞台上随机选择一个点。如果您可以绘制一个或多个包含该点的矩形（不仅仅是一个以该点为左下角的矩形），则返回一个包含该点的随机定位矩形。可以通过一些细微的差别来定位矩形而不带偏见，但我会把这个留给你。

在最坏的情况下，有一个空间正好足以容纳我们的矩形，而舞台的其余部分则被填满。所以这种方法成功的概率 > 1/N，或者失败的概率 < 1-1/N。重复N次。我们现在失败的概率 < (1-1/N)^N < 1/e。失败是指我们的矩形有一个空间，但我们没有找到它。成功意味着我们找到了一个空间（如果存在的话）。为了获得合理的成功概率，我们重复 Nlog(N) 次以获得 1/N 的失败概率，或 N² 次以获得 1/e^N 的失败概率。

总结：尝试随机点直到我们找到一个空间，在 NlogN（或 N²）次尝试后停止，在这种情况下，我们可以确信不存在空间。

    运行时间：O(NlogN)表示成功概率高，O(N²)表示成功概率非常高
    空间：O(1)
于 2009-01-28T17:27:42.470 回答
1

我不确定这会有多优雅，但您可以设置最大尝试次数。也许100？

当然，您可能还有一些可用空间，但无论如何您都可以触发“完成”事件。这就像补间库将对象捕捉到目标点只是因为它“足够接近”。

高温高压

于 2009-01-28T11:56:07.803 回答
1

您可以进行一项可能的检查以确定是否有足够的空间，即检查当前矩形组占用了多少面积。如果剩余的面积小于新矩形的面积，那么您可以立即放弃并退出。我不知道您可以获得哪些信息，或者矩形是否以常规模式放置，但如果是这样，您可以更改检查以查看是否明显没有足够的可用空间。

这可能不是最适合你的方法，但它是我脑海中第一时间蹦出来的！

于 2009-01-28T12:16:20.103 回答
0

假设您在尝试绘制矩形之前定义了矩形的尺寸，我认为这样的事情可能会起作用：

在舞台上为候选矩形建立一个可能的中心点网格。因此，对于 6x4 矩形，您的第一个点将位于 (3, 2)，然后是 (3 + 6 * x, 2 + 4 * y)。如果您可以在四个相邻点之间绘制一个矩形，则可能存在空间。

for (x = 0, x < stage.size / rect.width - 1, x++)
    for (y = 0, y < stage.size / rect.height - 1, y++)
        if can_draw_rectangle_at([x,y], [x+rect.width, y+rect.height])
            return true;

这并没有告诉您可以在哪里绘制它（尽管应该可以构建可能的绘图区域的列表），只是您可以。

于 2009-01-28T13:10:24.407 回答
0

我认为用你所拥有的唯一有效的方法是维护一个开放位置的 2D 布尔数组。具有足够大小的数组，以使绘图位置仍然显得随机。

当您绘制一个新矩形时，将数组中相应的矩形块归零。然后检查空闲区域是恒定的^H^H^H^H^H^H^H时间。糟糕，这意味着查找是 O(nm) 时间，其中 n 是长度，m 是宽度。必须有一个基于范围的解决方案，啊。

Edit2：显然答案就在这里，但在我看来，这在 Actionscript 上实现可能有点多，特别是如果您不热衷于几何图形。

于 2009-01-28T14:35:17.717 回答
0

这是我要使用的算法

  1. 放下N个随机点，其中N是你想要的矩形数量
  2. 迭代地增加在每个点 N 创建的矩形的尺寸，直到它们接触另一个矩形。

如果您想要最小允许的矩形大小，您可以限制初始点的放置方式。

如果您希望所有空间都被矩形覆盖，则可以将随机点逐步添加到剩余的“空闲”空间，直到没有区域未被覆盖。

于 2009-01-28T18:27:16.687 回答