将PCL XYZ云转换为XY (3D到2D)

Question

设置

我有一个PointXYZ类型的PCL点云。我需要将它转换为vector<vector<bool> >类型的网格映射，其中map[x][y]应该是真的，如果至少有一个点的话。地图应该代表点云的某一区域(例如，覆盖点云尺寸x=-10,10，y=-15,15的20x30个单元格)。

我现在所拥有的

目前我有两种方法：

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

现在，第一种方法对小点云很好: O(n)，n是点云中的点数。

我认为，第二种方法对大云很有好处。最后的查询只有O(m)，其中m是映射的大小。然而，建立Kd树和将云投射到飞机上都应该是O(n)。

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

问题

有什么更好的方法吗？也许是八叉树或者Voxel(2D中的)？方法之一的问题是，我毫无必要地关注利益范围以外的问题。

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

Answer 1

如果点云已经“有组织”(例如，如果它直接来自RGBD传感器)，那么通过巧妙地遍历2D数组，您可以在最好的情况下击败O(N)。有关组织点云的信息，请参阅structures.html。

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

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