Multiple UIView's overlapping

问题:

I am creating multiple custom UIView's in a custom UIView. The creation of the custom sub-views is ok. They look like this:

The draw method is quite straightforward:

[[UIColor brownColor] set];

CGContextRef ctx = UIGraphicsGetCurrentContext();
CGContextSetLineWidth(ctx,
                      5.0f);
CGContextBeginPath(ctx);
CGContextMoveToPoint(ctx, 0.0f, 0.0f);
CGContextAddLineToPoint(ctx, 100.0f, 0.0);
CGContextAddLineToPoint(ctx, 130.0f, 25.0f);
CGContextAddLineToPoint(ctx, 100.0f, 50.0f);
CGContextAddLineToPoint(ctx, 0.0f, 50.0f);
CGContextClosePath(ctx);
CGContextStrokePath(ctx);
[super drawRect:rect];

Adding it to the super view is also quite simple:

    ITContextFigure *view = [[ITContextFigure alloc] initWithFrame:CGRectMake(location.x, location.y, 135.0f, 50.0f)];
    [view setBackgroundColor:[UIColor yellowColor]];
    [self addSubview:view];

So my questions are:

1) How can I detect when one overlaps the other?

I saw this solution:

if (CGRectContainsRect([myImageView1 frame], [myImageView2 frame])) {
        NSLog(@"Overlaped, it's working!");
}

But if I have multiple UIViews, doing a for on the super view and checking every single sub-view doesn't seem a good solution for me.

2) In this case, what can be done?

My main goal is to detect when this happens:

---

Update 1.0

Going to try what has been showed here, since there isn't a more elegant way. If I am able to achieve it, I will post the code on Github, if anyone needs it.

回答1:

You can dramatically cut down on the number of collision detections you need to do by cleverly sorting your data (these are called scan line or seep line algorithms). Here's an outline of how you might apply this technique to your situation.

Sort your subviews into an array ordered by ascending y. If two subviews share the same y order them by ascending x. This is your inactive list and this forms the main input to the algorithm.

The algorithm proceeds as follows.

1. While there are inactive subviews, choose an active_y. This is the y coordinate of the first subview on the inactive list.

2. Move all subviews with origins on the active_y line to a working list, sorted by ascending x. This is the active list.

3. Run through the active list collision testing each each subview with subsequent ones on the list. You do this using two indices into the list (let's call them left and right). As soon as you see a right subview that cannot intersect with the left you can advance the left index.

4. While doing the collision detection you also check to see if a subview is now completely below the active_y. Once it is, you should remove it from the active list.

The algorithm completes when all the subviews on the inactive list have been consumed and the final run through the active list completed.

This algorithm greatly cuts down on the number of collision detections you will need to perform and is roughly O(n log n), but it can also simplify the collision detection itself.

Since the active list is sorted left to right you always know when you are doing you detection routine which one is on the left and which is on the right. So, for example, when comparing the arrow shapes in your example you only need to check whether the the two leftmost vertices of the right shape fall within the left shape. You may find CGPathContainsPoint useful.

If the number of distinct shapes you are dealing with increases then you might need to consider pushing the collision detection into the scan line algorithm itself. This is a little trickier, but basically instead of the list holding subview pointers they would hold line segments that make up the shapes (excluding horizontal ones).