标签: kdtree

在试图弄清楚如何在OpenGL/GLSL中实现kd树之后的一天,我非常沮丧......

我在GLSL中声明我的KD节点:

layout(std140) uniform node{
  ivec4 splitPoint;
  int dataPtr;
} nodes[1024];

SplitPoint保存kd树分割点,向量的第四个元素保持splitDirection在3d空间中形成一个平面.DataPtr目前仅在树的叶子中保存随机值.

整个阵列形成一个Ahnentafel列表.

在C++中,结构如下所示:

struct Node{
  glm::ivec4 splitPoint;
  GLint dataPtr;
  GLint padding[3];
};

我相信这是正确的,我上传构造的树在缓冲区.作为检查,我将缓冲区映射到主内存并检查值:

0x08AB6890     +0  +256    +0    +1    -1  -858993460  -858993460  -858993460
0x08AB68B0   +256    +0    +0    +0    -1  -858993460  -858993460  -858993460
0x08AB68D0   +256  +256    +0    +0    -1  -858993460  -858993460  -858993460
[...]
0x08AB7070     +0    +0    +0    +0 +2362  -858993460  -858993460  -858993460

看起来很好(它实际上说节点0中的音量在y方向上被分割为(0,256,0),-1是没有数据的符号).

现在为树遍历我尝试了这个:

float distanceFromSplitPlane;
while(nodes[n].dataPtr == -1){

  // get split direction
  vec3 splitDir = vec3(0,0,0);
  if(nodes[n].splitDir == …

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

[Time|Price|M1|M2|M3|M4] 
x ~400,0000

Time是主键，M1贯穿M4是不同的指标（例如标准差或移动平均线的斜率）。

这是一个真实的例子（摘录：）

+------------+--------+-----------+--------+-----------+-----------+
|  Time      | Price  |     M1    |   M2   |    M3     |     M4    |
+------------+--------+-----------+--------+-----------+-----------+
| 1105410300 | 1.3101 |   12.9132 | 0.4647 |   29.6703 |        50 |
| 1105410600 | 1.3103 |    14.056 | 0.5305 | 29.230801 |        50 |
| 1105410900 | 1.3105 |   15.3613 | 0.5722 |   26.8132 |        25 |
| 1105411200 | 1.3106 | 16.627501 | 0.4433 | …

我正在尝试实现一个Kd树来执行最近邻居并在C++中近似最近邻搜索.到目前为止,我遇到了最基本的Kd树的2个版本.

1. 数据存储在节点和叶子中的那个,例如这里
2. 数据仅存储在叶子中的数据,例如此处

它们似乎基本相同,具有相同的渐近性质.

我的问题是:为什么选择一个而不是另一个？

到目前为止,我认为有两个原因:

1. 在节点中存储数据的树也较浅1级.
2. 仅在叶子中存储数据的树具有更容易实现的delete data功能

在决定选择哪一个之前,我还应该考虑其他一些原因吗？

我正在尝试使用 KD 树来平衡一组 (Million +) 3D 点，我有两种方法可以做到。

方式一：

1. 使用 O(n) 算法沿给定轴查找数组大小/第 2 个最大元素并将其存储在当前节点

2. 迭代向量中的所有元素，对于每个元素，将它们与我刚刚找到的元素进行比较，并将较小的放在 newArray1 中，将较大的放在 newArray2 中

3. 递归

方式二：

1. 使用快速排序 O(nlogn) 沿给定轴对数组中的所有元素进行排序，获取位置 arraysize/2 的元素并将其存储在当前节点中。

2. 然后将索引 0 到 arraysize/2-1 的所有元素放入 newArray1，将 arraysize/2 到 arraysize-1 的所有元素放入 newArray2

3. 递归

方式 2 看起来更“优雅”，但方式 1 似乎更快，因为中位数搜索和迭代都是 O(n)，所以我得到 O(2n)，它只是减少到 O(n)。但同时，即使方式2是O(nlogn)的排序时间，将数组拆分为2可以在恒定时间内完成，但这是否弥补了O(nlogn)的排序时间？

我该怎么办？或者有没有更好的方法来做到这一点，我什至没有看到？

目前有一个工作示例，用于scipy.spatial.KDTree使用最近邻查找某些 x,y 点。

问题是，如果我有每个 x,y 点的日期时间数据，我可以将其放入 KDTree 并修改我的空间最近邻搜索以进行最近时空邻居搜索吗？

使用以下方法搜索最近的空间邻居：

pts = np.array([[1, 50], [1.89, 52.4]])

print tree.query(pts, k=5)

给定一个点列表，如何在 KDTree 中获取它们的索引？

from scipy import spatial
import numpy as np

#some data
x, y = np.mgrid[0:3, 0:3]
data = zip(x.ravel(), y.ravel())

points = [[0,1], [2,2]]

#KDTree
tree = spatial.cKDTree(data)

# incices of points in tree should be [1,8]

我可以做这样的事情：

[tree.query_ball_point(i,r=0) for i in points]

>>> [[1], [8]]

这样做有意义吗？

我尝试创建 WGS84 坐标的 KD 树并找到特定半径内的邻居

from sklearn.neighbors.dist_metrics import DistanceMetric
from sklearn.neighbors.kd_tree import KDTree    
T = KDTree([[47.8665, 8.90123]], metric=DistanceMetric.get_metric('haversine'))

但得到以下错误：

ValueError: metric HaversineDistance is not valid for KDTree

如何在 KD 树中使用半正弦距离？

这篇文章建立在这篇文章的基础上。

我得到了一个 Pandas 数据框，其中包含城市的地理坐标（大地坐标）作为经度和纬度。

import pandas as pd

df = pd.DataFrame([{'city':"Berlin", 'lat':52.5243700, 'lng':13.4105300},
                   {'city':"Potsdam", 'lat':52.3988600, 'lng':13.0656600},
                   {'city':"Hamburg", 'lat':53.5753200, 'lng':10.0153400}]);

对于每个城市，我都试图找到最近的另外两个城市。因此我尝试了 scipy.spatial.KDTree。为此，我必须将大地坐标转换为 3D 笛卡尔坐标（ECEF = 以地球为中心、以地球固定）：

from math import *

def to_Cartesian(lat, lng):
    R = 6367 # radius of the Earth in kilometers

    x = R * cos(lat) * cos(lng)
    y = R * cos(lat) * sin(lng)
    z = R * sin(lat)
    return x, y, z

df['x'], df['y'], df['z'] = zip(*map(to_Cartesian, df['lat'], df['lng']))
df

这给我这个：

这样我就可以创建 KDTree：

coordinates = …

我在许多参考资料中都被告知 KDTree 是一种为大数据寻找最近邻的快速方法。我当前的问题是为给定的数据 A 找到 X 中最近的点。详细说明，目前 X 有 1,000,000 个数值数据，A 由 10,000 个组成。我想为 A 中的每个点找到 X 中最近的点。因此，结果应该是 10,000 个索引，指示 X 中的数据点。

当我使用带有 for 循环的 cdist（来自 scipy.spatial）来查找 A 中每个数据的最近点时，大约需要半小时（1972 秒），而使用 n_jobs 时 cKDTree.query 需要大约 50 分钟（2839 秒） = 4。

cdist 的代码如下：

t = time.time() 
nn = np.array([])
jump = 1000
nloop = np.ceil(A.shape[0]/jump).astype(int)
for ii in range(nloop):
   temp = cdist(X, A[ii*jump:(ii+1)*jump])
   nn = np.append(nn, np.argmin(temp, axis = 0))
print('Elapsed time: ', time.time() - t) # this was 1926 seconds (a …

具有所需起点和终点的绳索点云

我有一个大约有 300 个点的绳状物体的点云。我想对该点云的 3D 坐标进行排序，以便绳子的一端具有索引 0，另一端具有索引 300，如图所示。该对象的其他点云可能是 U 形的，因此我无法按 X、Y 或 Z 坐标排序。因此，我也无法按到单个点的距离进行排序。

我已经通过sklearn或scipy查看了 KDTree来计算每个点的最近邻，但我不知道如何从那里开始对数组中的点进行排序而不需要重复输入。

有没有一种方法可以对数组中的这些坐标进行排序，以便从起点开始在数组中附加下一个最近点的坐标？