1

环境

我有一个 PCL 类型的点云PointXYZ。我需要将它转换为 type 的网格图vector<vector<bool> >，map[x][y]如果至少有一个点它应该是真的。地图应该代表点云的某个区域（比如 20x30 个单元格，覆盖 x=[-10,10],y=[-15,15] 的点云维度。

我现在拥有的

目前我有两种方法：

  1. 扫描所有点并将地图中的相应单元格设置为true。
  2. 将点投影到平面，创建一个 Kd-Tree，然后为地图中的每个单元格查询树中最近的点，如果它落入单元格中，则将单元格设置为 true。

现在，第一种方法适用于小点云：O(n)，其中 n 是点云中的点数。

我认为第二种方法适用于大型云。最终查询只有 O(m)，其中 m 是地图的大小。但是，构建 Kd 树和将云投影到平面上都应该是 O(n) 左右。

我认为第二种方法总是更糟，但我会进行测试看看。

问题

有没有更好的方法？也许有八叉树或体素网格（二维）？方法一的问题是，我不必要地查看感兴趣区域之外的点。

在我看来，我不可能是第一个遇到这个问题的人，对吧？

4

1 回答 1

3

如果点云已经“组织好”（例如，如果它直接来自 RGBD 传感器），您可以通过巧妙地遍历 2D 阵列在最佳情况下击败 O(N)。有关有组织的点云的信息，请参阅https://pcl.readthedocs.io/projects/tutorials/en/latest/basic_structures.html

如果点云没有组织，那么除了点本身之外，点云中没有关于空间组织的信息，因此您几乎在每种情况下都必须触摸它们中的每一个。如果地图足够小，您可以在地图满时退出，但我猜这不太可能发生。

如果您对概率结果感到满意，那么您可以通过随机采样点云来构建地图。

于 2013-01-23T09:36:17.990 回答