假设我有一组矩形(大小不同或相同)。
- 任务是从集合中找到(并删除)大于或等于给定矩形的矩形。
- 它还应该是集合中比可以包含给定矩形的最小矩形。
这很容易通过线性搜索/更新在O(n)时间内解决，但是有可能获得更好的结果吗?我认为O(log n)是最优的。插入和删除也必须比0 (n)快，这样在我的情况下才有用。
是否可以通过不寻找最佳矩形来创建任何捷径，而是将第二个限制放宽为:"它还应该是包含给定矩形的最小矩形之一"-
我正在考虑使用z顺序曲线(宽度/高度)，并将其用作一维索引，并将其与树相结合。这样行吗?还是会有太多的浪费?
另一种方法是使用一个轴使用树，然后线性测试另一个。
有人做过类似的事情，可以分享他们的经验吗?这是一个还没有完全阐述的想法:
也许你可以使用一个带有两个元组值(高度和宽度)的四叉树，每个元组值代表一个矩形。
一个节点(w, h)有4个子节点:
-
(<w, <h)-包含具有较小宽度和较小高度的矩形 -
(>=w, <h)-包含较大宽度和较小高度的矩形 -
(<w, >=h)-包含具有较小宽度和较大高度的矩形 -
(>=w, >=h)-包含具有较大宽度和高度的矩形
当你下降在(w, h) rect节点寻找一个容器为你的(w2, h2) rect现在有4种不同的情况:
-
w2<w and h2<h-三个选项:(>=w, <h),(<w, >=h),(>=w, >=h) -
w2>=w and h2<h-两个选项:(>=w, <h),(>=w, >=h) -
w2<w and h2>=h-两个选项:(<w, >=h),(>=w, >=h) -
w2>=w and h2>=h-一个选项:(>=w, >=h)
你必须下降到所有可能的分支，这仍然比O(n)好。
插入是O(log n)。不确定是否要删除和平衡。但我几乎可以肯定，这也是有解决办法的。