Mar*_*mic 7 algorithm rectangles
我有一组N个正数,以及一个尺寸为X和Y的矩形,我需要将其划分为N个较小的矩形,这样:
我需要这方面的指示.你知道网上描述的这种算法吗？你有什么想法(伪代码很好)？
谢谢.
你描述的内容听起来像树图:
树图将分层(树形结构)数据显示为一组嵌套矩形.树的每个分支都有一个矩形,然后用表示子分支的较小矩形平铺.叶节点的矩形具有与数据上的指定维度成比例的面积.
该维基百科页面链接到Ben Shneiderman的页面,该页面提供了一个很好的概述和Java实现的链接:
然后在教师休息室里对此感到困惑的时候,我有了Aha!当你向下穿过水平时,将屏幕分成水平和垂直方向交替的矩形的经验.这种递归算法看起来很有吸引力,但是我花了几天时间才能说服自己它总能工作并编写一个六行算法.
维基百科还提供了Mark Bruls,Kees Huizing和Jarke J. van Wijk(PDF)的"Squarified Treemaps",它提出了一种可能的算法:
我们如何将矩形递归地镶嵌成矩形,使得它们的纵横比(例如max(高度/宽度,宽度/高度))尽可能接近1？所有可能的细分都非常多.这个问题属于NP难问题.但是,对于我们的应用,我们不需要最佳解决方案,需要一个可以在短时间内计算的好解决方案.
您没有在问题中提及任何递归,因此您的情况可能只是树形图的一个级别; 但由于算法一次只能在一个级别上工作,这应该没问题.