actionscript-3 - 在舞台上寻找空闲区域

Question

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

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

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，尝试另一个随机位置。

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

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

Answer 1

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

一种可能的确定性方法:

当您在空舞台上绘制一个矩形时，这会将舞台分成最多 4 个区域，以适合您的下一个矩形。当你绘制下一个矩形时，一个或两个区域被分成最多 4 个子区域(每个)可以适合一个矩形，等等。你永远不会创建超过 N 个区域，其中 S 是你的舞台面积，并且A 是最小矩形的面积。保留一个区域列表(未排序很好)，每个区域由其四个角点表示，每个区域都标有其面积，并使用按面积加权 reservoir sampling水库大小为 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。失败是指我们的矩形有空间，但我们没有找到它。成功是指我们找到了一个空间(如果存在的话)。为了获得合理的成功概率，我们对 1/N 的失败概率重复 Nlog(N) 次，或者对 1/e^N 的失败概率重复 N² 次。

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

运行时间:O(NlogN) 成功概率高， O(N²) 非常高成功概率
空间:O(1)