IPhone - intersection of rectangles

Question

I have this NSMutableArray, which is a collection of objects that move around the screen. When an object intersects another, I need to build an array with this object intersected. If this object itself intersects with another, this one should be included in this array and so on, recursively, until I recognize all objects intersecting with an object that intersects with another, etc.

Example: I move object1 and intersect object2, but object2 intersects object3, which intersects 4, which intersects 5, etc.

I want to collect all these objects in one array.

I have done this:

NSMutableArray *intersectingObjects = [NSMutableArray array]; for (Obj *oneObj in allObjects) { if (oneObj != movingObject) { if (CGRectIntersectsRect(movingObject.frame, oneObj)) { [intersectingObjects addObject:oneObj]; } } } // at this point I got an array of all objects intersecting with the // moving object, then I created a similar block to // test all these intersecting objects against all objects again, // then I discovered the objects that were intersecting with the first block 

The problem is that it just gives me 2 levels in depth.

How to create a recursion here that goes to the whole tree of possibilities?

thanks.

Answer 1

Since a one-time calculation will be of the order of O (n ^ 2), I would suggest supporting NSMutableArray for each object that contains the objects that it currently intersects directly. Then the order for each new calculation changes to O (n), just taking the union of the elements in the tree.

However, if you still want to use the O (n ^ 2) method, here is an example. I assume Obj is a subclass of UIView?

 - (void) addViewsWhichIntersectView:(Obj*)movingObject toArray:(NSMutableArray*) intersectingObjects { for (Obj *oneObj in allObjects) { if (movingObject != oneObj && //assuming you only care about address comparison, override isEqual and use that method otherwise ![intersectingObjects containsObject:oneObj) && CGRectIntersectsRect(movingObject.frame, oneObj.frame) { [intersectingObjects addObject:oneObj]; [self addViewsWhichIntersectView: oneObj toArray:intersectingObjects]; } } } 

Then for the driver, simply initialize the mutable array and pass the link to the source object.

Answer 2

 [self intersectingObjects:allObjects withObject:movingObject]; - (NSMutableArray*) intersectingObjects:(NSArray*)objects withObject:(id)obj{ NSMutableArray * objectsToCheck = [NSMutableArray arrayWithArray:objects]; [objectsToCheck removeObject:obj]; NSMutableArray * intersectingWith = [NSMutableArray array]; for (id oneStepObj in objectsToCheck) { if (CGRectIntersectsRect(obj.frame, oneStepObj)) { //This object intersected with the provided object [intersectingWith addObject:oneStepObj]; //Also add all the objects that intersect with oneStepObj, take care of duplicates for(id nStepObj in [self intersectingObjects:objectsToCheck withObject:oneStepObj]){ if(![intersectingWith containsObject:nStepObj]){ [intersectingWith addObject:nStepObj]; } } } } } return intersectingWith; } 

Answer 3

Here is the N ^ 2 approach (good for small N):

 *intersectingObjects = [NSMutableArray array]; for (Obj *oneObj in allObjects) { for (Obj* twoObj in allObjects) { if ( oneObj != twoObj ) { if (CGRectIntersectsRect(movingObject.frame, oneObj)) { [intersectingObjects addObject:oneObj]; } } } } 

To be faster, you need to do some some indexing. Recursion here is not always better if you do not have a data structure for objects indexed by location. But maintaining this index requires work (usually when updating locations).

Answer 4

I wrote an application that does this pretty well, it's called QColor - send me a request for a promo code if you want to see it.

In my experience, the iPhone stopped updating live using an inefficient algorithm. This is what I settled in (pseudo-code - sorry, the full source has many other things).

It should be noted that this algorithm contains multiple overlapping rectangles, so when you refresh the screen, you need to display SubviewToFront: at the intersections with most rectangles.

 NSArray intersections; // each Intersection is an array of rectangles with a calculated rect - contact me if you want code that can do this (it not glorious). - (void) addRect: newRect { intersections addObject: newRect; for (Intersection *intersection in intersections) { if (intersection intersects newRect) { create new intersection of intersection + newRect // note, do NOT modify the intersection - add a NEW one. Important point. } } } - (void) removeRect: aRect { remove every intersection that contains aRect - careful, don't use fast enumeration while editing the data structure. } - (void) moveRect: aRect { for (Intersection *intersection in intersections) { if (intersection contains aRect) { recompute the intersection with the moved aRect. If ANY rectangle no longer intersects, delete the entire intersection (compare count before and after recalculation) } else { if (intersection intersects newRect) { create new intersection of intersection + newRect } } } } 

This is not as beautiful as the recursive algorithm, but it is important that the total number of intersections is low. Now I first tried this with n! algorithm, so of course he suffocated. N ^ 2 above, I'm not sure if this will be adequate. As far as I understand, my algorithm goes through the order n each time, although some examples of the worst cases with everything overlapping (but not completely) may be n! (which is data, not an algorithm).

I have screenshots on the page of my application if you want to render the rectangles: http://itunes.apple.com/ph/app/qcolor/id490077718?mt=8

Done - sorry for any typos!

Damien