需要算法來計算矩形的大小

-1

我得到一個邏輯謎語，我需要一個有效的算法來解決它。需要算法來計算矩形的大小

我有一個大小爲w * h（寬*高）的大矩形（盒子）。

我也有其他矩形不是大小，但有固定的比例。

什麼是最快的方式來獲得X，將讓每個X矩形的最大尺寸在框內（大矩形）？

實施例：

的框矩形大小爲150 * 50（寬×高）和i具有25個小矩形。

小矩形的固定比例爲3（如果height = 5，則width = 5 * 3 = 15）。讓我們調用矩形x的高度。

我想找到那個最大的X，它可以讓我把所有的矩形插入大矩形（進入框）。

（小矩形將被放置在行和列，例如5列和5行由比例和最大高度）

沒有人知道一個有效的算法來解決這個？

來源

2012-02-14 user436862

我試圖採取小矩形的最大尺寸和最小值，並計算需要多少行和列，然後測量作爲矢量的最大尺寸。這不是一個好的解決方案。 – user436862 2012-02-14 17:53:24

呃什麼？

難道只是（w * h）/ 75？

是的，括號不需要......但是不是你想要的嗎？或者我在這裏丟失了什麼？

其中w和h是大矩形或父矩形的尺寸。而75是3 * 25。

來源

2012-02-14 18:00:34 bharal

在這個例子中，我不知道小矩形的大小。這是我想找到的。我只知道高度和寬度之間的比例。在真實情況下，我知道大矩形的大小，小矩形的數量以及高度和寬度的比例。 – user436862 2012-02-14 20:10:29

我試圖用經驗來解決這個問題（使用backtracking解決）而不是分析，即找到所有可能性*（我將解釋*）。實質上，我們希望將每個矩形以小到矩形的最大尺寸（最大尺寸可以通過在碰到其鄰居的起點或增長到容器主矩形之前最大的矩形定義）來定義。這意味着如果我們試圖將每一個矩形放在其可能的大小上，那麼其中一個解決方案就是最好的解決方案。另外請注意，這是真正的一維問題，因爲矩形的高度和寬度受比率的限制;設置一個隱式設置另一個。

* - 當我說了所有的可能性，我真的意味着最合理的可能性。由於我們處於浮點空間，因此我們無法測試所有可能性。我們可以測試更精細，更精細的測試，但無法測試所有尺寸。由於這個原因，我們定義了一個步長來遍歷我們將要嘗試的rects的大小。

const float STEP_SIZE = 0.0001; 
float fLastTotalSize = 0; 

int main() 
{ 
    PlaceRect(myRects.begin(), myRects.end()); 
} 

void PlaceRect(Iterator currentRect, Iterator end) 
{ 
    if (currentRect == end) 
    { 
    return; 
    } 

    float fRectMaxSize = CalculateMaxPossibleRectSize(*currentRect); 

    // find the number of steps it will take to iterate from the smallest 
    // rect size to the largest 
    int nSteps = fRectMaxSize/STEP_SIZE; 

    for(int i = 0; i < nSteps; ++i) 
    { 
    // based on the step index scale the rect size 
    float fCurrentRectTestSize = i*STEP_SIZE; 

    currentRect->SetSize(fCurrentRectTestSize); 

    float fTotalSize = CalculateTotalSizesOfAllRects(); 
    if (fTotalSize > fLastTotalSize) 
    { 
     fLastTotalSize = fTotalSize; 
     SaveRectConfiguration(); 
    } 

    // Continue placing the rest of the rects assuming the size 
    // we just set for the current rect 
    PlaceRect(currentRect + 1, end); 

    // Once we return we can now reset the current rect size to 
    // something else and continue testing possibilities 
    } 
}

根據步長，這可能很長一段時間運行矩形的數量，但會發現你的經驗解決方案。

來源

2012-02-14 18:35:14 Unknown1987

需要算法來計算矩形的大小

回答

相關問題