将点映射到斐波那契格子上最近的点

Question

我使用以下代码生成斐波那契格子，单位球体请参见第 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
// ???

Answer 1

您可能正在寻找的是空间索引： https: //en.wikipedia.org/wiki/Spatial_database#Spatial_index。由于您只关心最近邻搜索，因此您可能需要使用相对简单的内容，例如http://docs.scipy.org/doc/scipy-0.14.0/reference/ generated/scipy.spatial.KDTree.html 。

请注意，空间索引通常考虑平面上的点而不是球体上的点。为了适应您的情况，您可能需要将球体分成几个可以用矩形近似的区域。然后，您可以根据矩形近似找到几个最近邻，并计算它们的实际半正矢距离来识别真正的最近邻。