将一个矩形划分为给定区域的近似正方形
我有一组 N 个正数，以及一个尺寸为 X 和 Y 的矩形，我需要将其划分为 N em> 较小的矩形，使得：
- 每个较小矩形的表面积与其在给定集合中的相应数字成正比
- 大矩形的所有空间都被占据，并且较小矩形之间没有剩余空间
- 每个小矩形的形状应接近正方形如果可行，
- 执行时间应该相当短，
我需要这方面的指示。您知道网络上描述的这种算法吗？你有什么想法吗（伪代码就可以）？
谢谢。
I have a set of N positive numbers, and a rectangle of dimensions X and Y that I need to partition into N smaller rectangles such that:
- the surface area of each smaller rectangle is proportional to its corresponding number in the given set
- all space of big rectangle is occupied and there is no leftover space between smaller rectangles
- each small rectangle should be shaped as close to square as feasible
- the execution time should be reasonably small
I need directions on this. Do you know of such an algorithm described on the web? Do you have any ideas (pseudo-code is fine)?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您所描述的听起来像树形图：
该维基百科页面链接到 Ben Shneiderman 的页面，其中给出一个很好的概述和 Java 实现的链接：
维基百科还有 Mark Bruls、Kees Huizing 和 Jarke J. van Wijk 的“方形树状图”< /a> (PDF) 提出了一种可能的算法：
您在问题中没有提到任何递归，因此您的情况可能只是树状图的一层；但由于算法一次只能在一个级别上工作，所以这应该没有问题。
What you describe sounds like a treemap:
That Wikipedia page links to a page by Ben Shneiderman, which gives a nice overview and links to Java implementations:
Wikipedia also to "Squarified Treemaps" by Mark Bruls, Kees Huizing and Jarke J. van Wijk (PDF) that presents one possible algorithm:
You do not mention any recursion in the question, so your situation might be just one level of the treemap; but since the algorithms work on one level at a time, this should be no problem.
我一直在做类似的事情。我优先考虑简单性而不是获得尽可能相似的纵横比。这（理论上）应该有效。在纸上测试了 1 到 10 之间的某些 N 值。N
= 要创建的矩形总数，
Q = 最大（宽度，高度）/最小（宽度，高度），
R = N / Q
如果 Q > N/2，将矩形沿其最长边分成 N 部分。
如果 Q <= N/2，则沿矩形的最短边将矩形分割为 R（圆角整数）部分。
然后沿着其最短边将子矩形分割为 N/R（向下舍入整数）部分。
从下一个子矩形除法的结果中减去向下舍入的值。对所有子矩形重复此操作，或者直到创建所需数量的矩形。
I have been working on something similar. I'm prioritizing simplicity over getting as similar aspect ratios as possible. This should (in theory) work. Tested it on paper for some values of N between 1 and 10.
N = total number of rects to create,
Q = max(width, height) / min(width, height),
R = N / Q
If Q > N/2, split the rect in N parts along its longest side.
If Q <= N/2, split the rect in R (rounded int) parts along its shortest side.
Then split the subrects in N/R (rounded down int) parts along its shortest side.
Subtract the rounded down value from the result of the next subrects division. Repeat for all subrects or until the required number of rects are created.