找到能够容纳另一个矩形的最小面积矩形。

Question

找到能够容纳另一个矩形的最小面积矩形。

algorithmsearchdata-structurescomputational-geometrybest-fit

4

假设我有一组矩形（具有不同或相同的尺寸）。

任务是找到（并删除）该集合中大于等于给定矩形的矩形。它还应该是能够包围给定矩形的最小矩形。

通过进行线性搜索/更新，可以很容易地在O(n)时间内解决此问题，但是否可能实现更好的结果？我会认为O(log n)是最佳的。插入和删除必须比O(n)更快才能在我的情况下使用。

可以通过不找到最优矩形而缓解第二个限制来节省任何快捷方式： “它还应该是能够包围给定矩形的最小矩形之一”-

我考虑使用Z-order curve（宽度/高度）作为一维索引，并将其与树结合使用。那样行得通吗？还是会浪费太多？

另一种方法是使用一个轴使用树，然后线性测试另一个轴。

有人做过类似的事情并分享他们的经验吗？

- eq_

你的查询矩形能否旋转90度？ - j_random_hacker

不行（因为我在追求速度，而填充矩形的数据来自第三方黑盒模块），但还是出于兴趣，你有什么优化想法吗？利用您知道一个维度始终大于（或小于）另一个维度的事实？怎么做？ - eq_

2

尝试使用优先搜索树（优先级=面积，值=宽度）。但是，仅当矩形的宽度/高度足够随机时，才会得到log(N)。 - Evgeny Kluev

假设您的所有可用矩形都旋转，使其宽度<=高度，并按宽度排序。然后旋转查询矩形，使其宽度>=高度。如果现在对可用矩形数组进行二进制搜索以查找第一个宽度(i)>=宽度(查询)的矩形i，则该矩形肯定适合查询矩形（可能在旋转其中一个矩形后）--因为高度(i)>=宽度(i)>=宽度(查询)>=高度(查询)。但是：它不一定是紧密贴合的，当然二进制搜索可能找不到解决方案！ - j_random_hacker

什么公式可以确定矩形a是否包含矩形b？看起来如果h(a) >= h(b)并且w(a) >= w(b)，那么a包含b（其中h是斜边），但我不是数学家。 - Strawberry

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Julian · Accepted Answer

这是一个尚未完全详细阐述的想法：

也许你可以使用一个四分支树，每个节点有一个2元组值（高度和宽度），分别代表一个矩形。

一个节点（w，h）有4个子节点：

- (

当你下降到一个(w，h)的矩形节点来查找你的(w2，h2)矩形的容器时，现在有4种不同的情况：

- w2 < w且h2 < h - 三个选项：(≥w，

你必须下降到所有可能的分支，这仍然比O(n)好。

插入是O(log n)。还不确定删除和平衡的情况。但我几乎可以肯定也有解决方案。