4
$\begingroup$

I have a GPS dataset that corresponds to a route taken by a vehicle in a day. It consist of a set of coordinates. Then say I have a coordinate and I want to know how close this coordinate is to this route. So basically I am calculating the distance to each point on the route and get the minimum value. But I have to do this many times. If route has n points and there are m coordinates whose distance to the route must be calculated then complexity is m*n. I was just wondering if there could be a smarter way to this this?

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ Voronoi diagram maybe? It might be an overkill though. $\endgroup$
    – nir shahar
    Sep 22, 2021 at 14:40
  • $\begingroup$ I doubt there is faster way to achieve this than exhaustively testing each point $\endgroup$
    – Nikos M.
    Sep 22, 2021 at 15:10
  • $\begingroup$ @NikosM. In $1$-$D$, the problem can be solved in $O((m+n) \log n)$ time. So, I hope there should be better algorithms in $2$-$D$. $\endgroup$
    – Inuyasha Yagami
    Sep 22, 2021 at 16:29
  • $\begingroup$ A related StackOverflow answer. $\endgroup$
    – Inuyasha Yagami
    Sep 22, 2021 at 16:35
  • 1
    $\begingroup$ Related question: Finding the Voronoi cell a point belongs to $\endgroup$
    – Pål GD
    Sep 22, 2021 at 20:36

0

Reset to default

Your Answer

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