如何找到覆盖另一个矩形的矩形区域
我有一个点[xmin，ymin，xmax，ymax]的列表，如黑点所示
如何找到哪个矩形被另一个矩形覆盖，以及它被覆盖多少。算法应该是有效的。 一种解决方案是检查每个矩形与每个矩形的时间复杂度为O（n ^ 2），但我需要高效的算法。
请注意，图像中显示了许多这样的矩形，红色的应该被检测出去，绿色应该被保留。
输入是n矩形输出是覆盖区域和它覆盖的矩形ID。 最好给出一些算法和解释。
假设矩形列表是L并且说只有绿色列表的最终列表是G 矩形可以一个接一个添加到G.在每次添加之前，将对照已经在G中的列表进行检查。 如果它与其中一个重叠，则比较它们的大小（区域）。 如果它大于列表中的那个，则替换它，否则它不会被添加到G 。
G永远不会有两个重叠的矩形（即算法不变）。 这样你只能检查那些候选人在最终名单中结束。
如果矩形具有随机重叠，这肯定比O（n ^ 2）好。 但最坏的情况仍然是O（n ^ 2） - 当L中的输入矩形都没有重叠时。 在这种情况下，每个重叠检查都是O（n）操作。
但重叠检查可以优化。 通过维护一个基于X和Y的排序列表，可以对最接近矩形xmin，xmax，ymin和ymax的点进行重叠检查。 这个我觉得有点棘手，尤其是当新的矩形只有部分重叠或者它与多个重叠时。 但这是可以完成的。
在任何情况下，重叠检查都可以在一定程度上加快，不必违背G中的所有矩形。 我无法对它进行量化，但是，我相信它可以在O（nlogn）中完成。
这不是一个答案，只是一个提示：
您可能会发现四叉树空间细分数据结构很有用。 如果布局良好，那么可以显着减少碰撞检测次数。
这种结构被旧的街机视频游戏机中的各种2D Sprite引擎所使用，并且在图形中也有其他应用。
你的问题看起来就像搜索一个高效的2D精灵引擎。 在视频游戏中，点集经常变化（精灵在整个地方飞行），所以算法必须快速。
如果你的任务可以减少到这个问题，那么你应该能够找到很多不同语言的现有代码
链接地址: http://www.djcxy.com/p/63235.html上一篇: how to find area of rectangle which is covering another rectangle