KDTree+UTM
update 时间：2020，7，25
在自动驾驶平台中，高精地图数据坐标通常采用平面坐标，如UTM，目的是方便坐标的转换以及几何计算。
因此，地图数据模块为了能够方便的提供给其他模块使用，建议输出UTM或者车身坐标系。
在Apollo中，Map数据源数据采用UTM坐标存储，在程序启动时会在内存中构建KDTree空间索引。
KDTree空间索引支持快速的最近邻搜索，并且可以直接利用平面坐标构建KDTree。这为后续坐标计算提供了便利。
而s2geometry，虽然同样支持平面坐标索引，但其平面坐标单位并非是“meter”，而是采用一种s2geometry内定的一种平面坐标。
综上，采用KDTree索引+UTM坐标是一种更为方便与高效的组合。
update 2020年7月17日09:32:50
最近邻搜索
上面方法构造的空间索引，是不支持最近邻搜索的。因此，我们构建s2ShapeIndex索引，这是s2geometry提供的一种内存空间索引，支持最近邻搜索。这就需要我们在程序启动时，把数据加载到内存里，再构建内存空间索引。暂时没有找到s2geometry最近邻搜索的其他方法。
以下原文：
在之前的文章，使用sqlite3+spatialte+wxsqlite3的方案实现了一个地图数据查询的接口。后来基于性能和数据处理灵活度的考虑，对接口库进行了重构，改为使用sqlite3+s2geometry+protobuf。
这里简单介绍一下方案
开始
总体分为两步，1. 数据导入 2. 数据检索
1. 数据导入
- 设计高精度地图数据protobuf的格式，可以参考apollo 的map模块。
- 拿到原始地图数据，格式可能是mif/shp 等。用GDAL加载数据，解析成protobuf的message。
- 使用s2gemetry对message构建空间索引。将空间索引和message的id关联，存储至表A
- message序列化后存储至表B
2. 数据检索
- 空间检索范围作为入参。
- 再次使用s2gemetry计算空间检索范围内的索引值。利用s2geometry空间索引计算方法，再结合表A和表B，即能够空间范围内取得message数据。
结束
优化：
- 可以在程序启动时将索引表 表A 的内容提前加载到内存中。
- 使用s2geometry生成更细化的空间索引，空间换取时间。
