单位球体上的最近邻,点分布大致均匀

发布于 2024-07-17 03:57:12 字数 640 浏览 9 评论 0原文

我正在编写一个实现 SCVT(球心 Voronoi 曲面细分)的程序。 我从分布在单位球体上的一组点开始(我可以选择随机点或等面积螺旋)。 会有几百个到 64K 点。

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

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

稍后我需要找到给定点的最近邻居,以查看用户单击的图块。 这在上面的问题中很容易解决,而且不需要太快。 我需要提高效率的部分是单位球体上数百万个最近的邻居。 有什么指点吗?

哦,我使用的是 x、y、z 坐标,但这并不是一成不变的。 看起来它会简化事情。 我也使用 C,因为我最熟悉它,但也不执着于这个选择。 :)

我考虑过对样本点使用螺旋图案,因为这至少为我提供了最后一个点找到的邻居作为下一次搜索的良好起点。 但如果我这样做,看起来任何类型的树搜索都会变得毫无用处。

编辑: [抱歉,我以为我已经清楚标题和标签了。 我可以轻松生成随机点。 问题是最近邻搜索。 当所有点都在单位球体上时,什么是有效的算法?]

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.

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.

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. :)

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?]

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(7

等待我真够勒 2024-07-24 03:57:12

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

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.

绳情 2024-07-24 03:57:12

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

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

陌路黄昏 2024-07-24 03:57:12

我设计了一条沿着球体从一极到另一极螺旋的曲线(我确信我不是第一个)。 它与相邻绕组保持恒定的距离(如果我做得对的话)。 对于 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 并以相同的方式搜索该绕组。

批判?

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):

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.

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.

Critique?

海螺姑娘 2024-07-24 03:57:12

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

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.

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.

中性美 2024-07-24 03:57:12

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

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.

孤星 2024-07-24 03:57:12

好的。 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,这很容易适合现代计算机的内存。

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.

我不是你的备胎 2024-07-24 03:57:12

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

首先将所有点放入二维方阵中(通过将点转换为极坐标)。 然后您可以运行完整或部分空间排序,因此点将在矩阵内排序。

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

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

您可以在以下论文中阅读有关此想法的更多详细信息(您可以在线找到其 PDF 副本):基于紧急行为的 GPU 上的超大群体模拟

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

如果需要完整排序,可以多次运行此类偶奇转置传递(如以下维基百科页面所述):

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

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.

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.

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.

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.

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.

If you need a full sort, you can run such even-odd transposition pass several times (as described in the following Wikipedia page):

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

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文