Finding closest object to CGPoint

Question

I have four UIViews on a UIScrollView (screen divided into quartiles)

On the quartiles, I have a few objects (UIImageViews), on each quartile.

When the user taps the screen, I want to find the closest object to the given CGPoint?

Any ideas?

I have the CGPoint and frame (CGRect) of the objects within each quartile.

UPDATE:

_{(source: skitch.com)}

Red Pins are UIImageViews.

    // UIScrollView
    NSLog(@" UIScrollView: %@", self);

    // Here's the tap on the Window in UIScrollView's coordinates
    NSLog(@"TapPoint: %3.2f, %3.2f", tapLocation.x, tapLocation.y);

    // Find Distance between tap and objects
    NSArray *arrayOfCGRrectObjects = [self subviews];
    NSEnumerator *enumerator = [arrayOfCGRrectObjects objectEnumerator];

    for (UIView *tilesOnScrollView in enumerator) {

        // each tile may have 0 or more images
        for ( UIView *subview in tilesOnScrollView.subviews ) {

            // Is this an UIImageView?
            if ( [NSStringFromClass([subview class]) isEqualToString:@"UIImageView"]) {

                // Yes, here are the UIImageView details (subView)
                NSLog(@"%@", subview);

                // Convert CGPoint of UIImageView to CGPoint of UIScrollView for comparison...
                // First, Convert CGPoint from UIScrollView to UIImageView's coordinate system for reference
                CGPoint found =  [subview convertPoint:tapLocation fromView:self];
                NSLog(@"Converted Point from ScrollView: %3.2f, %3.2f", found.x, found.y);

                // Second, Convert CGPoint from UIScrollView to Window's coordinate system for reference
                found =  [subview convertPoint:subview.frame.origin toView:nil];
                NSLog(@"Converted Point in Window: %3.2f, %3.2f", found.x, found.y);

                // Finally, use the object's CGPoint in UIScrollView's coordinates for comparison
                found =  [subview convertPoint:subview.frame.origin toView:self]; // self is UIScrollView (see above)
                NSLog(@"Converted Point: %3.2f, %3.2f", found.x, found.y);

                // Determine tap CGPoint in UIImageView's coordinate system
                CGPoint localPoint = [touch locationInView:subview];
                NSLog(@"LocateInView: %3.2f, %3.2f",localPoint.x, localPoint.y );

               //Kalle's code
                    CGRect newRect = CGRectMake(found.x, found.y, 32, 39);
                    NSLog(@"Kalle's Distance: %3.2f",[self distanceBetweenRect:newRect andPoint:tapLocation]);

            }

Debug Console

Here's the problem. Each Tile is 256x256. The first UIImageView's CGPoint converted to the UIScrollView's coordinate system (53.25, 399.36) should be dead on with the tapPoint (30,331). Why the difference?? The other point to the right of the tapped point is calculating closer (distance wise)??

<CALayer: 0x706a690>>
[207] TapPoint: 30.00, 331.00
[207] <UIImageView: 0x7073db0; frame = (26.624 71.68; 32 39); opaque = NO; userInteractionEnabled = NO; tag = 55; layer = <CALayer: 0x70747d0>>
[207] Converted Point from ScrollView: 3.38, 3.32
[207] Converted Point in Window: 53.25, 463.36
[207] Converted Point: 53.25, 399.36 *** Looks way off!
[207] LocateInView: 3.38, 3.32
[207] Kalle's Distance: 72.20 **** THIS IS THE TAPPED POINT
[207] <UIImageView: 0x7074fb0; frame = (41.984 43.008; 32 39); opaque = NO; userInteractionEnabled = NO; tag = 55; layer = <CALayer: 0x7074fe0>>
[207] Converted Point from ScrollView: -11.98, 31.99
[207] Converted Point in Window: 83.97, 406.02
[207] Converted Point: 83.97, 342.02
[207] LocateInView: -11.98, 31.99
207] Kalle's Distance: 55.08 ***** BUT THIS ONE's CLOSER??????

Jugurtha

This is basically going to require a bunch of math. Are your UIImageViews the same size? – Midnight

Yes, they are. CGRect 26.624 71.68 32 39. All the same size. – Jugurtha

Added Update with Image and Kalle's code. There's something strange happening when I convert the UIImageView's CGPoint to the UIScrollViews coordinate system that throws off the coordinates and Kalle's code. Can anyone see what I'm missing? – Jugurtha

Hm. For starters, try adding an NSLog in distanceBetweenRect:andPoint: that prints out the two points being compared? I.e.: NSLog(@"Calculating distance between %f,%f and %f,%f.", point.x,point.y, closest.x,closest.y); right above the return. If THAT looks odd and the input is right, I must've screwed up in my answer :O – Dacoity

I tried putting your tapLocation and frame in by hand, and added that debug blurb. I get: Calculating distance between 30.000000,332.000000 and 30.000000,110.680000. || distance => 221.320007 -- looks correct to me. – Dacoity

To me it seems like you need to convert tapLocation or the subview frame so they both use the same coordinate system. Right now you're sending the subview.frame and the tapLocation which are in different systems. No? – Dacoity

AH! Yes, you were RIGHT! See the Update. But, now the other point is closer to the tapped point! I must be missing something so obvious? – Jugurtha

Yeah now you're sending the last "found" that you generated, which you yourself say is way off... but it seems to be the closest one of the 3 possible ones. Not sure what's going wrong there. But 30,331 compared to [53-85, 399-438] and [84-116, 342-381] will give you 30,331 vs 53,399 and 30,331 vs 84,342. (53-30)^2 + (399-331)^2 > (84-30)^2 + (342-331)^2, so according to those points, the distance is closer to the second one. – Dacoity

The problem now, is that the UIImageView that was tapped is now farther away than the UIImageView that wasn't tapped using Kalle's code. How is that possible?? Doesn't make sense! The second one couldn't possibly be closer, because I tapped on the first one!! – Jugurtha

The ones you're comparing, are they the ones very close to each other on your map? The center of each pin might be what you want to focus on, instead of the rect itself. I mean, people will want to touch the pin, not the needle, and this might be what's causing you confusion as well. That'd simplify it, since you now only have to decide on an offset for the pin's center, and then compare two CGPoints using pythagora. – Dacoity

I'm off in a minute, but will check back in a few hours. Hope you figure it out. :) – Dacoity

Answer 1

The following method should do the trick. If you spot anything weird in it feel free to point it out.

- (CGFloat)distanceBetweenRect:(CGRect)rect andPoint:(CGPoint)point
{
    // first of all, we check if point is inside rect. If it is, distance is zero
    if (CGRectContainsPoint(rect, point)) return 0.f;

    // next we see which point in rect is closest to point
    CGPoint closest = rect.origin;
    if (rect.origin.x + rect.size.width < point.x)
        closest.x += rect.size.width; // point is far right of us
    else if (point.x > rect.origin.x) 
        closest.x = point.x; // point above or below us
    if (rect.origin.y + rect.size.height < point.y) 
        closest.y += rect.size.height; // point is far below us
    else if (point.y > rect.origin.y)
        closest.y = point.y; // point is straight left or right

    // we've got a closest point; now pythagorean theorem
    // distance^2 = [closest.x,y - closest.x,point.y]^2 + [closest.x,point.y - point.x,y]^2
    // i.e. [closest.y-point.y]^2 + [closest.x-point.x]^2
    CGFloat a = powf(closest.y-point.y, 2.f);
    CGFloat b = powf(closest.x-point.x, 2.f);
    return sqrtf(a + b);
}

Example output:

CGPoint p = CGPointMake(12,12);

CGRect a = CGRectMake(5,5,10,10);
CGRect b = CGRectMake(13,11,10,10);
CGRect c = CGRectMake(50,1,10,10);
NSLog(@"distance p->a: %f", [self distanceBetweenRect:a andPoint:p]);
// 2010-08-24 13:36:39.506 app[4388:207] distance p->a: 0.000000
NSLog(@"distance p->b: %f", [self distanceBetweenRect:b andPoint:p]);
// 2010-08-24 13:38:03.149 app[4388:207] distance p->b: 1.000000
NSLog(@"distance p->c: %f", [self distanceBetweenRect:c andPoint:p]);
// 2010-08-24 13:39:52.148 app[4388:207] distance p->c: 38.013157

There might be more optimized versions out there, so might be worth digging more.

The following method determines the distance between two CGPoints.

- (CGFloat)distanceBetweenPoint:(CGPoint)a andPoint:(CGPoint)b
{
    CGFloat a2 = powf(a.x-b.x, 2.f);
    CGFloat b2 = powf(a.y-b.y, 2.f);
    return sqrtf(a2 + b2)
}

Update: removed fabsf(); -x^2 is the same as x^2, so it's unnecessary.

Update 2: added distanceBetweenPoint:andPoint: method too, for completeness.

Dacoity

Ok, this is getting interesting. Let me post a bit of code that converts the objects CGPoint into the coordinates of the UIScrollView so that Kalle's code should work. I've noticed some strange behavior... – Jugurtha

Happy to Report, SOVLED! I was using [subview convertPoint:subview.frame.origin toView:self]; instead of [[subview superview] convertPoint:subview.frame.origin toView:self]; Back to my original code and all worked fine. But you helped me track done the mistake. Perfect! Thanks Kalle!! I owe you one! – Jugurtha

Great to hear :) Out of curiosity, how did you originally solve it? – Dacoity

Here's how I solved it earlier, however because I didn't have the right "view", the numbers were off. I like you're approach better though. -(CGFloat)distanceBetweenPoints:(CGPoint)pt1 and:(CGPoint)pt2 { CGFloat xdist = pt2.x - pt1.x; CGFloat ydist = pt2.y - pt1.y; CGFloat distance = sqrt((xdist * xdist) + (ydist * ydist)); return distance; } – Jugurtha

Ahh, yeah with the wrong view, any method will give weird results. :P I think you probably don't need to go quite as far as I did, since your app is about tapping on pins; it doesn't seem to need that kind of accuracy. – Dacoity

For distance, there's also hypotf(a.x - b.x, a.y - b.y) – Quitclaim

Answer 2

If you're using Swift, here's how you can calculate the distance between a CGPoint and a CGRect (e.g. an UIView's frame)

private func distanceToRect(rect: CGRect, fromPoint point: CGPoint) -> CGFloat {
    // if it's on the left then (rect.minX - point.x) > 0 and (point.x - rect.maxX) < 0
    // if it's on the right then (rect.minX - point.x) < 0 and (point.x - rect.maxX) > 0
    // if it's inside the rect then both of them < 0. 
    let dx = max(rect.minX - point.x, point.x - rect.maxX, 0)
    // same as dx
    let dy = max(rect.minY - point.y, point.y - rect.maxY, 0)
    // if one of them == 0 then the distance is the other one.
    if dx * dy == 0 {
        return max(dx, dy)
    } else {
        // both are > 0 then the distance is the hypotenuse
        return hypot(dx, dy)
    }
}

Polyclinic

Answer 3

Thanks @cristian,

Here's Objective-C version of your answer

- (CGFloat)distanceToRect:(CGRect)rect fromPoint:(CGPoint)point
{
    CGFloat dx = MAX(0, MAX(CGRectGetMinX(rect) - point.x, point.x - CGRectGetMaxX(rect)));
    CGFloat dy = MAX(0, MAX(CGRectGetMinY(rect) - point.y, point.y - CGRectGetMaxY(rect)));

    if (dx * dy == 0)
    {
        return MAX(dx, dy);
    }
    else
    {
        return hypot(dx, dy);
    }
}

Partition

Answer 4

Shorter @cristian answer:

func distance(from rect: CGRect, to point: CGPoint) -> CGFloat {
  let dx = max(rect.minX - point.x, point.x - rect.maxX, 0)
  let dy = max(rect.minY - point.y, point.y - rect.maxY, 0)
  return dx * dy == 0 ? max(dx, dy) : hypot(dx, dy)
}

Personally, I would implement this as a CGPoint extension:

extension CGPoint {
    func distance(from rect: CGRect) -> CGFloat {
        let dx = max(rect.minX - x, x - rect.maxX, 0)
        let dy = max(rect.minY - y, y - rect.maxY, 0)
        return dx * dy == 0 ? max(dx, dy) : hypot(dx, dy)
    }
}

Alternatively, you can also implement it as a CGRect extension:

extension CGRect {
    func distance(from point: CGPoint) -> CGFloat {
        let dx = max(minX - point.x, point.x - maxX, 0)
        let dy = max(minY - point.y, point.y - maxY, 0)
        return dx * dy == 0 ? max(dx, dy) : hypot(dx, dy)
    }
}

Krawczyk