Finding a point close enough to a point

Question

I have a problem with some peculiar characteristics.

I have:

• a point P (well in reality it is an array of points ArrayP, but the function I want to write is applied to each and every point, so it receives each time one point)

• an array of other points (which form a trajectory) Trajectory

• also the index of the first point in the original array.

Also the number of points in Trajectory is always bigger than the number of points in ArrayP.

I need to find the closest point in Trajectory to P

For example

My problem is that I don't know the indexes in Trajectory, only the index in ArrayP

Also the number of points in Trajectory is big so I prefer not to try all of them.

I have developed an algorithm that works well for some simple trajectories but it fails in some a bit more complicated trajectories still. Rather than posting it here and ask for improvements, I would like to hear a fresh approach on how to solve this problem

Answer 1

When you say "I prefer not to try all of them", is there really a need for this (i.e. would be too long to compute otherwise) or just your intuition ? Because otherwise this is a pretty straightforward problem, simply calculate the distances between all the trajectory points and each point in your array and return the minimum for each one.

Regarding the issue of not having the index of the trajectory points, you can simply use two variables to store the current nearest point and its distance and update it as you iterate through the trajectory points.