Detecting collisions on drag in iOS

Question

Given a view hierarchy where views can be dragged, what is the most efficient way to detect collisions between the dragged view and the other views?

This would be the brute-force approach (in pseudo-code):

- (void) onDrag 
{
    CGRect absoluteDraggedViewRect; // Calculate
    for (UIView *otherView in hierarchy)
    {
        CGRect absoluteOtherViewRect; // Calculate
        if (CGRectIntersectsRect(absoluteDraggedViewRect, absoluteOtherViewRect))
        {
            // Collision!
        }
    }
}

How would you improve the above code?

Answer 1

I think the only improvement 'visible' at this point is to add:

if (otherView == self)
    continue;

in your loop. Of course only if self is in hierarchy.

In the end you have to check for every view if it intersects with your dragged one. If you later realize that this turns out to be a significant performance issue, you can try to spread the workload. You could divide your 'moving area' into multiple sections. After a view is dragged you calculate with which sections it intersects and save a dictionary or another appropriate data structure with all views in each section. Then you'd only have to loop through the views of the sections of the dragged view. But if that pays off depends on your specific use case. And I would only consider it, if your current method turns out to be a performance problem.

As Donald Knuth once said:

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil"