在最大“缩放”的圆圈内包装固定大小的矩形

Question

我需要一种算法将一组N个矩形放置在半径为R的圆内，以便它们被放大到最大可能大小超过圆圈的边界。我仍然在努力，所以如果我找到答案，我会在这里发布...

Answer 1

如果我会这样做，我可能会通过二进制搜索使用函数测试问题是否可以解决给定的N，R和rectangle_scale。

测试功能也许应该是这样的：

testfunction（R，rectangle_scale）

1. 适合尽可能多的矩形尽可能沿直径
2. 适合尽可能多的相邻的直径以上到直径顶部的矩形（例如2 * R/rectangle_scale *侧）或类似的东西）
3. 重复（放置在刚刚放置的矩形上面，直到没有更多的矩形可以适合为止
4. 返回适合矩形数

二进制搜索将被标准：

while(upperbound-lowerbound > limit) { 
    new_bound = (upperbound+lowerbound)/2; 
    num_fit = testfunction(N, R, new_bound); 
    if(num_fit > N) { 
     upperbound = new_bound; 
    } else { 
     lowerbound = new_bound; 
    } 
} 

理想情况下，你当然会想数学做到这一点。如果一个近似值对你来说很好，你可以通过区域来完成。近似值可以是（矩形区域*比例* N = pi * R^2）=> scale = scale = pi * R^2/N/rectangle_area。

但是，如果您需要准确性，我将只使用面积近似值以智能方式设置初始下限/上限。

希望这会有所帮助！