good algorithm to determine if there are overlapping in multiple rectangles
-
Suppose we represent rectangle with CRect(MFC), its edges is parallel to Ox and Oy. now we have N rectangles(N might be a very large number, for instance N = 9999). Now I want to determine whether there is(are) overlapping in these rectangles, of course I want the best algorithm. Anybody can help me?
-
Suppose we represent rectangle with CRect(MFC), its edges is parallel to Ox and Oy. now we have N rectangles(N might be a very large number, for instance N = 9999). Now I want to determine whether there is(are) overlapping in these rectangles, of course I want the best algorithm. Anybody can help me?
The Bounding Box method is fairly simple, this technique involves checking whether an object has intercepted (overlapped) an invisible square boundary that is usually placed over, and often remains relative to, a game object.
int bounding_box_collision(int b1_x, int b1_y, int b1_w, int b1_h, int b2_x, int b2_y, int b2_w, int b2_h)
{
if ((b1_x > b2_x + b2_w - 1) || // is b1 on the right side of b2?
(b1_y > b2_y + b2_h - 1) || // is b1 under b2?
(b2_x > b1_x + b1_w - 1) || // is b2 on the right side of b1?
(b2_y > b1_y + b1_h - 1)) // is b2 under b1?
{
// no collision
return 0;
}// collision return 1;}
-
Suppose we represent rectangle with CRect(MFC), its edges is parallel to Ox and Oy. now we have N rectangles(N might be a very large number, for instance N = 9999). Now I want to determine whether there is(are) overlapping in these rectangles, of course I want the best algorithm. Anybody can help me?
-
The best algorithm is up to you, of course. A naive algorithm would use a simple nested loop
for (i=0; i
Veni, vidi, vici.That is possibly a terrible idea you have 9999 Rect's as you are hoping it's singular process and you can process them on the fly. If you need to come back to them you just wasted a whole pile of time which you will have to repeat. If there is that many entries you would use the bounding box method as discussed by Supercoder and it may be better to bubble sort them or separate them into their own list at the same time while doing the test. At least then for any further processing you don't have to do the long overlap test again. So I am not convinced at all you would process them as per above it really depends what happens next.
In vino veritas