Я использую следующий код для создания решетки Фибоначчи, см. стр. 4 для единичной сферы. Я думаю, что код работает правильно. Затем у меня есть список точек (указанный широтой и долготой в радианах, так же, как сгенерированные точки решетки Фибоначчи). Для каждой из точек я хочу найти индекс ближайшей точки на решетке Фибоначчи. т.е. У меня есть latitude и longitude, и я хочу получить i. Как бы я это сделал?
Я специально не хочу перебирать все точки сетки и находить точку с минимальным расстоянием, так как на практике я генерирую намного больше, чем просто 50 точки, и я не хочу, чтобы среда выполнения быть O(n*m), если O(m) возможно.
FWIW, говоря о расстоянии, я имею в виду гаверсинусное расстояние.
#!/usr/bin/env python2
import math
import sys
n = 50
phi = (math.sqrt(5.0) + 1.0) / 2.0
phi_inv = phi - 1.0
ga = 2.0 * phi_inv * math.pi
for i in xrange(-n, n + 1):
longitude = ga * i
longitude = (longitude % phi) - phi if longitude < 0 else longitude % phi
latitude = math.asin(2.0 * float(i) / (2.0 * n + 1.0))
print("{}-th point: ".format(i + n + 1))
print("\tLongitude is {}".format(longitude))
print("\tLatitude is {}".format(latitude))
// Given latitude and longitude of point A, determine index i of point which is closest to A
// ???
