3

Is there a standard algorithm for finding the shortest distance from a point to an arbitrary extended shape (a MultiPolygon, in GIS terms — might be concave, might have holes, might be a cluster of islands) on the surface of the Earth?

I'm aware of an algorithm to do this on the Euclidean plane, and I'm aware of an algorithm to find the shortest distance between two points on the surface of the Earth (the "geodesic inverse problem"), but I'm not having any luck with literature searches for point-to-extended-shape.

The best thing I've come up with so far is to project the extended shape into an azimuthal-equidistant projection centered on the point, and then use the Euclidean shortest-distance algorithm, but this is slow and also drags an entire map projection library into the application, which I would prefer to avoid for operational reasons.

If it matters, I don't particularly need to know the closest point on the boundary of the extended shape, just the distance.

zwol
  • 135,547
  • 38
  • 252
  • 361
  • When you say "the geoid" do you consider Earth to be an ellipsoid of revolution (i.e. an ellipsoid with circular equator and latitudes but ellipsoidal longitudes)? Or do work with the simpler spherical model of Earth? – Futurologist Aug 13 '19 at 13:24
  • @Futurologist The former, that's what I meant to communicate by saying "geoid" and "on the surface of the Earth" rather than "on the surface of a sphere". – zwol Aug 13 '19 at 13:26
  • Then isn't the azimuthal-equidistant projection applicable to spherical geometry? I am not sure it works well from an arbitrary point on an ellipsoid of revolution (except at the poles, where you have rotational symmetry). – Futurologist Aug 13 '19 at 17:50
  • @Futurologist [PROJ.4 is perfectly happy to do azimuthal-equidistant projections from arbitrary points on an Earthlike ellipsoid](https://proj.org/operations/projections/aeqd.html), but that's all I know about that. – zwol Aug 13 '19 at 18:05
  • Sorry I am a bit suspicious, I am not sure what implementation is being used (it could be some best spherical approximation version). These azimuthal-equidistant projection is the geodesic exponential map on a surface (and in fact on any manifold). It is just that it does not have a closed form on a general surface, and it is likely it does not have a closed formula form for the ellipsoid. That's why I asked. Also, you may be aware of this: the geodesics from the given point are straight lines, but the geodesics between points on the extended shape are not straight lines, if this matters. – Futurologist Aug 13 '19 at 22:27
  • Could you take the Euclidean algorithm, implement or use the geodesic distance function, and then apply the Euclidean approach, but just instead of using the Euclidean distance, you use the geodesic distance. That would work if you care only about the distance from a point to the vertices of your extended shapes. But if your extended shapes are geodesic polygons on the ellipsoid, then you may need the shape of geodesics or some way of finding the distance from a point to a geodesic segment. – Futurologist Aug 13 '19 at 22:33
  • Also, maybe you have seen this article: https://link.springer.com/content/pdf/10.1007%2Fs00190-012-0578-z.pdf – Futurologist Aug 13 '19 at 22:37

0 Answers0