multi image collision detection

Question

heres the problem

i have 5 balls floating around the screen that bounce of the sides, top and bottom. thats working great.

what i want to do now is work out if any of them collide with each other.

i know about

 if (CGRectIntersectsRect(image1.frame, image2.frame)) 
{

}

but that only checks two images, i need to check all and each of them..

ive checked everywhere but cant find the answer, only others searching the same thing, any ideas?

thanks in advance

Spriggsy

edit:

im using this to find the CGRect and store it in an array

ball1 = NSStringFromCGRect(image1.frame);
ball2 = NSStringFromCGRect(image2.frame);
ball3 = NSStringFromCGRect(image3.frame);
ball4 = NSStringFromCGRect(image4.frame);
ball5 = NSStringFromCGRect(image5.frame);

bingoarray = [NSMutableArray arrayWithObjects:ball1,ball2,ball3,ball4,ball5,nil];

this then gets passed to a collision detection method

-(void)collision   {


    for (int i = 0;  i<[bingoarray count]-1 ; i++) {

        CGRect ballA = CGRectFromString([bingoarray objectAtIndex:i]);

        if (CGRectIntersectsRect(ballA, image1.frame)) {
            NSLog(@"test"); 
        }
    }

this i guess should check one ball against all the others.

so ball 1 gets checked against the others but doesnt check ball 2 against them. is this nearly there?

}

Answer 1

The ideal solution is to store all the rectangles into a interval tree or a segment tree in order to efficiently compute any overlapping areas. Note that you will have to generalize to 2 dimensions for your use case.

Another efficient approach would be to use a K-d tree to find the nearest other balls and compare against the nearest neighbor until there isn't a collision.

The simple approach is to simply iterate over all the balls and compare them to all other balls with a higher ID (to avoid double checking ball1 -> ball2 and ball2 -> ball1).

Since you only have 5 at once, the iterative approach is likely fast enough to not be dropping frames in the animation, but you should consider a more scalable solution if you plan to support more balls since the simple appreach run in quadratic time.

Answer 2

That is a fun little math problem to avoid being redundant.

You can create an array of the images. And loop through it, checking if each member collides with any successive members.

I can spell it out more with code if need be.

EDIT I couldn't resist

// the images are in imagesArray

//where you want to check for a collision

int ballCount = [imagesArray count];
int v1Index;
int v2Index;
UIImageView * v1;
UIImageView * v2;
for (v1Index = 0; v1Index < ballCount; v1Index++) {
  v1 = [imagesArray objectAtIndex:v1Index];
  for (v2Index = v1Index+1; v2Index < ballCount; v2Index++) {
    v2 = [imagesArray objectAtIndex:v2Index];
    if (CGRectIntersectsRect(v1.frame, v2.frame)) {
      // objects collided
      // react to collision here
    }
  }
}