I'm writing a program that implements SCVT (Spherical Centroidal Voronoi Tesselation). I start with a set of points distributed over the unit sphere (I have an option for random points or an equal-area spiral). There will be from a several hundred to maybe 64K points.
我正在编写一个实现SCVT(Spherical Centroidal Voronoi Tesselation)的程序。我从分布在单位球体上的一组点开始(我有随机点或等面积螺旋的选项)。将有几百到64K点。
I then need to produce probably several million random sample points, for each sample find the nearest point in the set, and use that to calculate a "weight" for that point. (This weigh may have to be looked up from another spherical set, but that set will stay static for any given run of the algorithm.)
然后我需要产生几百万随机样本点,每个样本找到集合中最近的点,并用它来计算该点的“权重”。 (这个权重可能必须从另一个球形集中查找,但是对于任何给定的算法运行,该集合将保持静态。)
Then I move the original points to the calculated points, and iterate the process, probably 10 or 20 times. This will give me the centers of the Voronoi tiles for subsequent use.
然后我将原始点移动到计算点,并迭代过程,可能是10或20次。这将为我提供Voronoi瓷砖的中心供后续使用。
Later I will need to find a given point's nearest neighbor, to see what tile the user clicked on. This is trivially solved within the above problem, and doesn't need to be super-fast anyway. The part I need to be efficient is all those millions of nearest neighbors on the unit sphere. Any pointers?
稍后我将需要找到一个给定点的最近邻居,以查看用户点击了哪个图块。这在上述问题中很容易解决,并且无论如何都不需要超快。我需要高效的部分是单位领域数百万最近邻居。有什么指针吗?
Oh, I'm using x, y, z coordinates, but that's not set in stone. It just looks like it will simplify things. I'm also using C as I'm most familiar with it, but not wedded to that choice either. :)
哦,我正在使用x,y,z坐标,但这并不是一成不变的。看起来它会简化一些事情。我也使用C,因为我最熟悉它,但也没有坚持这个选择。 :)
I've considered using the spiral pattern for the sample points, as that gives me at least the last point's found neighbor as a good starting point for the next search. But if I do that, it looks like it would make any sort of tree search useless.
我已经考虑过将螺旋模式用于采样点,因为这至少可以让我找到最后一个点的邻居作为下一次搜索的良好起点。但是,如果我这样做,它看起来会使任何类型的树搜索无用。
edit: [I'm sorry, I thought I was clear with the title and tags. I can generate random points easily. The issue is the nearest neighbor search. What's an efficient algorithm when all the points are on the unit sphere?]
编辑:[对不起,我以为我很清楚标题和标签。我可以轻松生成随机点。问题是最近邻搜索。当所有点都在单位球上时,什么是有效的算法?]
7 个解决方案
#1
Your points are uniformly distributed over the sphere. Therefore, it would make a lot of sense to convert them to spherical coordinates and discretize. Searching the 2D grid first would narrow down the choice of nearest neighbour to a small part of the sphere in constant time.
您的点均匀分布在球体上。因此,将它们转换为球坐标并离散是很有意义的。首先搜索2D网格将缩小在恒定时间内对球体的一小部分的最近邻居的选择。
#2
I have devised a curve (I'm sure I'm not the 1st) that spirals along the sphere from pole to pole. It remains a constant distance from neighboring windings (if I did it right). For z (-1 at south pole to +1 at north pole):
我已经设计了一条曲线(我确定我不是第一条),它沿着球体从一极到另一极旋转。它与相邻绕组保持恒定距离(如果我做得对)。对于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)
It makes k/2 revolutions around the sphere, with each winding sqrt(4pi/n) from adjacent windings, while the slope dz/d(x,y) is 1/k.
它围绕球体进行k / 2转,每个绕组sqrt(4pi / n)来自相邻绕组,而斜率dz / d(x,y)为1 / k。
Anyway, set k such that the inter-winding distance covers the largest tile on the sphere. For every point in the main set, calculate the theta of the nearest point on the curve, and index the list of points by those numbers. For a given test point, calculate it's (theta of the nearest point on the curve), and find that in the index. Search outward (in both directions) from there, to theta values that are as far away as your current nearest neighbor. After reaching that limit, if the distance to that neighbor is less than the distance from the test point to the next adjacent winding, you've found the nearest neighbor. If not, jump the theta value by 2pi and search that winding the same way.
无论如何,设置k使得绕组间距离覆盖球体上的最大瓦片。对于主集中的每个点,计算曲线上最近点的θ,并按这些数字索引点列表。对于给定的测试点,计算它(曲线上最近点的θ),并在索引中找到它。从那里向外(在两个方向上)搜索到与当前最近邻居一样远的θ值。达到该限制后,如果到该邻居的距离小于从测试点到下一个相邻绕组的距离,则找到最近的邻居。如果没有,将theta值跳过2pi并以相同的方式搜索绕组。
Critique?
#3
Here is the article on neighbor search: http://en.wikipedia.org/wiki/Nearest_neighbor_search In my understanding you can use trivial algorithm of going through all Voronoi centers and calculate 3d distance between your point and center point.
这是关于邻居搜索的文章:http://en.wikipedia.org/wiki/Nearest_neighbor_search根据我的理解,你可以使用通过所有Voronoi中心的简单算法来计算你的点和中心点之间的3d距离。
distance_2 = (x - x_0)^2 + (y - y_0)^2 + (z - z_0)^2
where (x_0, y_0, z_0) is the point of interest (click) for you and {(x, y, z)} are Voronoi centers. The smallest distance will give you the nearest center.
其中(x_0,y_0,z_0)是您感兴趣的点(点击),{(x,y,z)}是Voronoi中心。最小的距离将为您提供最近的中心。
#4
Using a KD Trie is a good way to speed up the search. You can also get significantly better performance if you can tolerate some error. The ANN library will give you the result within an ε of your choosing.
使用KD Trie是加速搜索的好方法。如果您可以容忍某些错误,您还可以获得明显更好的性能。 ANN库将根据您选择的ε给出结果。
#5
OK. NEARPT3 http://www.ecse.rpi.edu/Homepages/wrf/Research/nearpt3/nearpt3.pdf algorithm could be helpful in your case. And it all depends on how many space you can afford to use for your N points. If it is O(N*logN) then there are algorithms like kD-tree based (http://www.inf.ed.ac.uk/teaching/courses/inf2b/learnnotes/inf2b-learn06-lec.pdf) which would work for O(logN) to find nearest point. In case of 64K point Nlog_2 N = about 10^6 which is easily can fit into memory of modern computer.
好。 NEARPT3 http://www.ecse.rpi.edu/Homepages/wrf/Research/nearpt3/nearpt3.pdf算法可能对您的情况有所帮助。这一切都取决于你能为N点使用多少空间。如果它是O(N * logN),则有基于kD树的算法(http://www.inf.ed.ac.uk/teaching/courses/inf2b/learnnotes/inf2b-learn06-lec.pdf)适用于O(logN)以找到最近的点。在64K点的情况下,Nlog_2 N =约10 ^ 6,这很容易适应现代计算机的存储器。
#6
You may find that organising your points into a data structure called an Octree is useful for efficient search for nearby points. See http://en.wikipedia.org/wiki/Octree
您可能会发现将点组织成称为八叉树的数据结构对于有效搜索附近点非常有用。见http://en.wikipedia.org/wiki/Octree
#7
Another possibility, simpler than creating a quad-tree, is using a neighborhood matrix.
另一种比创建四叉树更简单的可能性是使用邻域矩阵。
First place all your points into a 2D square matrix (by converting the points to polar coordinates). Then you can run a full or partial spatial sort, so points will became ordered inside the matrix.
首先将所有点放入2D方阵(通过将点转换为极坐标)。然后,您可以运行完整或部分空间排序,因此点将在矩阵内排序。
Points with small Y (or phi) could move to the top rows of the matrix, and likewise, points with large Y would go to the bottom rows. The same will happen with points with small X (or theta) coordinates, that should move to the columns on the left. And symmetrically, points with large X value will go to the right columns.
具有小Y(或phi)的点可以移动到矩阵的顶行,同样,具有大Y的点将移动到底行。具有小X(或θ)坐标的点也会发生同样的情况,这些点应移动到左侧的列。对称地,具有大X值的点将转到右列。
After you did the spatial sort (there are many ways to achieve this, both by serial or parallel algorithms) you can lookup the nearest points of a given point P by just visiting the adjacent cells where point P is actually stored in the neighborhood matrix.
在进行空间排序(通过串行或并行算法实现此目的的方法有很多种)之后,您可以通过访问相邻单元格来查找给定点P的最近点,其中点P实际存储在邻域矩阵中。
You can read more details for this idea in the following paper (you will find PDF copies of it online): Supermassive Crowd Simulation on GPU based on Emergent Behavior.
您可以在下面的论文中阅读有关此想法的更多详细信息(您可以在线找到它的PDF副本):基于紧急行为的GPU上的超大规模人群模拟。
The sorting step gives you interesting choices. You can use just the even-odd transposition sort described in the paper, which is very simple to implement (even in CUDA). If you run just one pass of this, it will give you a partial sort, which can be already useful if your matrix is near-sorted. That is, if your points move slowly, it will save you a lot of computation.
排序步骤为您提供有趣的选择。您可以使用本文中描述的奇偶换位排序,这种排序非常简单(即使在CUDA中)。如果你只运行一次,它会给你一个局部排序,如果矩阵接近排序,这可能已经很有用。也就是说,如果你的点移动缓慢,它将为你节省大量的计算。
If you need a full sort, you can run such even-odd transposition pass several times (as described in the following Wikipedia page):
如果你需要一个完整的排序,你可以多次运行这种奇偶换位传递(如下面的*页面所述):
#1
Your points are uniformly distributed over the sphere. Therefore, it would make a lot of sense to convert them to spherical coordinates and discretize. Searching the 2D grid first would narrow down the choice of nearest neighbour to a small part of the sphere in constant time.
您的点均匀分布在球体上。因此,将它们转换为球坐标并离散是很有意义的。首先搜索2D网格将缩小在恒定时间内对球体的一小部分的最近邻居的选择。
#2
I have devised a curve (I'm sure I'm not the 1st) that spirals along the sphere from pole to pole. It remains a constant distance from neighboring windings (if I did it right). For z (-1 at south pole to +1 at north pole):
我已经设计了一条曲线(我确定我不是第一条),它沿着球体从一极到另一极旋转。它与相邻绕组保持恒定距离(如果我做得对)。对于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)
It makes k/2 revolutions around the sphere, with each winding sqrt(4pi/n) from adjacent windings, while the slope dz/d(x,y) is 1/k.
它围绕球体进行k / 2转,每个绕组sqrt(4pi / n)来自相邻绕组,而斜率dz / d(x,y)为1 / k。
Anyway, set k such that the inter-winding distance covers the largest tile on the sphere. For every point in the main set, calculate the theta of the nearest point on the curve, and index the list of points by those numbers. For a given test point, calculate it's (theta of the nearest point on the curve), and find that in the index. Search outward (in both directions) from there, to theta values that are as far away as your current nearest neighbor. After reaching that limit, if the distance to that neighbor is less than the distance from the test point to the next adjacent winding, you've found the nearest neighbor. If not, jump the theta value by 2pi and search that winding the same way.
无论如何,设置k使得绕组间距离覆盖球体上的最大瓦片。对于主集中的每个点,计算曲线上最近点的θ,并按这些数字索引点列表。对于给定的测试点,计算它(曲线上最近点的θ),并在索引中找到它。从那里向外(在两个方向上)搜索到与当前最近邻居一样远的θ值。达到该限制后,如果到该邻居的距离小于从测试点到下一个相邻绕组的距离,则找到最近的邻居。如果没有,将theta值跳过2pi并以相同的方式搜索绕组。
Critique?
#3
Here is the article on neighbor search: http://en.wikipedia.org/wiki/Nearest_neighbor_search In my understanding you can use trivial algorithm of going through all Voronoi centers and calculate 3d distance between your point and center point.
这是关于邻居搜索的文章:http://en.wikipedia.org/wiki/Nearest_neighbor_search根据我的理解,你可以使用通过所有Voronoi中心的简单算法来计算你的点和中心点之间的3d距离。
distance_2 = (x - x_0)^2 + (y - y_0)^2 + (z - z_0)^2
where (x_0, y_0, z_0) is the point of interest (click) for you and {(x, y, z)} are Voronoi centers. The smallest distance will give you the nearest center.
其中(x_0,y_0,z_0)是您感兴趣的点(点击),{(x,y,z)}是Voronoi中心。最小的距离将为您提供最近的中心。
#4
Using a KD Trie is a good way to speed up the search. You can also get significantly better performance if you can tolerate some error. The ANN library will give you the result within an ε of your choosing.
使用KD Trie是加速搜索的好方法。如果您可以容忍某些错误,您还可以获得明显更好的性能。 ANN库将根据您选择的ε给出结果。
#5
OK. NEARPT3 http://www.ecse.rpi.edu/Homepages/wrf/Research/nearpt3/nearpt3.pdf algorithm could be helpful in your case. And it all depends on how many space you can afford to use for your N points. If it is O(N*logN) then there are algorithms like kD-tree based (http://www.inf.ed.ac.uk/teaching/courses/inf2b/learnnotes/inf2b-learn06-lec.pdf) which would work for O(logN) to find nearest point. In case of 64K point Nlog_2 N = about 10^6 which is easily can fit into memory of modern computer.
好。 NEARPT3 http://www.ecse.rpi.edu/Homepages/wrf/Research/nearpt3/nearpt3.pdf算法可能对您的情况有所帮助。这一切都取决于你能为N点使用多少空间。如果它是O(N * logN),则有基于kD树的算法(http://www.inf.ed.ac.uk/teaching/courses/inf2b/learnnotes/inf2b-learn06-lec.pdf)适用于O(logN)以找到最近的点。在64K点的情况下,Nlog_2 N =约10 ^ 6,这很容易适应现代计算机的存储器。
#6
You may find that organising your points into a data structure called an Octree is useful for efficient search for nearby points. See http://en.wikipedia.org/wiki/Octree
您可能会发现将点组织成称为八叉树的数据结构对于有效搜索附近点非常有用。见http://en.wikipedia.org/wiki/Octree
#7
Another possibility, simpler than creating a quad-tree, is using a neighborhood matrix.
另一种比创建四叉树更简单的可能性是使用邻域矩阵。
First place all your points into a 2D square matrix (by converting the points to polar coordinates). Then you can run a full or partial spatial sort, so points will became ordered inside the matrix.
首先将所有点放入2D方阵(通过将点转换为极坐标)。然后,您可以运行完整或部分空间排序,因此点将在矩阵内排序。
Points with small Y (or phi) could move to the top rows of the matrix, and likewise, points with large Y would go to the bottom rows. The same will happen with points with small X (or theta) coordinates, that should move to the columns on the left. And symmetrically, points with large X value will go to the right columns.
具有小Y(或phi)的点可以移动到矩阵的顶行,同样,具有大Y的点将移动到底行。具有小X(或θ)坐标的点也会发生同样的情况,这些点应移动到左侧的列。对称地,具有大X值的点将转到右列。
After you did the spatial sort (there are many ways to achieve this, both by serial or parallel algorithms) you can lookup the nearest points of a given point P by just visiting the adjacent cells where point P is actually stored in the neighborhood matrix.
在进行空间排序(通过串行或并行算法实现此目的的方法有很多种)之后,您可以通过访问相邻单元格来查找给定点P的最近点,其中点P实际存储在邻域矩阵中。
You can read more details for this idea in the following paper (you will find PDF copies of it online): Supermassive Crowd Simulation on GPU based on Emergent Behavior.
您可以在下面的论文中阅读有关此想法的更多详细信息(您可以在线找到它的PDF副本):基于紧急行为的GPU上的超大规模人群模拟。
The sorting step gives you interesting choices. You can use just the even-odd transposition sort described in the paper, which is very simple to implement (even in CUDA). If you run just one pass of this, it will give you a partial sort, which can be already useful if your matrix is near-sorted. That is, if your points move slowly, it will save you a lot of computation.
排序步骤为您提供有趣的选择。您可以使用本文中描述的奇偶换位排序,这种排序非常简单(即使在CUDA中)。如果你只运行一次,它会给你一个局部排序,如果矩阵接近排序,这可能已经很有用。也就是说,如果你的点移动缓慢,它将为你节省大量的计算。
If you need a full sort, you can run such even-odd transposition pass several times (as described in the following Wikipedia page):
如果你需要一个完整的排序,你可以多次运行这种奇偶换位传递(如下面的*页面所述):