Convert PCL XYZ cloud to XY (3D to 2D)

Question

Setting

I have a PCL point cloud of type PointXYZ. I need to convert it to a grid map of type vector<vector<bool> >, where map[x][y] should be true iff there is at least one point it. The map should represent a certain region of the point cloud (say 20x30 cells covering the point cloud dimensions of x=[-10,10],y=[-15,15].

What I have now

At the moment I have two approaches:

1. Scan through all points and set the corresponding cell in the map to true.
2. Project the points to plane, create a Kd-Tree and then for each cell in the map query the tree for the closest point and set cell to true if it falls into the cell.

Now, the first approach is good for small point clouds: O(n), with n being the number of points in the point cloud.

The second approach is good for large clouds, I think. The final query is only O(m), where m is the size of the map. However, building the Kd-tree and projecting the cloud onto the plane should both be about O(n).

I am thinking the second approach is always worse but I'll run a test to see.

Question

Are there any better approaches? Maybe something with Octree or Voxel-Grid (in 2D)? The problem with approach one is, that I am needlessly looking at points that are outside the region of interest.

It seems to me that I can't be the first to have this problem, right?

Answer 1

If the point cloud is already "organised" (as would happen for example if it was straight from an RGBD sensor) you may be able to beat O(N) in the best-case by traversing the 2D array cleverly. For information about organizsed point clouds, see https://pcl.readthedocs.io/projects/tutorials/en/latest/basic_structures.html

If the point cloud is not organised then there is no information in the point cloud about the spatial organisation apart from the points themselves, so you will in almost every case have to touch every one of them. If the map is small enough you can exit when it gets full but that is unlikely to happen I guess.

If you are happy with probabilistic results then you can build the map by sampling the point cloud randomly.