Fastest way to calculate euclidian distance in 2D space

Question

What is the fastes way of determening which point q out of n points in 2D space is the closest (smallest euclidian distance) to point p, see attached imgage.

My current method of doing this in Python is storing all the distances in a list and then running

numpy.argmin(list_of_distances)

This is however a bit slow when calculating this for m number of points p. Or is it?

Answer 1

This falls under closest point query -problems.

How many points are expected? Are your points static or do they change? One naive but powerful approach for static points would be to pre-compute every known distance, which would result in O(1) lookup.

Answer 2

Instead of calculating the distances, you could calculate the squared distances. That way you don't need to perform n * m square roots.

Answer 3

Put everything as soon as possible into numpy and do calculations there. If you have many points, it is much faster than calculating distances in lists:

import numpy as np

px, py
x = np.fromiter(point.x for point in points, dtype = np.float)
y = np.fromiter(point.y for point in points, dtype = np.float)

i_closest = np.argmin((x - px) ** 2 + (y - py) ** 2)