将固定大小的矩形包装在具有最大“缩放”的圆内。

发布于 2024-12-03 19:44:43 字数 89 浏览 5 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

维持三分热 2024-12-10 19:44:43

如果我要这样做，我可能会使用一个函数通过二分搜索来测试问题对于给定的 N、R 和矩形比例是否可解决。

测试函数可能应该是这样的：

testfunction(R,fragment_scale)

沿着直径尽可能多地拟合矩形
在与直径顶部的矩形相邻的直径上方尽可能多地拟合（例如 2*R/rectangle_scale*side ）或类似的东西）
重复（放置在您刚刚放置的矩形上方。这样做直到没有更多的矩形可以容纳为止
返回适合的矩形的数量

然后二分搜索将是标准的：

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

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

希望这有帮助！

If I would do this I would probably do it through a binary search using a function testing whether the problem is solvable for a given N, R and rectangle_scale.

The test function should probably be something like:

testfunction(R, rectangle_scale)

Fit as many rectangle as possible along the diameter
Fit as many as possible above the diameter adjacent to the rectangle on top of the diameter (e.g. 2*R/rectangle_scale*side) or something like that)
Repeat (placing above the rectangles you just place. Do this until no more rectangles can be fit
return the number of rectangles that fit

The binary search would then be standard:

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;
   }
}

Ideally you would of course want to do this mathematically. If an approximation is fine for you, you could maybe do it through areas. A proximation would be (rectangle_area*scale*N = pi*R^2) => scale = scale = pi*R^2 / N / rectangle_area.

However, if you need accuracy I would only use the area approximation for setting the initial lower/upper bounds in an intelligent way.

Hope this helps!

回复收藏 0 原文

~没有更多了~