标签: kdtree

我看了KD树和R树的定义.在我看来,他们几乎是一样的.

KD树和R树之间有什么区别？

我正在寻找Java中的KDTree实现.
我做了谷歌搜索,结果似乎很随意.实际上有很多结果,但它们大多只是一点一点的实施,而我宁愿找到一些具有更多"生产价值"的东西.像apache集合或.NET的优秀C5集合库.我可以看到公共错误跟踪器并检查上次SVN提交的时间.此外,在理想的世界中,我会找到一个设计良好的空间数据结构API,而KDTree只是该库中的一个类.

对于这个项目,我只会在2维或3维工作,而我大多只对一个好的最近邻实现感兴趣.

写完这篇文章之后,我决定将我的钱放在我的嘴边,并开始转换我以前使用的项目recursion-schemes.

有问题的数据结构是一个懒惰的kdtree.请查看具有显式和隐式递归的实现.

这主要是一种简单的转换:

data KDTree v a = Node a (Node v a) (Node v a) | Leaf v a

至

data KDTreeF v a f = NodeF a f f | Leaf v a

现在对整个shebang进行基准测试后,我发现该KDTreeF版本比普通版本慢了两倍(在这里找到整个版本).

这只是额外的Fix包装,让我放慢了速度吗？有什么我可以做的吗？

注意事项:

• 目前这是专门为(V3双).
• 这是在变形应用之后的cata-.Hylomorphism不适合kdtrees.
• 我用cata (fmap foo algebra)了好几次.这是好习惯吗？
• 我使用Edwards recursion-schemes包.

编辑1:

这有关系吗？https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers 是newtype Fix f = Fix …

这两种算法有什么区别？

我有一个二维数组:

MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0],
                [6588253.79, 1933602.89, 212.66, 0, 0],
                 etc...)

前两个元素MyArray[0],并MyArray[1]是X和Ÿ点的坐标.

对于数组中的每个元素,我想找到以半径X单位返回其单个最近邻居的最快方法.我们假设这是在2D空间.

让我们说这个例子X = 6.

我通过将每个元素与每个其他元素进行比较来解决问题,但是当列表长度为22k点时,​​这需要15分钟左右.我们希望最终在大约3000万点的名单上运行.

我已经阅读了关于Kd树并了解基本概念,但却无法理解如何编写脚本.

四叉树和kd树之间的主要区别是什么？我知道他们在很多方面分裂了点,但我不明白为什么我们会使用一个而不是另一个.我需要一个允许我计算给定区域中有多少点(2D点)的结构.基本上,我试图检测点集群.

我正在查看KD树的维基百科页面.作为一个例子,我在python中实现了用于构建列出的kd树的算法.

然而,使用KD树进行KNN搜索的算法切换语言并不完全清楚.英语解释开始有意义,但它的一部分(例如它们"展开递归"以检查其他叶节点的区域)对我来说并没有任何意义.

这是如何工作的,如何在python中使用KD树进行KNN搜索？这不是一个"send me the code!"类型问题,我不期望这样.请简单解释一下:)

我目前正在为物理引擎(Hobby项目)编写KDTree.

KDTree不包含点数.相反,它包含Axis Aligned边界框,它绑定环境中的不同对象.

我的问题是决定如何在KDTree节点满了时拆分它们.我正在尝试2种方法:

方法1:始终将节点在最大轴上精确地分成两半.

• 这具有相当均匀间隔的树的优点.
• 大缺点:如果对象集中在节点的小区域中,则将创建冗余子分区.这是因为所有卷都被分成两半.

方法2:查找包含对象的节点区域.拆分平面上的节点,该节点将该区域在其最大轴上分成两半.示例 - 如果所有对象都集中在节点的底部,则它按长度方式分割,从而将底部分成两部分.

• 这解决了上述方法的问题
• 索引存在于同一平面(例如地形)上的内容时,会创建长而窄的节点.如果我稍后要添加一些不在同一平面上的其他对象,则这些细长节点提供非常差的索引.

所以我在这里寻找的是分割我的KD-Tree节点的更好方法.考虑到这将是一个物理引擎,决策需要足够简单,以便实时进行.

我正在使用CGAL(最新的)KD树实现来搜索点集中的最近邻居.维基百科和其他资源似乎也暗示KD树是可行的方式.但不知怎的,它们太慢了,而且Wiki也暗示了O(n)的最坏情况,这远非理想.

[BEGIN-EDIT] 我现在正在使用"nanoflann",这比用于K邻居搜索的CGAL中的等效物快约100-1000倍.我正在使用"英特尔Embree"进行光线投射,这比CGAL的AABB树快约100-200倍. [END-EDIT]

我的任务看起来像这样:

我有一个巨大的点集,比如高达几百万.点!它们的分布在三角形几何体的表面上(是的,光子示踪剂).所以可以说它们的分布在3D空间中是2D的,因为它在3D中是稀疏的,但在观察表面时是密集的......这可能是问题对吗？因为对我而言,这似乎触发了KD树的最坏情况性能,这可能会更好地处理3D密集点...

CGAl非常擅长它的功能,所以我有点怀疑它们的实现很糟糕.我用它进行光线追踪的AABB树在地上几分钟内燃烧了十亿个光线......我猜这是非常了不起的.但另一方面,他们的KD树甚至无法处理mio.在任何合理的时间点和250k样本(点查询)......

我提出了两个解决方案,从KD树中剔除废话:

1)使用纹理贴图将光子存储在几何体上的链接列表中.这总是一个O(1)操作,因为你无论如何都必须进行光线投射......

2)使用视图相关的切片哈希集.这是你得到的越远,哈希集越粗.所以基本上你可以想到NDC坐标中的1024x1024x1024光栅,但是使用哈希集来节省稀疏区域的内存.这基本上具有O(1)复杂度,并且可以有效地并行化,用于插入(微分片)和查询(无锁).

前一解决方案的缺点在于,几乎不可能对相邻光子列表进行平均,这在较暗区域中是重要的,以避免噪声.后一种解决方案没有这个问题,并且应该与KD树特征相同,只是它具有O(1)最坏情况性能,lol.

所以你怎么看？糟糕的KD树实施？如果没有,对于有界最近邻居查询,是否存在比KD树"更好"的东西？我的意思是我没有反对上面的第二个解决方案,但提供类似性能的"经过验证的"数据结构会更好!

谢谢!

这是我使用的代码(不可编译):

#include "stdafx.h"
#include "PhotonMap.h"

#pragma warning (push)
    #pragma warning (disable: 4512 4244 4061)
    #pragma warning (disable: 4706 4702 4512 4310 4267 4244 4917 4820 4710 4514 4365 4350 4640 4571 4127 4242 4350 4668 4626)
    #pragma warning (disable: 4625 4265 4371)

    #include <CGAL/Simple_cartesian.h>
    #include <CGAL/Orthogonal_incremental_neighbor_search.h>
    #include <CGAL/basic.h>
    #include <CGAL/Search_traits.h>
    #include <CGAL/point_generators_3.h>

#pragma warning (pop)

struct PhotonicPoint
{
    float vec[3];
    const Photon* photon;

    PhotonicPoint(const Photon& photon) : …

我有一组要为其构建KD树的点.一段时间后,我想定期为这个KDTree添加几点.在scipy实现中有没有办法做到这一点