标签: kdtree

我想为我实现一些空间索引数据结构之王MKAnnotations.目前,当我尝试根据距离标准过滤它们时非常慢(3-4k的位置,目前非常慢,只有一个简单的双for...).

我想创建群集MKAnnotations,以确定它是否接近另一个群集.此外,这些位置处于某种(创建)顺序,并且需要"先前"/"下一步"功能来"跳跃"(这不是必须的).我已经阅读了有关kd-tree和r-tree结构的信息,它们似乎都满足了过滤/聚类的快速距离/邻居获取选项,但我不确定哪种选择最适合我,或者是否还有其他选项.我应该使用什么算法/数据结构？

更新:我将这些位置存储在Core Data数据库中,它们代表一个路径.打开地图时,它们被提取到一个数组中,然后我只使用该数组进行距离计算和注释创建.当用户移动/缩放地图时,我会遍历它们并确定需要在地图上更改的内容,因此整个内容都是静态的.据我所知,如果我要使用树,我可以在那里存储位置,当发生缩放/移动时,我只搜索它并获得新区域中的那些.这是真的 ？

即使在动态情况下,当我可以向此数组添加新位置时,它也只是一次插入而且很少发生.

我试图弄清楚哪种结构对点,kd树或八叉树的半径搜索更好？在这个问题中已经提到过,但没有答案.在我看来,由于八叉树具有固定的叶子大小,它已经可以计算出我需要访问的分支,而对于kd-tree,你必须迭代地访问分支,直到覆盖半径.

输入：

point = (lat, long)
places = [(lat1, long1), (lat2, long2), ..., (latN, longN)]
count = L

输出： neighbors = places接近的子集point。（len(neighbors)=L）

问： 我可以用kd树的快速最近邻小号查找与纬度和经度点？（例如，在scipy中实现）

是否有必要在坐标x，y中转换该点的地理坐标（纬度和经度）？

这是解决此问题的最佳方法吗？

我试图制作一些Haskell类型,这些类型不是由类型参数化,而是由类型的元素,特别是整数.例如,R ^ 2中的(线性代数)矢量和R ^ 3中的矢量是不同类型的对象.具体来说,我正在Haskell中编写一个KD树,我想通过一个正整数对我的数据结构进行参数化,因此三维树和四维树具有不同的类型.

我试图通过元组对我的树进行参数化,但它似乎没有去任何地方(并且似乎有点不太可能推进,特别是因为它似乎不是三元组或更大的甚至是仿函数(和我不知道怎么说,例如HomogeneousTuple a => Functor a).我想做这样的事情:

data (TupleOfDoubles a) => KDTree a b = ... ---so in a 3DTree a is (Double,Double,Double)

这将是不错的,或类似的东西同样好

data KDTree Int a = ... -- The Int is k, so KDTree has kind Int -> * -> *

有谁知道这些影响是否可行或合理？

谢谢 - 约瑟夫

我目前正在寻找一种方法来构建几个kd树,以便快速查询一些n维数据.但是,我对scipy KD树算法有一些问题

我的数据包括 id -> {data: somedata, coordinate: x, y}

我希望能够根据坐标和k最近邻居的ID进行查询,并获得修复半径neghbour的id.从KDTree和cKDtree的scipy实现来看,这是不可用的.

我的其他选择是写我自己的KD树,这不会那么好,因为我只是我,或者......？

让这个坐标与欧几里德距离,

case class coord(x: Double, y: Double) {
  def dist(c: coord) = Math.sqrt( Math.pow(x-c.x, 2) + Math.pow(y-c.y, 2) ) 
}

然后让一个坐标网格

val grid = (1 to 25).map {_ => coord(Math.random*5, Math.random*5) }

然后对于任何给定的坐标

val x = coord(Math.random*5, Math.random*5) 

最近的点x是

val nearest = grid.sortWith( (p,q) => p.dist(x) < q.dist(x) )

所以前三个最接近的是nearest.take(3).

有没有办法让这些计算更具时间效率,特别是对于有一百万点的网格的情况？

我建立了一个d维度 KD 树。我想在这棵树上进行范围搜索。维基百科提到了 KD 树中的范围搜索，但没有以任何方式谈论实现/算法。有人可以帮我解决这个问题吗？如果不是任意的d，至少对d = 2和的任何帮助d = 3都会很棒。谢谢！

有2个图像A和B.我从中提取关键点(a [i]和b [i]).
我想知道如何有效地确定[i]和b [j]之间的匹配？

我遇到的一个明显的方法是将A中的每个点与B中的每个点进行比较.但是对于大型图像数据库而言,它过于耗时.我怎样才能将a [i]与b [k]进行比较,其中k是小范围的？

我听说kd-tree可能是个不错的选择,不是吗？关于kd-tree有什么好的例子吗？

还有其他建议吗？

我想知道是否可以在创建后从 scikit-lern KD-Tree 实例中添加或删除数据点？

例如：

from sklearn.neighbors import KDTree
import numpy as np
X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
kdt = KDTree(X, leaf_size=30, metric='euclidean')

'''
Do another stuff

'''
# Then, I want to add [8,3] point to kdt without rebuilding it again
# How to remove [-2,-1] from kdt ?

我在KD-Tree文档中没有找到此类信息

我需要分割一大堆3D点(使用C++).这些点作为二进制浮点数组存储在HDD上,文件通常大于10GB.我需要将集合划分为大小小于1GB的较小子集.子集中的点应该仍然具有相同的邻域,因为我需要对数据执行某些算法(例如,对象检测).

我以为我可以使用KD-Tree.但是,如果我无法将所有点加载到RAM中,如何有效地构建KD-Tree？也许我可以将文件映射为虚拟内存.然后我可以保存指向属于某个段的每个3D点的指针并将其存储在KD树的节点中.那会有用吗？还有其他想法吗？

谢谢您的帮助.我希望你能解决这个问题:D