寻找舞台上的空闲区域

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

我想过尝试的随机位置，确认其是否是免费的

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

问题是，如果没有空闲空间，我会被卡在永久的随机位置上。

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

来源

2009-01-28 Carlo

让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。我们的失败意味着我们的矩形有一个空间，但我们没有找到它。通过成功我们的意思是我们找到了一个空间，如果存在的话为了获得合理的成功概率，我们重复Nlog（N）次，1/N失败概率，或N/2次，1/e^N失败概率。

摘要：尝试随机点，直到找到空格，在NlogN（或N²）尝试后停止，在这种情况下，我们可以确信没有空间存在。

运行：O（NlogN）

O（N²）

空间：O（1）

来源

2009-01-28 17:27:42 Imran

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

确定您可能仍有一些可用空间，但您仍然可以触发“完成”事件。这就好像补间库将对象捕捉到目标点时，只是因为它“足够接近”。

HTH

来源

2009-01-28 11:56:07

一个可能的检查，你可以做，以确定是否有足够的空间，将检查多少面积的电流设定rectangels被占用。如果剩余区域的数量少于新矩形的面积，那么您可以立即放弃并纾困。我不知道你有什么信息可用，或者矩形是否按照常规模式放置，但如果是这样的话，你可以改变支票来查看是否显然没有足够的可用空间。

这对你来说可能不是最合适的方法，但它是第一件突然出现在我脑海中的东西！

来源

2009-01-28 12:16:20 chillysapien

假设你想绘制之前定义的矩形的尺寸，我觉得这样的事情可能工作：

在舞台上建立的可能中心点网格候选矩形。所以对于一个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-28 13:10:24

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

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

来源

2009-01-28 13:37:08

我没有Karma对您选择的答案发表评论，但您选择作为正确答案的确定性版本不起作用，因为它不允许您放置跨越多个区域的矩形。你需要首先应用上面提到的转换。 – 2009-01-28 23:54:22

我认为唯一有效的方法是用维护一个开放位置的二维布尔数组来实现这一点。拥有足够大小的数组，以便绘图位置仍然显示为随机。

当您绘制一个新的矩形时，将相应的矩形片段归零。然后检查一个空闲区域是不变的。糟糕，这意味着查找是O（nm）时间，其中n是长度，m是宽度。必须有一个基于范围的解决方案，argh。

Edit2：显然答案是here但在我看来这可能是一个很大的Actionscript实现，特别是如果你不热衷于几何。

来源

2009-01-28 14:35:17 Overflown

这里的算法我倒是用

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

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

如果你想要所有用矩形覆盖的空间，你可以随机增加随机点到剩余的“空闲”空间，直到没有剩下的区域被发现。

来源

2009-01-28 18:27:16 Ryan

寻找舞台上的空闲区域

回答

相关问题