Найти ближайшую точку на ломаной линии / пути

Мне нужно найти ближайшую точку из заданного 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, я написал такой код:

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

Тем не менее проблема в точной точке. Какой-нибудь алгоритм? Я отправлю ответ здесь, когда найду.


ios google-maps objective-c polyline
person Nat    schedule 19.01.2015    source источник
comment
Можете описать, в чем проблема?   -  person Ian MacDonald    schedule 19.01.2015

Ответы (2)


arrow_upward
8
arrow_downward

Хорошо, мне удалось это написать. Метод 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];
}
person Nat    schedule 19.01.2015
comment
спасибо за фрагмент кода, он очень помог. Проголосуйте за это. Также вы можете помочь, как я могу отследить все точки на поворотных точках ломаной линии? Если я получаю обновления GPS после того, как пользователь свернул на дорогу, то маркер выглядит как прыжок с x на y. вместо этого я хочу, чтобы он выглядел как пересекающаяся кривая на ломаной линии. - person NewStackUser; 09.12.2016
comment
@NewStackUser Что именно означает сделать так, чтобы он выглядел как пересекающаяся кривая на ломаной линии? - person Nat; 09.12.2016
comment
Я работаю над навигационным приложением, я получаю обновление GPS в точке x, а затем прямо в y, а между ними есть поворот направо в соответствии с полилинией, но мой GMSMarker перемещается непосредственно от x к y по диагонали с анимацией, мне нужно, чтобы он двигался по полилинии, как плавный поворот. Теперь проясните мою точку зрения? - person NewStackUser; 09.12.2016
comment
Подробности см. На странице: stackoverflow .com / questions / 41060922 / - person NewStackUser; 09.12.2016

arrow_upward
0
arrow_downward

nearestPointToPoint() от @Vive до 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
person Changhoon    schedule 09.02.2020