iPhone - intersection of rectangles

Question

I have this NSMutableArray which is a collection of objects that are being moved on the screen. When an object intersects another one, I need to construct an array with this object intersected. If this object is by itself intersecting with another, this one must be included in that array and so on, recursively until I know all the objects intersecting with the object that was intersecting with the other and so on.

Example: I am moving object1 and I intersect object2, but object2 intersects object3 that intersects 4, that intersects 5 and so on.

I want to collect all these objects in one array.

What I did was 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 this just gives me 2 levels deep.

How do I create a recursion here, that will go to the whole tree of possibilities?

thanks.

Answer 1

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

In my experience, the iPhone stopped updating live with an inefficient algorithm. Here is what I settled on (pseudocode - sorry, the full source has a lot of other stuff going on).

One thing to note, this algorithm keeps multiple overlapping rectangles so when you update the screen you need to bringSubviewToFront: on the intersections with the 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's 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 pretty as a recursive algorithm, but it's important to keep the total number of intersections low. Now I first tried this with an n! algorithm so of course it choked. The n^2 one above, I'm not sure if it will be adequate. As I understand my algorithm, each time through is order n though some worst case examples with everything overlapping (but not completely) could be n! (that's the data, not the algorithm).

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

Gotta run - sorry for any typos!

Damien

Answer 2

Here is a 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'd have to do some indexing of some sort. Recursion isn't necessarily better here unless you have a data structure of objects indexed by location. But it takes work to maintain that index (typically when you update locations).

Answer 3

Because the 1 time calculation would be on the order of O(n^2), I would suggest maintaining an NSMutableArray for each object which contains the objects it is currently intersecting directly. Then the order for each new calculation changes to O(n), simply taking a union of the items in the tree.

However, if you'd still like to pursue the O(n^2) method, here's an example. I'm assuming 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, just initialize a mutable array and pass in your reference to the original object.

Answer 4

[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;
}