Working with Python, so my actual problem is computationally finding the closest 2D point from an array (thousands of points) which represents a road network coordinates to a given point (the car location). This calculation required every time stamp of 0.2 seconds (online). While examining the closest pair of point problem algorithm, it finds the closest point within a certain array and not with a respect to a given point as I willing to find. Does anyone familiar with python implementation or a suitable algorithm? Any help is welcome.
thanks to you all - the following is my solution (syntactic one):
import numpy as np
from sklearn.neighbors import KDTree
np.random.seed(0)
samples = np.random.uniform(low=0, high=500, size=(1000000, 2))
samples.sort(kind='quicksort')
tree = KDTree(samples)
car_location = np.array([[200, 300]])
closest_dist, closest_id = tree.query(car_location, k=1) # closest point with respect to the car location
print(samples)
print("The car location is: ", car_location)
print("The closest distance is: ", closest_dist)
print("The closest point is: ", samples[closest_id])
The output:
[[ 274.40675196 357.59468319]
[ 272.4415915 301.38168804]
[ 211.82739967 322.94705653]
...,
[ 276.40594173 372.59594432]
[ 464.17928848 469.82174863]
[ 245.93513736 445.84696018]]
The car location is: [[200 300]]
The closest distance is: [[ 0.31470178]]
The closest point is: [[[ 199.72906435 299.8399029 ]]]
ChrisN - The above is a solution for your 2nd suggestion. Your 3rd sounds definitely a better computationally solution. however, I think that my solution will satisfy the required problem. if it won't I'll try to post a solution for the 3rd. tnx!