哪种数据结构适合查询“距点p距离d内的所有点"; [英] which data structure is appropriate to query "all points within distance d from point p"

查看:33
本文介绍了哪种数据结构适合查询“距点p距离d内的所有点";的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有一个 3D 点云,我想有效地查询距任意点 p(不一定是存储点云的一部分)距离 d 内的所有点

I have a 3D pointcloud and I'd like to efficiently query all points within distance d from an arbitrary point p (which is not necessarily part of the stored pointcloud)

查询看起来像

Pointcloud getAllPoints(Point p, float d);

哪种加速结构适合于此?范围树似乎只适用于查询矩形体积,而不适用于球体体积(当然我可以查询球体的边界框,然后整理出所有距离大于 d 的顶点 - 但也许有更好的方法这个??)

what accelerationstructure would be appropriate for this? A range-tree seems to be appropriate only for querying rectangular volumes, not sphere volumes (of course I could query the boundingbox of the sphere and then sort out all vertices that have larger distance than d - but maybe there is a better way to do this??)

谢谢!

根据 Novelocrats 的建议,我尝试定义结构的所需功能:

according to Novelocrats suggestion, I try to define the desired functions of the structure:

SearchStructure Create(Set<Point> cloud) 
Set<Point> Query(SearchStructure S, Point p, float maxDistance)
SearchStructure Remove(Point p)
SearchStructure Insert(Point p)
SearchStructure Displace(Set<Point> displacement) //where each value describes an offsetVector to the currently present points

通常,在 n 次查询之后,点会被置换,并且会进行一些(不是很多!)插入和删除操作.与所有点的边界框相比,偏移向量非常小

Usually, after n queries, the points get displaced and a few (not many!) insertions and deletions are made. the offset vectors are very small compared to the boundingbox of all points

推荐答案

您需要的是一种分解空间的结构,以便可以有效地找到特定区域.正确分解的 octreekD-tree 应该可以让您很好地做到这一点,因为您只会打开"包含您的点 p<的树部分/code> 寻找附近的点.这应该让您对需要比较距离的额外点的数量设置一个相当低的渐近界限(知道在某个分解级别以下,所有点都足够接近).不幸的是,我对这方面的文献还不够了解,无法给出更详细的指示.我对这些东西的认识来自于 Barnes-Hut n-Body 模拟算法.

What you want is a structure that decomposes space so that particular regions can be found efficiently. A properly decomposed octree or kD-tree should allow you to do this well, as you would only 'open' the section of the tree containing your point p to look for points nearby. This should let you put a fairly low asymptotic bound on how many extra points you need to compare distance to (knowing that below some level of decomposition, all points are close enough). Unfortunately, I don't know the literature in this area well enough to give more detailed pointers. My encounter with these things is from the Barnes-Hut n-Body simulation algorithm.

这是与这个问题密切相关的另一个问题.还有另一个.还有第三个,提到了我以前从未听说过的数据结构 (Hilbert R-Trees).

Here's another question closely related to this one. And another. And a third, mentioning a data structure (Hilbert R-Trees) that I hadn't previously heard of.

这篇关于哪种数据结构适合查询“距点p距离d内的所有点";的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆