如何隨機地放置以最小的重疊和好的分散

Question

矩形我想的矩形的任意數量置於一個固定的大小父使得它們是：

1. 隨機放置
隨機
2. 旋轉到內一個給度範圍
3. 奈斯利分散圍繞中心點（不是所有的結塊成一個角部）
4. 不重疊，除非必要，由於缺乏空間
5. 隨着最小重疊時，它的NE子宮外

爲了幫助您查看問題，我想將圖像分散到窗口中供用戶選擇。

谷歌搜索導致我做了各種包裝等算法，但沒有真正解決我的要求。

有沒有人有任何好點子？

Answer 1

它不應該比要複雜得多：在隨機位置隨機旋轉

1. 將新矩形。只需要使用三個隨機值（x，y，r）就可以了，除非你想要隨機大小（在這種情況下，你需要w和h）。這不應該給任何角落聚集（通過隨機是隨機的）。
2. 對於已經放置的每個矩形，檢查碰撞。 Here's one way.同時檢查窗口邊緣是否有碰撞（如果你不希望事物超出屏幕）;在邊界周圍放置四個虛擬矩形可能是一種便宜的方法。
3. 如果存在任何碰撞，則有兩種選擇：將新的矩形移動到新的隨機位置，或將新的矩形和阻擋矩形移開，直到它們不再接觸。兩者都有好處 - 只有在頁面真正滿的時候，才能找到適合的地方，而僅僅移動新的更快更容易;移動兩者幾乎肯定會成功，但需要更長的時間，並可能導致連鎖反應碰撞，這些碰撞都必須遞歸地進行排序。

在任何情況下，您都會嘗試保持較小的矩形數，因爲比較次數可能會很快變大。使用短路（例如「如果他們在屏幕中間，那麼不要擔心仔細觀察」）可能有幫助，但不能保證。

編輯：好的，所以要求＃5。很有可能，添加新矩形的push-both-rectangles-until-them-no-longer-collide-recursively方法最終會成爲最簡單的方法 - 只需在幾千次迭代後切斷循環，一切都將試圖儘可能遠離其他所有事物，留下最小的重疊。或者，讓方法在一個單獨的線程中運行，這樣當用戶添加更多內容時，用戶可以看到它們擴展（也可以阻止它看起來像在鎖定時一樣），一旦沒有矩形移動超過X個單元就停止迭代。

Answer 2

我不明白要求2.你是說矩形本身圍繞矩形中心點旋轉，或者矩形只覆蓋圍繞所有矩形中心點的360度圓的一部分。

我不確定隨機是要走的路。

只需除以360度所需的矩形的數目。這是在繪製每個矩形時抵消每個矩形的度數。這應包括要求3，4，5

Answer 3

這個怎麼樣？考慮你必須將矩形放置成帶狀的帶電粒子，這些粒子彼此排斥並且也被容器的壁排斥。你可以開始通過（隨機）分發他們（和給予他們隨機角度）在容器中，然後運行仿真其中，響應作用於其上（角度將根據這些力量的轉動力矩改變強制每個「粒子」動作）。當你在公差範圍內進行配置時停止。

你可以通過處理每個矩形爲橢圓形，其可以通過將每個橢圓作爲已經經歷縮放和旋轉的圓被進一步簡化簡化計算。