在 polyline/path 中找到最近的点

Question

我需要在 GMSPolyline 的数组中找到距给定 CLLocationCoordinate2D 最近的点。如果更好的话，我可以将其转换为 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;
}

不过，问题出在确切的点上。任何算法？找到后我会post在这里回答。

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: 
- (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];
}

Answer 2

@Vive 的 nearestPointToPoint() 到 Swift 5

func nearestPointToPoint(_ origin: CGPoint, _ pointA: CGPoint, _ pointB: CGPoint) -> (CGPoint, Double) {
  let dAP = CGPoint(x: origin.x - pointA.x, y: origin.y - pointA.y)
  let dAB = CGPoint(x: pointB.x - pointA.x, y: pointB.y - pointA.y)
  let dot = dAP.x * dAB.x + dAP.y * dAB.y
  let squareLength = dAB.x * dAB.x + dAB.y * dAB.y
  let param = dot / squareLength

  // abnormal value at near latitude 180
  //  var nearestPoint = CGPoint()
  //  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
  //  }

  let nearestPoint = CGPoint(x: pointA.x + param * dAB.x, 
                             y: pointA.y + param * dAB.y)

  let dx = origin.x - nearestPoint.x
  let dy = origin.y - nearestPoint.y
  let distance = sqrtf(Float(dx * dx + dy * dy))

  return (nearestPoint, Double(distance))
}

结果是

me: (53, -1), pointA: (52, -2), pointB(52, 0) => (52, -1)
me: (53, 0), pointA: (52, -1), pointB(52, 1) => (52, 0)
me: (53, 1), pointA: (52, 0), pointB(52, 2) => (52, 1)

me: (-1, -77), pointA: (0, -78), pointB(-2, -78) => (-1, -78)
me: (0, -77), pointA: (-1, -78), pointB(1, -78) => (0, -78)
me: (1, -77), pointA: (2, -78), pointB(0, -78) => (1, -78)

me: (1, 179), pointA: (0, 178), pointB(0, 180) => (0, 179)
me: (1, 180), pointA: (0, 179), pointB(0, -179) => (0, 180)
me: (1, -179), pointA: (0, 180), pointB(0, -178) => (0, -179)

但是在纬度 180 处出现了一些错误。我无法修复它。

me: (0, 180), pointA: (0, 179), pointB(1, 180) => (0.5, 179.5)
me: (0, -179), pointA: (0, 179), pointB(1, -179) => (0.99, -178.99) // abnormal

在 polyline/path 中找到最近的点

Find nearest point in polyline/path

google-maps

objective-c

polyline

ios