У меня есть облако точек PCL типа PointXYZ
, Мне нужно преобразовать его в карту типа сетки vector<vector<bool> >
, где map[x][y]
должно быть верно, если есть хотя бы один пункт. Карта должна представлять определенную область облака точек (скажем, 20×30 ячеек, охватывающих размеры облака точек x = [- 10,10], y = [- 15,15].
На данный момент у меня есть два подхода:
Теперь первый подход подходит для небольших облаков точек: O (n), где n — это количество точек в облаке точек.
Второй подход хорош для больших облаков, я думаю. Последний запрос — только O (m), где m — размер карты. Тем не менее, построение Kd-дерева и проецирование облака на плоскость должны составлять около O (n).
Я думаю, что второй подход всегда хуже, но я проведу тест, чтобы увидеть.
Есть ли лучшие подходы? Может быть, что-то с Octree или Voxel-Grid (в 2D)? Проблема с первым подходом состоит в том, что я без необходимости смотрю на точки, которые находятся за пределами области интересов.
Мне кажется, что я не могу быть первым, кто столкнулся с этой проблемой, верно?
Если облако точек уже «организовано» (как, например, если бы оно было прямо от датчика RGBD), вы можете превзойти O (N) в лучшем случае, ловко пройдя 2D-массив. Для получения информации об организованных облаках точек см. http://pointclouds.org/documentation/tutorials/basic_structures.php
Если облако точек не организовано, то в облаке точек нет никакой информации о пространственной организации, кроме самих точек, поэтому вам почти во всех случаях придется прикасаться к каждой из них. Если карта достаточно мала, вы можете выйти, когда она заполнится, но это вряд ли произойдет, я думаю.
Если вас устраивают вероятностные результаты, вы можете построить карту, взяв случайную выборку из облака точек.
Других решений пока нет …