的圓內分發對象

可能重複：
How to pack squares into circles?的圓內分發對象

我有，我需要一個圓內適合一羣不同大小的矩形的一個問題。所有的矩形必須適合在圓中，不會相互重疊，也不會溢出圓。

假設矩形可以適合在圓內，如何開發算法將它們分佈在圓內？

我能想到的所有東西都是反覆隨機分配矩形，並測試條件是否滿足（蠻力）。

2012-10-04 George Reith

該問題與binpacking問題（在2d）密切相關，這是NP難題 - 沒有已知的有效解決方案來解決問題「矩形是否適合圓圈？」，更不用說 - 找到放置位置他們適合。更具體地說，它與[此問題]幾乎相同（http://stackoverflow.com/q/7342389/572670），它也是NPC。 – amit

最好的方法將嚴重依賴於包裝的緊密程度。如果你需要在一個巨大的圓圈內安裝三個小矩形，那麼你的方法就會簡單而有效。隨着圓尺寸變小和矩形數量變大，該算法必須變得更復雜以在合理的時間內解決問題。 –

正如其他人所提到的，最佳的解決方案（在說最小面積或均勻distriubtion）很可能是NP難。儘管如此，根據您的需要，還有一些很好的算法可以將不同大小的矩形包裝到其他矩形中。例如：Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites：

本文介紹了一種快速算法收拾一系列不同的寬度和高度爲單個包圍矩形的矩形的，沒有重疊和以最小化在所述的浪費的空間量的方式包圍矩形。 [...]逐步顯示算法如何到達最佳包圍矩形。

注意，在上述過程中的邊界矩形被允許改變（我也不是確信的解決方案是最佳包圍矩形）。你可以通過將它分解成離散的矩形來近似一個圓。

雖然不是您尋找的完整解決方案，但我認爲這可能是一個很好的第一步。

來源

2012-10-04 14:05:02 Hooked

這是一個經典的約束問題，蠻力是一種方法，但有其他方法可以更好地使用諸如啓發式之類的方法來幫助將算法引導到解決方案。您需要查看一些約束性編程，並且可以使用谷歌學術搜索引擎來搜索一些更好的算法。

維基百科有一個很好的概述： http://en.wikipedia.org/wiki/Packing_problem

來源

2012-10-04 13:20:36

的圓內分發對象

回答

相關問題