# Map Tile Formation
###### tags: `Self-Driving Cars`, `ROS`

## TL; DR: [DOWNLOAD PACKAGE](https://github.com/biomotion/map_tile_loader)

When localizing self-driving cars given point cloud map within a large area, it's a **waste of memory** if you always load the whole map to perform scan mathcing. Therefore, we usually devide a large map into **small tiles of points**. Here, we explain how the data is arranged and provide an example map loader for you to get use of this map.

## Filename
There exists many files in the folder. Each of pcd file contains points of a certain area labeled in its filename. The first and second number marked in the filename represents ,respectively, **the x, y coordinate** of the start point of this tile. In the map we provided, we divide the whole map into tiles with **100 meters** size.

There is a file named `submaps_config.json` which summarized all files in the map tile folders. It listed number of points, x and y centers of the submap and filename of each pcd. You can reference this file to create a submap loader accordinly.


...


## How to use
You definately can load the whole map if you have enough memory and nice graphics card to show the map. Otherwise, we suggest using map tile and load only neighbor area you want to match.

- For combining multiple pcd file into one `pcl::PointCloud<T>`, PointCloud class supports the method `insert`. Use the following code to combind `all_cloud` and `new_cloud`. The combined point cloud will be stored in `all_cloud`.

all_cloud->insert(all_cloud->end(), new_cloud->begin(), new_cloud->end());

- To search nearby submaps given a specific point, we should build a KD-tree in order to reduce search time to **O(log(n))**. Thankfully, PCL has implemented the KD-tree for us. See the [document](https://pointclouds.org/documentation/classpcl_1_1_kd_tree_f_l_a_n_n.html) if you are interested in further use of this class.

// build kd-tree
pcl::PointCloud<pcl::PointXYZ>::Ptr centroidCloud;
// ... add new points
submapKdtree.setInputCloud(centroidCloud); 

// search via kd-tree
pcl::PointXYZ center;
double searchRad;
std::vector<int> pointIndices;
std::vector<float> pointSquaredDistance;
submapKdtree.radiusSearch(
    center, searchRad, pointIndices, pointSquaredDistance);
cout << "found points: " << pointIndices;

Now you can choose to implement your own library for loading map tiles or use [the package I already implemented](https://github.com/biomotion/map_tile_loader).