python - KD/Qtree 实现

Question

我有以下路径数据:

    id1            p1        p2
 0   1             7.935     5.103
 1   1             7.934     5.112
 2   1             7.936     5.102
 3   1             7.938     5.145
 4   2             7.930     5.191
 5   2             7.945     5.161
 6   2             7.954     5.127

在上述数据框中，(p1,p2)构成坐标数据，属于同一“id1”的所有点构成一条单独的路径；上述 df rows(0-3) 中属于 id1 = 1 的为一条路径，依此类推。

我正在尝试实现四叉树来分析这些轨迹。为了实现四叉树，我尝试使用“pyqtree”https://github.com/karimbahgat/Pyqtree python 包。

代码中“len(spindex)”是项目总数，而边界框，“bbox”的格式是(xmin, ymin, xmax, ymax)，“testitem”是交集边界框，而len(matches) 将给出交集中的节点数。

我正在尝试使用上面的 df 来实现四叉树。请让我知道如何在代码中使用上述 df 作为“items”。然后如何为这些轨迹给出不同的边界框。另外，我如何知道或查询树以找到哪些轨迹位于四叉树的哪个区域。

Answer 1

所以你想要查询每个轨迹的位置，这意味着你需要计算并插入每个轨迹的bbox。通常，这种类型的数据每条轨迹都有一行，并带有描述 xy 坐标序列的几何字段。但由于坐标向下，我们必须采取解决方法，首先将属于每个轨迹 id 的所有 xy 点分组，然后计算 bbox。

这是未经测试的示例代码，用于填充索引(我的 pandas 很生锈，因此可能会出现一些错误):

for group in df.groupby('voygid'):
    bbox = [ group['x'].min(), group['y'].min(), group['x'].max(), group['y'].max() ]
    spindex.insert(group['voygid'][0], bbox)

不太确定您计划如何进行集群，这将是一个单独的问题。四叉树的主要目的不是询问某个项目位于哪个四边形中，而是询问哪些项目与任意 bbox 区域相交。

因此，如果您将坐标区域划分为单独的集群区域，您就可以查询每个区域中位于哪些 voygid 轨迹。

for clusterbbox in clusters:
    voygids = spindex.intersects(clusterbbox)

请注意，一个项目可以跨越并位于多个四边形中，因此您之后可能需要也可能不需要额外的充实。