KD/Qtree实施 [英] KD/Qtree Implementation

问题描述

我有以下路径数据:

    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"的所有点均形成一条单独的路径；在上面属于id1 = 1的df行(0-3)中，是一条路径，依此类推.

In the above data frame, (p1,p2) forms the coordinate data and all the points belonging to the same "id1" forms one separate path; in the above df rows(0-3) belonging to id1 = 1 is one path and so on.

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

I am trying to implement Quadtree for the analysis of these trajectories. To implement Quadtrees I am trying to use "pyqtree" https://github.com/karimbahgat/Pyqtree python package.

在代码"len(spindex)"中是项目的总数，而在边界框中，"bbox"的格式为(xmin，ymin，xmax，ymax)，"testitem"是相交边界框，而len(matches)将给出相交处的节点数.

In the code "len(spindex)" are the total number of items, while bounding box, "bbox" is in the format (xmin, ymin, xmax, ymax), "testitem" is the intersection bounding box, while len(matches) will give the number of nodes in the intersection.

我正在尝试使用上述df来实现四叉树.请让我知道如何在代码中将上述df用作项目".然后如何给这些轨迹赋予不同的边界框.此外，我将如何知道或查询树以查找哪些轨迹位于四叉树的哪个区域.

I am trying to use the above df to implement quadtree. Please let me know how to use the above df as "items" in the code. And then how to give different bounding box for these trajectories. Also, how will I know or query the tree to find which trajectories are located in which area of the quadtree.

推荐答案

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

So you want to query the location of each trajectory, which means you need to calculate and insert the bbox for each. Ususally this type of data would have one row for each trajectory with a geometry field describing the sequence of xy coordinates. But since your coordinates go downwards we must do a workaround to first group all xy points belonging to each trajectory id and then calculate the bbox.

以下是未经测试的示例代码，用于填充索引(我的大熊猫非常生锈，因此可能会出现一些错误):

Here is untested example code to popoulate the index (my pandas is quite rusty so prob some mistakes in there):

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)

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

Not really sure how you plan to cluster, which would be a separate question. The main purpose of a quadtree is not to ask which quad an item is located in, but rather to ask which items intersect with any arbitrary bbox region.

因此，如果将坐标区域划分为单独的聚类区域，则可以查询每个区域中有哪些voygid轨迹.

So if you divide your coordinate area into separate cluster regions you can then query which voygid trajectories are located in each.

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

请注意，一个项目可以跨越多个正方形，并且位于多个正方形中，因此您以后可能需要或不需要额外的充实.

Note that an item can span across and be located in multiple quads, so you may or may not need need additional fleshing out afterwards.

这篇关于KD/Qtree实施的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！