尋找舞臺上的空閒區域

我在舞臺上的隨機位置繪製矩形，我不希望它們重疊。因此，對於每個矩形，我需要找到一個空白區域來放置它。尋找舞臺上的空閒區域

我想過嘗試的隨機位置，確認其是否是免費的

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

尋找舞臺上的空閒區域

回答

相關問題