Jer*_*y B 6 geometry nearest-neighbor
我正在编写一个实现SCVT(Spherical Centroidal Voronoi Tesselation)的程序.我从分布在单位球体上的一组点开始(我有随机点或等面积螺旋的选项).将有几百到64K点.
然后我需要产生几百万随机样本点,每个样本找到集合中的最近点,并用它来计算该点的"权重".(这个权重可能必须从另一个球形集中查找,但对于任何给定的算法运行,该集合将保持静态.)
然后我将原始点移动到计算点,并迭代该过程,可能是10或20次.这将为我提供Voronoi瓷砖的中心供后续使用.
稍后我将需要找到给定点的最近邻居,以查看用户点击的图块.这在上述问题中很容易解决,并且无论如何都不需要超快.我需要高效的部分是单位领域数百万最近邻居.有什么指针吗？
哦,我正在使用x,y,z坐标,但这并不是一成不变的.看起来它会简化一些事情.我也使用C,因为我最熟悉它,但也没有坚持这个选择.:)
我已经考虑过将螺旋模式用于采样点,因为这至少给了我最后一点找到的邻居作为下一次搜索的良好起点.但是,如果我这样做,它看起来会使任何类型的树搜索无用.
编辑:[对不起,我以为我很清楚标题和标签.我可以轻松生成随机点.问题是最近邻搜索.当所有点都在单位球上时,什么是有效的算法？]
这是有关邻居搜索的文章：http://en.wikipedia.org/wiki/Nearest_neighbor_search 根据我的理解，您可以使用遍历所有 Voronoi 中心的简单算法并计算您的点和中心点之间的 3d 距离。
distance_2 = (x - x_0)^2 + (y - y_0)^2 + (z - z_0)^2
其中 (x_0, y_0, z_0) 是您感兴趣的点（点击），{(x, y, z)} 是 Voronoi 中心。最小的距离将为您提供最近的中心。