在多段线/path中查找最近的点
我需要从GMSPolyline数组上的给定CLLocationCoordinate2D查找最近点。 如果更好，我可以把它转换成GMSPath 。 有没有现成的方法（或任何存储库）进行这样的计算？ 我有一些执行问题。 我想知道如何创build一个algorithm：
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; }
不过，问题的确切点在于。 任何algorithm？ 我会在find答案的时候发布。
好吧，我已经设法写下来了。 方法nearestPointToPoint:onLineSegmentPointA:pointB:distance:允许你find最近的坐标和选定的点和段线之间的距离（所以开始和结束行）。
- (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），并find最好的一个。
// 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]; }