我使用以下代码生成斐波那契晶格，请参阅第 4 页了解单位球体。我认为代码工作正常。接下来，我有一个点列表（以弧度为单位指定纬度和经度，就像生成的斐波那契晶格点一样）。对于每个点，我想找到斐波那契格子上最近点的索引。 IE。我有
latitudelongitudei我特别不想迭代晶格中的所有点并找到距离最小的点，因为在实践中我生成的不仅仅是
50 O(n*m) 如果 O(m)FWIW，当谈论距离时，我的意思是haversine距离。
#!/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
// ???
您可能正在寻找的是空间索引：https://en.wikipedia.org/wiki/Spatial_database#Spatial_index。由于您只关心最近邻搜索，因此您可能需要使用相对简单的东西，例如 http://docs.scipy.org/doc/scipy-0.14.0/reference/ generated/scipy.spatial.KDTree.html。
请注意，空间索引通常考虑平面上的点而不是球体上的点。为了适应您的情况，您可能需要将球体分成几个可以用矩形近似的区域。然后你可以根据矩形近似找到几个最近邻，并计算它们的实际半正弦距离来识别真正的最近邻。
这里使用球坐标会更容易一些。
您的球面坐标由 lat = arcsin(2 * i / (2 * N + 1)) 和 lon = 2 * PI * i / 黄金比例给出。 扭转这一局面并不是死胡同——这是确定纬度的好方法。反向方法的问题只是它无法表示经度。
sin(纬度) = 2 * i / (2 * N + 1)
i = (2 * N + 1) * sin(纬度) / 2
这个 i 是与输入点的纬度相匹配的点的索引的精确表示。下一步是你的选择 - 暴力，或选择不同的螺旋。
斐波那契螺旋非常适合覆盖球体，但其特性之一是它不保留连续索引之间的局部性。因此，如果你想找到最近的点，你必须搜索一个很大的范围——甚至很难估计这个搜索的范围。蛮力是昂贵的。然而，这已经是对检查每个点的原始问题的重大改进 - 如果您愿意，您可以对结果进行阈值并以您喜欢的任何方式限制您的搜索，并获得大致准确的结果。但是，如果您想以更具确定性的方式完成此任务，则必须进行更深入的研究。
我对这个问题的解决方案看起来有点像这样（抱歉，这是用 C# 编写的，而不是 Python）
// Take a stored index on a spiral on a sphere and convert it to a normal vector
public Vector3 UI2N(uint i)
{
double h = -1 + 2 * (i/n);
double phi = math.acos(h);
double theta = sqnpi*phi;
return new Vector3((float)(math.cos(theta) * math.sin(phi)), (float)math.cos(phi), (float)(math.sin(theta) * math.sin(phi)));
}
// Take a normalized vector and return the closest matching index on a spiral on a sphere
public uint N2UI(Vector3 v)
{
double iT = sqnpi * math.acos(v.y); // theta calculated to match latitude
double vT = math.atan2(v.z, v.x); // theta calculated to match longitude
double iTR = (iT - vT + math.PI_DBL)%(twoPi); // Remainder from iTR, preserving the coarse number of turns
double nT = iT - iTR + math.PI_DBL; // new theta, containing info from both
return (uint)math.round(n * (math.cos(nT / sqnpi) + 1) / 2);
}
其中 n 是螺旋线的分辨率，sqnpi 是 sqrt(n * PI)。 这不是最有效的实现方式，也不是特别清晰。然而，这是一个我可以尝试解释的中间立场。 我使用的螺旋是我在这里找到的： https://web.archive.org/web/20121103201321/http://groups.google.com/group/sci.math/browse_thread/thread/983105fb1ced42c/e803d9e3e9ba3d23#e803d9e3e9ba3d23%22%22
（猎户座螺旋基本上就是我在这里使用的螺旋）
由此，我可以反转该函数以获得 Theta（沿螺旋的距离）的粗略和精细测量，并将它们结合起来找到最合适的指数。其工作原理是 iT 是累积的，但 vT 是周期性的。 vT 是更正确的经度测量，但 iT 是更正确的纬度测量。
我强烈鼓励任何阅读本文的人尝试除我正在使用代码所做的事情之外的事情，因为我知道可以从这里改进它 - 这就是我所做的，并且我会做得更好。对于当前的实现，使用双精度数是绝对必要的 - 否则会丢失太多信息，特别是在三角函数和转换为 uint 的情况下。
Keinert、Innmann、Sanger 和 Stamminger 的论文“球形斐波那契映射”为这个问题提供了恒定时间的解决方案，而无需使用查找表。 https://docplayer.net/40493580-Spherical-fibonacci-mapping.html有一个可下载版本。