algorithm - 具有给定纵横比的树形图

Question

我想创建一个TreeMap，使用图片来填充treemap矩形。我可以假设所有图片都具有相同的宽度和高度（即纵横比）。因此，我需要一种treemapping算法来创建具有给定比例的矩形，我是否能够将图片放在那里（如果需要，也许可以缩放图片）。

你能推荐一个吗？

Answer 1

一般来说，解决方案是不可能的——Albin Sunnanbo 通过反例提供了证明。假设您的边界矩形与目标矩形具有相同的纵横比，您可以通过将边界矩形缩放为正方形，在其上运行平方树图 [pdf] 算法，然后缩小尺寸，从而获得足够好的解决方案到一个矩形。由于平方树形图不能保证完美的正方形，因此您的最终矩形不会具有完美的纵横比，但实际上它可能不会过多地扭曲您的图片。

一个很好的改进是在你的图片上运行一个接缝雕刻通道，以将它们正确地放入稍微偏离纵横比的矩形中；例如，如果您使用它来组装拼贴画，您应该从中获得视觉上令人愉悦的结果。