需要算法来计算矩形的大小

-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

需要算法来计算矩形的大小

回答

相关问题