Ближайший сосед Python - координаты

Я хотел проверить, правильно ли использую дерево KD scipy, потому что оно работает медленнее, чем простой брутфорс.

У меня было три вопроса по этому поводу:

Q1.

Если я создам следующие тестовые данные:

nplen = 1000000
# WGS84 lat/long
point = [51.349,-0.19]
# This contains WGS84 lat/long
points = np.ndarray.tolist(np.column_stack(
        [np.round(np.random.randn(nplen)+51,5),
         np.round(np.random.randn(nplen),5)]))

И создайте три функции:

def kd_test(points,point):
    """ KD Tree"""
    return points[spatial.KDTree(points).query(point)[1]]

def ckd_test(points,point):
    """ C implementation of KD Tree"""
    return points[spatial.cKDTree(points).query(point)[1]]

def closest_math(points,point):
    """ Simple angle"""
    return (min((hypot(x2-point[1],y2-point[0]),y2,x2) for y2,x2 in points))[1:3]   

Однако я ожидал, что дерево cKD будет самым быстрым - запустив это:

print("Co-ordinate: ", f(points,point))
print("Index: ", points.index(list(f(points,point))))
%timeit f(points,point)

Время результата - простой метод перебора работает быстрее:

closest_math: 1 loops, best of 3: 3.59 s per loop
ckd_test: 1 loops, best of 3: 13.5 s per loop
kd_test: 1 loops, best of 3: 30.9 s per loop

Это потому, что я как-то неправильно его использую?

Q2.

Я бы предположил, что даже для того, чтобы получить рейтинг (а не расстояние) ближайших точек, все же необходимо спроецировать данные. Однако кажется, что спроецированные и непроецированные точки дают мне одного и того же ближайшего соседа:

def proj_list(points,
              inproj = Proj(init='epsg:4326'),
              outproj = Proj(init='epsg:27700')):
    """ Projected geo coordinates"""
    return [list(transform(inproj,outproj,x,y)) for y,x in points]
proj_points = proj_list(points)
proj_point = proj_list([point])[0]

Это просто потому, что мой разброс точек недостаточно велик, чтобы вносить искажения? Я выполнял повторный запуск несколько раз и все равно получил тот же индекс из возвращаемых спроектированных и непроектированных списков.

Q3.

Является ли обычно более быстрым проецирование точек (как указано выше) и вычисление расстояния гипотенузы по сравнению с вычислением расстояния гаверсинуса или винсента на (непроектируемых) широте / долготе? И какой вариант будет более точным? Я провел небольшой тест:

from math import *
def haversine(origin,
              destination):
    """
    Find distance between a pair of lat/lng coordinates
    """
    lat1, lon1, lat2, lon2 = map(radians, [origin[0],origin[1],destination[0],destination[1]])
    dlon = lon2 - lon1
    dlat = lat2 - lat1
    a = sin(dlat / 2) ** 2 + cos(lat1) * cos(lat2) * sin(dlon / 2) ** 2
    c = 2 * asin(sqrt(a))
    r = 6371000  # Metres
    return (c * r)

def closest_math_unproj(points,point):
    """ Haversine on unprojected """
    return (min((haversine(point,pt),pt[0],pt[1]) for pt in points))

def closest_math_proj(points,point):
    """ Simple angle since projected"""
    return (min((hypot(x2-point[1],y2-point[0]),y2,x2) for y2,x2 in points)) 

Результаты:

Таким образом, это, кажется, говорит о том, что проецирование, а затем выполнение расстояния быстрее, чем нет - однако я не уверен, какой метод принесет более точные результаты.

Тестирование этого с помощью онлайн-расчета винсенти, по-видимому, является планируемым -координаты - это то, что нужно: