Find closest point on line from a particular point

Question

I'm using Google Maps iOS to set up Geofencing around a building complex. I've created a polyline around the complex and if the user taps outside of the polyline it will move the marker to the closest point that's on the polyline, otherwise it will just place the marker. This seems to work relatively well using this method.

However I've noticed that this method only seems to work when the point in question is perpendicular to a point on the line, otherwise it comes up with strange results. I've posted my code and some screenshots below.

-(CLLocationCoordinate2D) findClosestPointWithinFence:(CLLocationCoordinate2D) pointToTest {
    CLLocationDistance smallestDistance = 0;
    CLLocationCoordinate2D closestPoint = pointToTest;

    for(int i = 0; i < [geoFencePoints count] - 1; i++) {
        CGPoint point = [[geoFencePoints objectAtIndex:i] CGPointValue];
        CGPoint point2 = [[geoFencePoints objectAtIndex:i + 1] CGPointValue];
        CLLocationCoordinate2D locationA = CLLocationCoordinate2DMake(point.x, point.y);
        CLLocationCoordinate2D locationB = CLLocationCoordinate2DMake(point2.x, point2.y);
        CLLocationCoordinate2D myLoc = [self findClosestPointOnLine:locationA secondPoint:locationB fromPoint:pointToTest];

        if(GMSGeometryIsLocationOnPath(myLoc, dealershipParameters.path, YES)) {
            if(smallestDistance == 0) {
                smallestDistance = GMSGeometryDistance(myLoc, pointToTest);
                closestPoint = myLoc;
            } else {
                if(smallestDistance > GMSGeometryDistance(myLoc, pointToTest)) {
                    smallestDistance = GMSGeometryDistance(myLoc, pointToTest);
                    closestPoint = myLoc;
                }
            }
        }
    }
    return closestPoint;
}

-(CLLocationCoordinate2D) findClosestPointOnLine:(CLLocationCoordinate2D)locationA secondPoint:(CLLocationCoordinate2D)locationB fromPoint:(CLLocationCoordinate2D) pointToTest {
    CGPoint aToP = CGPointMake(pointToTest.latitude - locationA.latitude, pointToTest.longitude - locationA.longitude);
    CGPoint aToB = CGPointMake(locationB.latitude - locationA.latitude, locationB.longitude - locationA.longitude);

    float atb2 = (aToB.x * aToB.x) + (aToB.y * aToB.y);

    float atp_dot_atb = (aToP.x  * aToB.x) + (aToP.y * aToB.y);

    float t = atp_dot_atb / atb2;

    CLLocationCoordinate2D myLoc = CLLocationCoordinate2DMake(locationA.latitude + aToB.x * t, locationA.longitude + aToB.y * t);
    return myLoc;
}

-(BOOL)testIfInsideGeoFence:(CLLocationCoordinate2D) pointToTest {
    return GMSGeometryContainsLocation(pointToTest, dealershipParameters.path, YES) || GMSGeometryIsLocationOnPath(pointToTest, dealershipParameters.path, YES);
}

Below the first screenshot shows the marker successfully finding the closest point, the marker off the blue line is where I initially tapped, and the marker on the blue line is the point it found. The second shows the marker failing to find the closest point. The marker on the screen is where I initially tapped, since it is unable to find a proper solution it doesn't place a second marker.

Screenshot 1 Screenshot 2

picciano · Accepted Answer · 2015-10-16T15:16:00.907

I ran into a similar issue. I think what is happening is that you are treating the line segment as a line. Since the segment does not extend to a point that would be perpendicular to the point, the closest point on the segment would be one of it endpoints, not an extension of the segment.

Here is a method I am using. It takes the endpoint of the segment and returns a struct containing the nearest point on the segment and the distance from the giving point. The key difference being the if-else statements that check whether the solution is on the segment or not. You may need to rework a few things for your purposes.

The other thing to note is that I have had more accurate results performing the math on MKMapPoints rather than CLLocationCoordinate2D objects. I think it has something to do with the earth being round or some such nonsense.

+ (struct TGShortestDistanceAndNearestCoordinate)distanceFromPoint:(CLLocationCoordinate2D)p
                   toLineSegmentBetween:(CLLocationCoordinate2D)l1
                                    and:(CLLocationCoordinate2D)l2 {
    return [[self class] distanceFromMapPoint:MKMapPointForCoordinate(p)
                         toLineSegmentBetween:MKMapPointForCoordinate(l1)
                                          and:MKMapPointForCoordinate(l2)];
}

+ (struct TGShortestDistanceAndNearestCoordinate)distanceFromMapPoint:(MKMapPoint)p
                      toLineSegmentBetween:(MKMapPoint)l1
                                       and:(MKMapPoint)l2 {
    double A = p.x - l1.x;
    double B = p.y - l1.y;
    double C = l2.x - l1.x;
    double D = l2.y - l1.y;

    double dot = A * C + B * D;
    double len_sq = C * C + D * D;
    double param = dot / len_sq;

    double xx, yy;

    if (param < 0 || (l1.x == l2.x && l1.y == l2.y)) {
        xx = l1.x;
        yy = l1.y;
    }
    else if (param > 1) {
        xx = l2.x;
        yy = l2.y;
    }
    else {
        xx = l1.x + param * C;
        yy = l1.y + param * D;
    }

    struct TGShortestDistanceAndNearestCoordinate result;
    MKMapPoint nearestPoint = MKMapPointMake(xx, yy);
    result.shortestDistance = MKMetersBetweenMapPoints(p, nearestPoint);
    result.nearestCoordinate = MKCoordinateForMapPoint(nearestPoint);

    return result;
}

score 0 · Answer 2 · answered Sep 28 '20 at 08:21

0

A very elegant solution. But I'm not sure about your test in the line "if param < 0 ... ". l1.x == l2.x iff the segment is vertical, and l1.y == l2.y iff it is horizontal. So how can this conjunction ever be true? (except when l1, l2 are identical)

answered Sep 28 '20 at 08:21

hgm

725
1
5
6

Find closest point on line from a particular point

2 Answers2