Thread: Checking intersection of 2 rectangles.

  1. #1
    In the Land of Diddly-Doo g4j31a5's Avatar
    Join Date
    Jul 2006
    Posts
    476

    Checking intersection of 2 rectangles.

    Hi, I'm planning to use a dirty rectangle method to blit screen with SDL. Everything seems fine except if there were intersecting sprites. So, can anybody tell me how to detect intersection between 2 rectangles (SDL_Rect)? Thanks in advance.

  2. #2
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    do you want the intersected rectangle or just to test if they actually intersect?

    if it's the latter, it's pretty easy. how would you test if a point is in a rectangle with corners top, left, bottom and right?
    Code:
    point p;
    rect r;
    
    bool bPointInRect = p.x > r.left && p.x < r.right && p.y > r.top && p.bottom;
    figure the rest out from there.
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  3. #3
    In the Land of Diddly-Doo g4j31a5's Avatar
    Join Date
    Jul 2006
    Posts
    476
    Quote Originally Posted by ChaosEngine
    do you want the intersected rectangle or just to test if they actually intersect?

    if it's the latter, it's pretty easy. how would you test if a point is in a rectangle with corners top, left, bottom and right?
    Code:
    point p;
    rect r;
    
    bool bPointInRect = p.x > r.left && p.x < r.right && p.y > r.top && p.bottom;
    figure the rest out from there.
    Yeah, I just want to check whether they're intersected or not. And for the code, that's what I had in mind too. But it seemed too costly because it means I have to check every for corners of the rectangle. Say for example, I have 100 sprites = 100 rectangles. Every loop I'll have to check 4 points' intersections to each other sprites (4 * 99). And this will be done for each rectangles (4*99*100). Is there any other optimized solution or is it the only way to do it? Thanks a lot for the reply.

  4. #4
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    The advantage of the method ChaosEngine gave you is that you will not really be doing calculations of 4 points on many of them.

    Short-circuit evaluation will guarantee that you will be doing less calculations.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  5. #5
    In the Land of Diddly-Doo g4j31a5's Avatar
    Join Date
    Jul 2006
    Posts
    476
    Quote Originally Posted by Mario F.
    The advantage of the method ChaosEngine gave you is that you will not really be doing calculations of 4 points on many of them.

    Short-circuit evaluation will guarantee that you will be doing less calculations.
    But I still have to call it for every corners of the rectangle, right? So it probably will be like this:
    Code:
    rect r,p;
    
    bool bRectInRectTopLeft = p.left > r.left && p.left < r.right && p.top > r.top &&  p.top < r.bottom;
    bool bRectInRectTopRight = p.right > r.left && p.right < r.right && p.top > r.top &&  p.top < r.bottom;
    bool bRectInRectBottomLeft = p.left > r.left && p.left < r.right && p.bottom > r.top &&  p.botom < r.bottom;
    bool bRectInRectBotomRight = p.right > r.left && p.right < r.right && p.bottom > r.top &&  p.bottom < r.bottom;
    bool bRectInRect = bRectInRectTopLeft || bRectInRectTopRight || bRectInRectBottomLeft || bRectInRectBotomRight;
    BTW, I've noticed something. For every rectangles, I don't have to make a loop to check all 100 of 'em. E.g. if I've checked rectangle A for every other rectangle's intersection, I don't have to check whether B is intersected with A in rectangle B's turn.

  6. #6
    Registered User
    Join Date
    May 2006
    Posts
    903
    This is pretty much what you want:

    Code:
    for(int i = 0; i < 100; i++) {
      for(int j = i + 1; j < 100; j++) {
        // collision detection
      }
    }

  7. #7
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465

  8. #8
    In the Land of Diddly-Doo g4j31a5's Avatar
    Join Date
    Jul 2006
    Posts
    476
    Thanks guys. I think I know what I should do now. Thanks alot.

  9. #9
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Quote Originally Posted by g4j31a5
    Say for example, I have 100 sprites = 100 rectangles. Every loop I'll have to check 4 points' intersections to each other sprites (4 * 99). And this will be done for each rectangles (4*99*100). Is there any other optimized solution or is it the only way to do it? Thanks a lot for the reply.
    There are a vast number of optimizations, but a lot depends on how specific you want to be. In general the more assumptions you are allowed to make about sprite size, sprite motion, etc. the easier it is to make a highly optimized, very specific algorithm.

    Space Invaders would be one game in which you can make a very efficient collision algorithm because:
    1. You have a maximum sprite size,
    2. The player ship has no y-axis mobility,
    3. The bullets move in one direction with one speed,
    4. The monsters likewise move all in the same pattern with the same speed.

    You could optimize the algorithm in this case by sorting the list of bullets and the list of monsters by y-value (or, more likely, you create the lists presorted). You only do collision testing on sprites that are within the narrow range of y-values that could conceivably overlap the player sprite. The motion of the bullets and monsters also can never cause the list to need resorting.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  10. #10
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Try sorting rectangles by orthogonal coordinates. If rect[X] does not intersect rect[X + 1] on the Y-axis, you can safely assume rect[X + 2] will not intersect rect[X] as well. This can speed up your algorithm by an order of magnitude if you don't expect many collisions at a time (eg. you're checking for collisions in a game every frame).

    The downside is that you need to sort the rectangles four times for each direction (decreasing X, increasing X, decreasing Y, increasing Y). The upside is that you can just use a std::map for this, which means you now get best-case O(n) amortized collision detection per frame.

    Yeah, I like to ramble. Here's (possibly slightly different from the above) pseudocode.

    Code:
    sort(rectangles by left edge, right to left) //or iterate a pre-filled ordered tree, like std::map
    
    for i = 0, i in sorted_rects.size, ++i
        for j = i + 1, j in sorted_rects.size, ++j
            if sorted_rects[i].right_edge < sorted_rects[j].left_edge
                //no collision detected in this dimension,
                //and sorted_rects[i] is not going to cross subsequent sorted_rects from j onwards
                break; //this part is what makes the algorithm fast
            else //intersect in this dimension, further checking
                if collision_check(sorted_rects[i], sorted_rects[j])
                    //collision found, deal with it
                //don't break, check the next rectangle
    //repeat for three other edges
    //remember to reverse sorting criteria, comparisons, etc etc.
    Hope this helps.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  11. #11
    In the Land of Diddly-Doo g4j31a5's Avatar
    Join Date
    Jul 2006
    Posts
    476
    Thanks. But I'm not using the rectangle intersection checking for collision detection because I didn't need it just yet. I needed it for blitting the sprites on the back buffer surface with a dirty rectangles algorithm (only blitting the sprites that changed). So rather than blitting the background and all the current sprites, I'll blit only the rectangles that changed. But if the dirty sprites intersect other clean sprites, I have to mark them dirty too so they will be updated also. But thanks anyway. I'll use a collision detection later if I develop games that need it such as Tetris or Raiden clones.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Profiler Valgrind
    By afflictedd2 in forum C++ Programming
    Replies: 4
    Last Post: 07-18-2008, 09:38 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  3. Forced moves trouble!!
    By Zishaan in forum Game Programming
    Replies: 0
    Last Post: 03-27-2007, 06:57 PM
  4. Difference Of Rectangles
    By SMurf in forum C Programming
    Replies: 2
    Last Post: 09-14-2005, 01:12 PM
  5. Problems about gcc installation
    By kevin_cat in forum Linux Programming
    Replies: 4
    Last Post: 08-09-2005, 09:05 AM