2013-03-17 38 views
0

我有一個大矩形(面向軸)包含很多小矩形(具有相同的方向的父和具有82x176像素的固定大小)。隨機矩形放置與最小的重疊和良好的分散

現在我有一個小的矩形是外面的,我必須把它放在大矩形內,以便它: - 隨機放置; - 由於缺乏空間(在這種情況下,最小重疊),除非必要,否則不與其他小矩形重疊。

該算法將在我的代碼執行過程中多次使用,還需要包含一個很好的分佈,以便小矩形將很好地分散在大矩形的中心周圍,而不是全部聚集到一個角落。

使用谷歌搜索,我發現了幾個關於矩形打包,最大空矩形,隨機分佈的算法......但沒有什麼真正解決我的需求,也沒有顯示出好的代碼實現。

有沒有人有任何好主意(如果可能,代碼或僞代碼是否更好,因爲通常當我看到數學公式時,我的大腦崩潰)?

+0

小直徑座標任意或82 * n,176 * m? – MBo

+0

他們必須是任意的。 –

+0

IDK肯定,但我會使用你剛纔問的[空矩形](http://stackoverflow.com/questions/15449048/largest-empty-rectangle-within-a-rectangle),並從最小的距離,只要從任何地方開始,並將小Rect放在那裏的任何地方,如果它適合。無論如何,你必須做最大的空Rect問題,以實現最小的重疊。 – SGM1

回答

2

你的問題太模糊了,任何人都難以發佈解決方案;這不是一個解決方案。相反,它是在如何攻擊這種問題的教訓。通過閱讀這篇開始:

http://en.wikipedia.org/wiki/How_to_Solve_It

雖然你在它也許拿起書的副本。

由於波利亞明智地說

如果不能解決問題,再有就是你可以解決一個簡單的問題:找到它。

這裏是你的問題的一個更容易的版本:

我有一條直線。在這一行我有一個線段的集合。集合中每個線段的起點和終點都在0和某個參數n之間(包含)。某些線段可能會相互重疊。

給定新線段的長度小於n,隨機放置新線段,使其起點和終點都在0和n之間,並且它不會「重疊」集合中的任何線段。如果不能這樣做,則計算新線段的開始和結束座標,以使其重疊量最小。

你能給我寫個解決方案嗎在C#中的問題?相信我,如果你不能解決更簡單的問題,那麼你永遠不會解決矩形版本。

如果不能解決問題再次更容易直到你可以解決這個問題。如果n不超過200,該怎麼辦?如果現有部分的集合只有零個,一個或兩個元素?如果新的細分市場的長度總是三?如果你擺脫了隨機性的要求會怎麼樣?如果你擺脫了最小化問題呢?等等。 繼續解決問題,直到解決問題。一旦你解決了一個更簡單的問題,試着將它調整成解決更大問題的解決方案。通過練習解決較簡單的問題,您將深入瞭解解決較難的問題。

0

根據您的需要,可能已經存在。例如,如果您正在開發Web應用程序,那麼請查看jQuery Masonry:http://masonry.desandro.com/demos/basic-multi-column.html

如果該代碼滿足您的需求,但您沒有在做一個Web應用程序,那麼也許您可以檢查源代碼以獲取所需內容。

希望這會有所幫助。