问题描述
我有一组的 N 的正数，和尺寸的长方形的 X 和是的，我需要分成的 ñ的小矩形，使得：
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:
- 每个较小矩形的表面面积成正比对应的号码，在给定的
- 在大矩形的所有空间被占用，还有更小的矩形之间没有多余的空间，
- 在每个小矩形的形状应尽量接近正方形，可行
- 执行时间应该是相当小
我需要在这个方向。你知道这种在网络上描述的算法？你有什么想法（伪code是罚款）？
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)?
感谢。
推荐答案
你描述像树形的声音是什么：
What you describe sounds like a treemap:
树图显示层次结构（树状结构）的数据为一组嵌套的矩形。树的每个分支都有一个矩形，然后将其与更小的矩形重新presenting支行瓷砖。叶节点的矩形的面积成比例的数据指定维度
这是维基百科页面链接到本·施奈德曼，这给出了一个很好的页面概述和链接的Java实现：
That Wikipedia page links to a page by Ben Shneiderman, which gives a nice overview and links to Java implementations:
然后同时在教师休息室纳闷这一点，我有啊哈！分割屏幕分成矩形交替水平和垂直方向为向下遍历的经验水平。这个递归算法似乎有吸引力，但我花了几天来说服自己，它会一直工作，并写了六线算法。
维基百科也正方树图由马克Bruls，基斯Huizing和Jarke J.面包车Wijk （PDF）是presents一种可能的算法：
Wikipedia also to "Squarified Treemaps" by Mark Bruls, Kees Huizing and Jarke J. van Wijk (PDF) that presents one possible algorithm:
我们怎样才能tesselate矩形递归成矩形，使得它们的纵横比（如最大（高/宽，宽/高））的方法1尽可能接近？所有可能tesselations的数量是非常大的。这个问题落在了NP难问题的范畴。然而，对于我们的应用，我们不需要的最优解，良好的解决方案 可在很短的时间来计算是必需的。
您没有提到的问题的任何递归，所以你的情况可能是树形图的只是一个级别;但由于算法的时间在一个水平上工作，这应该是没有问题的。
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.
这篇关于分区一个矩形接近正方形给定的区域的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！