how to find area of rectangle which is covering another rectangle
I have a list of point [xmin,ymin,xmax,ymax] for each as show by black point
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.
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.
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.
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.
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.
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).
This is not an answer, merely a hint:
You may find the Quadtree space subdivision data structure useful. If layed out well then you can reduce the number of collision detections significantly.
This kind of structure was used by various 2D sprite engines in old arcade video game machines and it has also other applications in graphics.
Your problem looks exactly like search for an efficient 2D sprite engine. In the video games the set of points changes frequently (sprites flying all over the place) so the algorithms had to be fast.
If your task can be reduced to this problem then you should be able to find lots of existing code in different languages
链接地址: http://www.djcxy.com/p/63236.html上一篇: 在网格中查找位于边界并包含点的最大矩形
下一篇: 如何找到覆盖另一个矩形的矩形区域