0

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

4

1 回答 1

2

如果我这样做，我可能会通过使用函数测试问题对于给定的 N、R 和 rectangle_scale 是否可解决的二分搜索来完成。

测试功能可能应该是这样的：

测试函数（R，rectangle_scale）

  1. 沿直径拟合尽可能多的矩形
  2. 尽可能多地安装在与直径顶部的矩形相邻的直径之上（例如 2*R/rectangle_scale*side 或类似的东西）
  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;
   }
}

理想情况下，您当然希望以数学方式执行此操作。如果近似值适合您，您可以通过区域进行。近似值是 (rectangle_area*scale*N = pi*R^2) => scale = scale = pi*R^2 / N / rectangle_area。

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

希望这可以帮助！

于 2011-09-09T19:43:52.270 回答