6

我正在编写一个实现 SCVT（Spherical Centroidal Voronoi Tesselation）的程序。我从分布在单位球面上的一组点开始（我可以选择随机点或等面积螺旋）。会有几百到可能 64K 点。

然后，我需要生成大约数百万个随机样本点，为每个样本找到集合中最近的点，并使用它来计算该点的“权重”。（这个权重可能必须从另一个球形集合中查找，但是对于任何给定的算法运行，该集合将保持静态。）

然后我将原始点移动到计算点，并迭代该过程，大概 10 或 20 次。这将为我提供 Voronoi 瓷砖的中心以供后续使用。

稍后我将需要找到给定点的最近邻居，以查看用户单击了哪个图块。这在上述问题中很容易解决，并且无论如何都不需要超快。我需要提高效率的部分是单位球面上数百万个最近的邻居。任何指针？

哦，我使用的是 x、y、z 坐标，但这不是一成不变的。看起来它会简化事情。我也在使用我最熟悉的 C，但也不拘泥于那个选择。:)

我考虑过对样本点使用螺旋模式，因为这至少让我找到了最后一个点的邻居作为下一次搜索的良好起点。但如果我这样做，看起来它会使任何类型的树搜索变得无用。

编辑：[对不起，我以为我对标题和标签很清楚。我可以轻松生成随机点。问题是最近邻搜索。当所有点都在单位球面上时，什么是有效的算法？]

4

7 回答 7

3

您的点均匀分布在球体上。因此，将它们转换为球坐标并离散化会很有意义。首先搜索 2D 网格会在恒定时间内将最近邻的选择范围缩小到球体的一小部分。

于 2009-04-14T23:56:43.343 回答
1

您可能会发现将您的点组织成一个称为八叉树的数据结构对于有效搜索附近的点很有用。见http://en.wikipedia.org/wiki/Octree

于 2009-04-14T09:59:57.363 回答
1

我设计了一条曲线（我确定我不是第一个），它沿着球体从一极到另一极螺旋。它与相邻绕组保持恒定距离（如果我做得对的话）。对于z（-1在南极到+1北极）：

n = a constant defining a given spiral
k = sqrt(n * pi)

r = sqrt(z^2)
theta = k * asin(z)
x = r * cos(theta)
y = r * sin(theta)

它k/2围绕球体旋转，每个绕组sqrt(4pi/n)从相邻绕组开始，而斜率dz/d(x,y)为1/k。

无论如何，设置k为使绕组间的距离覆盖球体上最大的瓷砖。对于主集中的每个点，计算theta曲线上最近点的 ，并按这些数字索引点列表。对于给定的测试点，计算它（theta曲线上最近点的），并在索引中找到它。从那里向外（在两个方向）搜索到theta与您当前最近的邻居一样远的值。达到该限制后，如果到该邻居的距离小于从测试点到下一个相邻绕组的距离，则您找到了最近的邻居。如果不是，则跳过该theta值2pi并以相同的方式搜索该绕组。

批判？

于 2009-04-18T03:10:26.000 回答
0

使用 KD Trie 是加快搜索速度的好方法。如果你能容忍一些错误，你也可以获得明显更好的性能。ANN库将在您选择的 ε 范围内为您提供结果。

于 2009-04-13T21:04:56.040 回答
0

好的。NEARPT3 http://www.ecse.rpi.edu/Homepages/wrf/Research/nearpt3/nearpt3.pdf算法可能对您的情况有所帮助。这一切都取决于您可以为您的 N 点使用多少空间。如果它是 O(N*logN) 那么有像 kD-tree 这样的算法（http://www.inf.ed.ac.uk/teaching/courses/inf2b/learnnotes/inf2b-learn06-lec.pdf）可以为 O(logN) 找到最近的点。在 64K 点 Nlog_2 N = 大约 10^6 的情况下，这很容易适合现代计算机的内存。

于 2009-04-14T05:40:50.623 回答
0

这是关于邻居搜索的文章：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 中心。最小的距离将为您提供最近的中心。

于 2009-04-13T05:42:26.273 回答
0

另一种比创建四叉树更简单的可能性是使用邻域矩阵。

首先将所有点放入 2D 方阵中（通过将点转换为极坐标）。然后您可以运行完整或部分空间排序，因此点将在矩阵内变得有序。

Y（或 phi）小的点可以移动到矩阵的顶行，同样，Y 大的点会移动到矩阵的底行。具有小 X（或 theta）坐标的点也会发生同样的情况，这些点应该移动到左侧的列。并且对称地，具有大 X 值的点将进入右列。

完成空间排序后（有很多方法可以通过串行或并行算法实现这一点），您可以通过访问点 P 实际存储在邻域矩阵中的相邻单元来查找给定点 P 的最近点。

您可以在以下论文中阅读有关此想法的更多详细信息（您可以在线找到它的 PDF 副本）：基于紧急行为的 GPU 上的超大规模人群模拟。

排序步骤为您提供了有趣的选择。您可以只使用论文中描述的奇偶转置排序，它实现起来非常简单（即使在 CUDA 中也是如此）。如果你只运行一次，它会给你一个部分排序，如果你的矩阵是接近排序的，这可能已经很有用了。也就是说，如果您的点移动缓慢，它将为您节省大量计算。

如果你需要一个完整的排序，你可以多次运行这样的奇偶转置传递（如下面的维基百科页面所述）：

http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort

于 2014-02-08T21:32:22.910 回答