如何找到矩形的区域被覆盖另一个矩形 [英] how to find area of rectangle which is covering another rectangle

问题描述

我有一点名单[XMIN，YMIN，XMAX，YMAX]每个作为展示用黑点

I have a list of point [xmin,ymin,xmax,ymax] for each as show by black point

如何找到它们正在覆盖另一个矩形和多少被覆盖.the算法应该是有效的矩形。一个解决办法是检查每一个矩形相互长方形这将需要哦的时间复杂度（N ^ 2），但我需要高效的算法。

How to find which are the rectangles that are being covered by another rectangle and how much it is being covered .the algorithm should be efficient. one solution would be to check every rectangle with each other rectangle which would take a time complexity of O(n^2) , but I need efficient algorithm.

请注意，有很多这样的长方形的秀形象。红色应该去除，绿一片被检测应保持。

Note that there are many such rectangle as show in image.the red one should be detected for removal and green one should be kept.

输入为n的矩形 输出覆盖和矩形ID其所覆盖的区域。 这将是preferable给予一定的算法和解释。

Input is n rectangle output is area of covering and rectangle id to which it cover . It would be preferable to give some algorithm and explanation.

推荐答案

说矩形的名单→，说最后的名单，只有拥有绿色的是< codeG 。该矩形可以添加一个又一个G之前每次添加，它是在核对清单了。它是否与其中之一相重叠，比较它们的大小（面积）。如果是大于一个在列表中，替换它，否则它不会被添加到。

Say the list of rectangles is L and say the final list that only has the green ones is G. The rectangles can be added one after another to G. Before each add, it is checked against the list already in G. If it overlaps with one of them, compare their sizes(areas). If it is bigger than the one in the list, replaces it, otherwise it is not added to G.

将永远不会有两个矩形重叠（即算法不变）。这样，您只核对那些候选人的最终名单结束了。

G will never have two rectangles that overlap (that is the algorithm invariant). This way you only check against those that are candidates for ending up in the final list.

这是肯定比为O（n ^ 2）更好，如果矩形具有随机重叠。但最坏的情况下仍然为O（n ^ 2） - 当没有输入矩形的→重叠。在这种情况下，每个重复检查是一个O（n）的操作。

This is definitely better than O(n^2), if the rectangles have random overlaps. But the worst case is still O(n^2) - when none of the input rectangles in L overlap. In that case each overlap check is a O(n) operation.

但重叠检查可以被优化。通过保持一个点的排序列表，基于X和Y上，重叠检查可以只对那些最接近矩形的XMIN，XMAX，YMIN与YMAX来完成。这个我觉得是有点棘手，尤其当新的矩形只是部分重叠，或者如果它有多个的重叠。但它可以做到的。

But the overlap check can be optimized. By maintaining a sorted list of points, based on both X and Y, the overlap check can be done just against the ones that are closest to the rectangle's xmin, xmax, ymin and ymax. This I think is a bit tricky, esp when the new rectangle only partially overlaps or if it overlaps with multiple ones. But it can be done.

在任何情况下，该重叠检查可以加快到某种程度，它不必须是对在所有的矩形。我无法量化，但做正确，我相信，它可以在O（nlogn）来完成。

In any case, the overlap check can be sped up to some extent that it doesn't have to be against all the rectangles in G. I couldn't quantify it, but done correctly, I believe, it can be done in O(nlogn).

这篇关于如何找到矩形的区域被覆盖另一个矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！