问题标签 [kdtree]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
3 回答
5640 浏览

computational-geometry - 它如何将图像与 kd-trees 和最近邻搜索进行比较/匹配?

我一直在向谷歌查询有关 kd-trees 和图像比较的一些材料,但我无法在使用 kd-trees 进行图像比较的技术之间建立“链接”。首先,我找到了一些关于使用随机 kd-trees 提高速度的文章,然后我被介绍给了 SIFT。在基本了解了 SIFT 的工作原理后,我阅读了有关最近邻搜索的内容。

我真正的问题是:如果我有来自 SIFT 的点网格,那么我为每个图像创建 kd-tree。最近邻搜索如何帮助我比较图像?起初,我认为将图像与树进行比较可以使用某种算法检查树结构以及每个点与图像 A 与图像 B 中同一节点中的点的距离。

如果问题太愚蠢,请提出材料或一些搜索主题。

谢谢!

0 投票
1 回答
542 浏览

java - 双kd树构造

请任何人告诉我如何构建对偶kd-tree以及如何遍历它?

并且至少告诉我nearest neighborjava. 这将有助于我的项目。

谢谢你。

0 投票
2 回答
877 浏览

c++ - 将 kdtree 写入/读取到文件中

我是 C++ 和数据结构的新手,我有近似最近邻居的代码,为此我在 C++ 中实现了一个 Kd-tree。

我的问题如何将 kd-tree 写入文件以及如何从该文件中读取它?

谢谢你的帮助

0 投票
1 回答
1338 浏览

algorithm - Kd-树问题

我正在尝试实施和理解KdTree,以下是我找到的链接。 http://ldots.org/kdtree/#buildingAkDTree 但我无法理解以下算法

我不明白是什么意思 Calculate the median x-value.

0 投票
2 回答
3671 浏览

c++ - Kd 树迭代实现(C++)

你好有没有人在 C++ 中迭代实现 Kd-Tree。我试过了,但是当节点数是奇数时它失败了。到目前为止,这是我的代码。我指的是http://ldots.org/kdtree/#buildingAkDTree网站了解详细信息。

失败的示例输入:

这适用的示例输入:

0 投票
3 回答
11008 浏览

python - scipy.spatial.KDTree 和 scipy.spatial.cKDTree 之间的区别

这两种算法有什么区别?

0 投票
2 回答
2043 浏览

c++ - 解释这个算法(比较SURF算法中的点)

我需要知道这个算法是否是已知的:


这比较了SURF算法的结果。

  1. 这是最近邻算法?看起来 func 正在搜索每个点的最近点。
  2. 我可以使用 Quadtree 或 kd-tree 做同样的事情吗?
  3. 有更好的算法来比较图像点并知道它们是否相同或相似?
  4. 最好我想将它们存储到 mysql 中并构建一个 kd-tree 来比较所有图像中的 1 个图像,这可能吗?
  5. RANSAC 对这项任务有什么用?
  6. 有什么方法可以捕捉误报?
0 投票
1 回答
2081 浏览

mysql - 在 MYSQL 中为“最近邻”搜索实现 kd 树?

我正在为外汇市场设计一个自动交易软件。在 MYSQL 数据库中,我每隔五分钟就有多年的市场数据。除了价格和时间,我有 4 个不同的数据指标。

Time是主键,M1通过M4是不同的指标(例如标准差或移动平均线的斜率)。

这是一个真实的例子(摘录:)

给定输入M1, M2, M3, 并且M4我想(快速准确地)找到 5,000 个最接近的匹配项。

样本输入:

我认为这些指标中的每一个都可以被视为一个“维度”,并且我可以做一个nearest neighbor search来定位这个多维空间中最近的数据点。

似乎最简单的方法是遍历每个数据点并测量到我的输入点的多维距离;但速度至关重要!

我读到了一种叫做K-D Trees用于此目的的东西。谁能解释一下或向我提供一些解释如何在 MYSQL 中实现这一点的材料?

值得一提的是,我可以对表格进行预处理,但输入是实时接收的。

目前我只是围绕每个维度上的数据独立地做了一个粗略的聚类:

重要的是要了解我对排名感兴趣的距离,而不是价值。

编辑:我更接近于理解如何做到这一点(我认为):我需要预处理每个指标的每一行并为其分配一个percentile代表其在其范围内的位置(百分比)的值。

例如,对于任何给定的值M1

如果我计算输入的百分位数并将用于最近邻搜索而不是实际值,我将有效地缩放各种指标,以便它们可以用作维度。

不过,我仍然不知道如何进行实际搜索。这甚至可以在 MySQL 中有效地完成吗?

0 投票
2 回答
414 浏览

haskell - 在 Haskell 中通过整数参数化类型

我正在尝试制作一些 Haskell 类型,这些类型不是按类型而是按类型的元素(特别是整数)进行参数化。例如,R^2 中的(线性代数)向量和 R^3 中的向量是不同类型的对象。具体来说,我正在用 Haskell 编写一个 KD 树,我想用一个正整数参数化我的数据结构,因此 3-D 树和 4-D 树具有不同的类型。

我试图通过元组参数化我的树,但它似乎没有去任何地方(而且这似乎不太可能被推动,特别是因为看起来三元组或更大的东西甚至不是函子(和我不知道如何说,例如 HomogeneousTuple a => Functor a)。我想做这样的事情:

那会很好,或者类似的东西同样好

有人知道这些效果中的任何一个是否可行或合理吗?

谢谢-约瑟夫

0 投票
1 回答
826 浏览

rendering - 斯坦福兔子模型中使用 kd 树的光线追踪

我正在尝试对 PLY 格式的斯坦福兔子模型进行光线追踪。我有一个解析器,它解析 PLY 文件并给我三角形的坐标值及其顶点。现在我很困惑如何继续前进。我应该把这些三角形顶点放在一个向量中,然后传递它们来构建一个 kd 树吗?还有人有教程或示例源代码,其中将 ply 模型传递给 kd 树,然后遍历 kd 树以对场景进行光线跟踪?如果有人有可以分享的示例代码,请告诉我。谢谢。