c++ - 在结构中搜索具有相似属性的数据

Question

我创建了一个结构体并用变量填充了一个数组，这些变量可以被认为是 x y z 平面中的坐标，或者是 3 维空间中与一个点的距离。

for (a=1; a<=lst; a++) {
for (b=1; b<=hst; b++) {    
        for (c=1; c<=wst; c++) {

    point[d].x=a*k+px;
    point[d].y=b*k+py;
    point[d].z=c*k+pz;
    d++;

    }
    }
}

变量 px ... 是作为通用 k 的一小部分随机添加的，以生成一个不太“刚性”的立方体。我想在一个循环的迭代中识别出在所选“点”的给定半径内的“点”，该循环的运行次数与点数一样多。但是，我想在不运行循环来检查 point[num] 数组中的每个点以查看它是否接近的情况下执行此操作。如果不根据 point[num] 数组中点的顺序进行检查，我可以做些什么来避免这种情况？

Answer 1

我可以看到两个很好的方法来做到这一点。

1. 如果您要查找的点位于一些有序的轴向对齐网格中，那么您可以立即访问特定半径内的那些点。这样做的方法是获取 x、y、z 点并将其转换为其网格位置以及半径以定义 x、y 和 z 的最小和最大网格位置。然后您可以立即访问这些变量。

2. 如果点的形式不是轴向对齐的，也不是按网格顺序排列的，那么您需要将其放在一个可以快速搜索的形式中。我建议使用 kd 树。它需要一个从 O(n) 到 O(log(n) 的搜索操作。它的工作方式是将点集沿均值分成两半，重复直到你有一个快速可搜索的树:

PCL(点云库)也会为您做这件事!

这是一个链接:

http://pointclouds.org/

还有一个关于使用 pcl 的 kd 树的教程:

http://pointclouds.org/documentation/tutorials/kdtree_search.php#kdtree-search

事实上，它甚至向您展示了从输入点到 kd 树存储点云的半径搜索代码。在我提供的教程页面上查看半径搜索中的邻居。

祝你好运!