查找具有可以容纳另一个矩形的最小区域的矩形
假设我有一组矩形（维度不同或相同）。
- 任务是从集合中查找（并删除）大于或等于给定矩形的矩形
- 它也应该是集合中可以包含给定矩形的最小矩形
这很容易通过线性搜索/更新在O(n)时间内解决，但是有可能获得更好的结果吗？我认为O(log n)是最佳值。Insert和removal也必须比O(n)快，这样在我的例子中才有用。
是否可以通过不找到最佳矩形来制定任何快捷方式，而是将第二个限制放宽为：“它也应该是可以包含给定矩形的最小矩形之一”-
我在考虑使用Z阶曲线（宽度/高度）并用作一维索引并将其与树结合起来。这可行吗？还是会有太多浪费？
另一种方法是使用一个轴使用树，然后线性地测试另一个。
有人做过类似的事情，可以分享他们的经验吗？
共有1个答案
以下是一个尚未完全阐述的想法：
也许你可以使用一个四叉树，它有两个元组值(高度和宽度),每个值代表一个矩形。
一个节点（w，h）具有4个子节点：
-
< li > <代码>(
当您在一个< code>(w，h) rect节点处向下寻找< code>(w2，h2) rect的容器时，现在有4种不同的情况:
- <代码>w2
你必须下降到所有可能的分支，这仍然比O（n）好。
插入是O（log n）。还不确定删除和平衡。但我几乎可以肯定也有解决方案。
-
我有一个点[xmin，ymin，xmax，ymax]的列表，每个点都按黑点显示 请注意，有许多这样的矩形，如图像所示。红色的应检测删除，绿色的应保留。 输入是 n 矩形 输出是覆盖区域和它覆盖的矩形 id 。最好给出一些算法和解释。
-
这是一个面试问题。 我们被赋予各种矩形的尺寸，我们必须找出可以包围所有矩形的矩形面积（最小值）？矩形也可以旋转。 在将矩形拟合到最小可能区域之前，我曾问过一个类似的问题。 上述方法考虑了所有可能性、旋转，并在所有布局情况下确定了所有此类可能性的最小值<我们不能先求矩形面积之和，然后再求最大长度、最大宽度吗？
-
给定两个矩形的边的长度，我必须编写代码来检查第一个矩形是否可以被第二个矩形完全覆盖。只能旋转第二个矩形，看看它是否可以覆盖第一个矩形。 A和B是第一个矩形的边的长度，我们要覆盖的那个，C和D是第二个矩形的边的长度，它将覆盖第一个。 我尝试了两种代码，但仍然不起作用。第一个是天真的解决方案，但我不知道它是否正确。 然后我用我的数学技巧找出第二个矩形（和）的边应该
-
在上面的图片中，我展示了两个矩形 矩形1，其x可以从-900到13700不等，Y可以从-600到6458 矩形2，其坐标X可以从0到3000变化，而y可以从0到2000变化 同样:矩形2的起点位于左上角位置(0，0)，而矩形1的起点位于左上角位置(宽度/2，高度/2)。 我需要做的是：使用缩放或平移将矩形1的点转换为矩形2的点。 那么，为了将矩形1的坐标转换为矩形2的坐标，< code>x和< c
-
我需要能够计算出矩形2的大小 为了说明我的问题，这里有一个图表： 我知道矩形的和 1 我知道的纵横比以及始终大于矩形1的最小和 我知道的起源，它始终是矩形1的中心 我知道弧度旋转角度 矩形 1 必须始终完全位于矩形 2 内 给定上述变量，我需要计算矩形2的最小尺寸，同时保持其纵横比和旋转原点。 这个优秀的函数计算旋转外矩形中最大的可能矩形。 计算旋转矩形中的最大矩形 我试图用它作为基础来实现我所要
-
问题内容： 创建哪一个将坐标从一个矩形映射到另一个矩形（给出浮动/双矩形）的最简单方法是什么？ 更新1 矩形可以完全不同。例如[（0,0）-（1,1）]和[（150，-14）-（-1000，-14.1）]。并且转换应该统一转换。例如，矩形角应一一变换。例如，坐标（0,0）应该变成（150，-14）。 更新2 我需要对象，而不仅仅是计算。因为我想将其应用于对象。我也想以一些简单转换的串联形式。 更新