ios - 在折线/路径中查找最近的点

Question

我需要从CLLocationCoordinate2D数组上的给定GMSPolyline中找到最近的点。如果更好，我可以将其转换为GMSPath。有没有现成的方法(或任何存储库)用于此类计算？我在执行过程中遇到一些问题。我想知道如何创建算法:

1. for all polylines
1.1. find smallest distance between polyline and touch point, save CLLocationCoordinate2D
2. for all distances from point 1.1.
2.1. find the shortest one, it's CLLocationCoordinate2D is our point

现在的问题是如何实现1.1 ..点？

基于 SOF shortest distance question，我编写了这样的代码:

- (void)findNearestLineSegmentToCoordinate:(CLLocationCoordinate2D)coordinate {
    GMSPolyline *bestPolyline;
    double bestDistance = DBL_MAX;
    CGPoint originPoint = CGPointMake(coordinate.longitude, coordinate.latitude);
    for (GMSPolyline *polyline in self.polylines) {
        polyline.strokeColor = [UIColor redColor]; // TMP

        if (polyline.path.count < 2) { // we need at least 2 points: start and end
            return;
        }
        for (NSInteger index = 0; index < polyline.path.count - 1; index++) {
            CLLocationCoordinate2D startCoordinate = [polyline.path coordinateAtIndex:index];
            CGPoint startPoint = CGPointMake(startCoordinate.longitude, startCoordinate.latitude);
            CLLocationCoordinate2D endCoordinate = [polyline.path coordinateAtIndex:(index + 1)];
            CGPoint endPoint = CGPointMake(endCoordinate.longitude, endCoordinate.latitude);
            double distance = [self distanceToPoint:originPoint fromLineSegmentBetween:startPoint and:endPoint];

            if (distance < bestDistance) {
                bestDistance = distance;
                bestPolyline = polyline;
            }
        }
    }

    bestPolyline.map = nil;
    bestPolyline.strokeColor = [UIColor greenColor]; // TMP
    bestPolyline.map = self.aView.mapView;
}

不过，问题出在确切点上。有什么算法吗？找到后我会在这里发布答案。

Answer 1

好的，我已经设法写了。方法nearestPointToPoint:onLineSegmentPointA:pointB:distance:允许您查找所选点和线段之间的最接近坐标和距离(因此具有起点和终点的线)。

- (CLLocationCoordinate2D)nearestPolylineLocationToCoordinate:(CLLocationCoordinate2D)coordinate {
    GMSPolyline *bestPolyline;
    double bestDistance = DBL_MAX;
    CGPoint bestPoint;
    CGPoint originPoint = CGPointMake(coordinate.longitude, coordinate.latitude);

    for (GMSPolyline *polyline in self.polylines) {
        if (polyline.path.count < 2) { // we need at least 2 points: start and end
            return kCLLocationCoordinate2DInvalid;
        }

        for (NSInteger index = 0; index < polyline.path.count - 1; index++) {
            CLLocationCoordinate2D startCoordinate = [polyline.path coordinateAtIndex:index];
            CGPoint startPoint = CGPointMake(startCoordinate.longitude, startCoordinate.latitude);
            CLLocationCoordinate2D endCoordinate = [polyline.path coordinateAtIndex:(index + 1)];
            CGPoint endPoint = CGPointMake(endCoordinate.longitude, endCoordinate.latitude);
            double distance;
            CGPoint point = [self nearestPointToPoint:originPoint onLineSegmentPointA:startPoint pointB:endPoint distance:&distance];

            if (distance < bestDistance) {
                bestDistance = distance;
                bestPolyline = polyline;
                bestPoint = point;
            }
        }
    }

    return CLLocationCoordinate2DMake(bestPoint.y, bestPoint.x);
}

方法 nearestPolylineLocationToCoordinate:将浏览所有折线(您只需要提供折线数组== self.polylines)即可找到最佳折线。

// taken and modified from: http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment
- (CGPoint)nearestPointToPoint:(CGPoint)origin onLineSegmentPointA:(CGPoint)pointA pointB:(CGPoint)pointB distance:(double *)distance {
    CGPoint dAP = CGPointMake(origin.x - pointA.x, origin.y - pointA.y);
    CGPoint dAB = CGPointMake(pointB.x - pointA.x, pointB.y - pointA.y);
    CGFloat dot = dAP.x * dAB.x + dAP.y * dAB.y;
    CGFloat squareLength = dAB.x * dAB.x + dAB.y * dAB.y;
    CGFloat param = dot / squareLength;

    CGPoint nearestPoint;
    if (param < 0 || (pointA.x == pointB.x && pointA.y == pointB.y)) {
        nearestPoint.x = pointA.x;
        nearestPoint.y = pointA.y;
    } else if (param > 1) {
        nearestPoint.x = pointB.x;
        nearestPoint.y = pointB.y;
    } else {
        nearestPoint.x = pointA.x + param * dAB.x;
        nearestPoint.y = pointA.y + param * dAB.y;
    }

    CGFloat dx = origin.x - nearestPoint.x;
    CGFloat dy = origin.y - nearestPoint.y;
    *distance = sqrtf(dx * dx + dy * dy);

    return nearestPoint;
}

您可以使用它，例如:

- (void)mapView:(GMSMapView *)mapView didEndDraggingMarker:(GMSMarker *)marker {
    marker.position = [self nearestPolylineLocationToCoordinate:marker.position];
}