1

I am working on a problem that involves some geometry and spatial points. Given a query, consisting of a point p and a line L (point not necessarily on the line), then find the point q on L that is closest to this to p. Moreover, find the Euclidean distance between p and q. As a sidenote, L here would consist of a sequence of points (hence L is not necessarily a straight line or a smooth curve).

My first take on this was to find the Euclidean distance of point p and for each of the points in L. Then take the argmin (to obtain point q) and min (for the Euclidean distance that we are looking for).

The problem of the above solution is that it seems too naive and too slow, given that L consists of several points. Moreover, this method would have to be done several times since I have a lot of points p that I need to process. I found some suggestions online to use a data structure called quad trees. The idea was to store all points in a quad tree. But I still can't wrap my head about how to compute the Euclidean distances and finding the point on this L that is closest to p using the quad tree search method. Any thoughts on how I could use quad trees to resolve the problem? And would this actually make the computation more efficient? The closest point might not be necessarily needed in the long run, but I would just like to compute it in case I do need it. But in general, I'm more interested in the Euclidean distance.

5
  • 2
    Hello and welcome. What tools do you have to work with? Can you please describe the process you are using, and the tools you have available? There are many methods to find a point on a line and to find distances between points. GIS software has tools for this. You can do it in postgis (st_closestpoint, st_distance)..
    – jbalk
    Aug 22, 2022 at 16:58
  • While it's possible quadtrees might be of use, you might want to try a data structure used in modern databases (R-tree variants), not one which isn't much used anymore.
    – Vince
    Aug 22, 2022 at 18:57
  • You're effectively asking for the distance between a LINESTRING and a point, which is close to asking for the distance between a POLYGON and a point, which I believe is a solved problem. It would be trickier in non-Euclidean space, but, fortunately, the Earth is flat. Aug 22, 2022 at 23:45
  • I guess you could start with the first (say L₀) and last (Ln) point on the line, work out the distance and then progressively move along until you converge on a single point. However that may not converge on the one closest point, but just a a closest minima
    – martyvis
    Aug 22, 2022 at 23:48
  • Actually, you can parametrize the line and find a closed form solution; however, in many cases, the min distance will occur at one of the endpoints. Aug 22, 2022 at 23:50

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.