地图数据检索接口-地图引擎

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. 数据检索

优化：

实现kNN算法时，最简单的实现方法就是线性扫描，正如我们上一章节内容介绍的一样->K近邻算法 ，需要计算输入实例与每一个训练样本的距离。当训练集很大时，会非常耗时。

为了提高kNN搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数，KD-Tree就是其中的一种方法。

K维空间数据集

其中

随机生成 13 个点作为我们的数据集

首先先沿 x 坐标进行切分，我们选出 x 坐标的中位点，获取最根李桥漏部节点的坐标

并且按照该点的x坐标将空间进行切分，所有 x 坐标小于 6.27 的数据用于构建左分支，x坐标大于 6.27 的点用于哪烂构建右分支。

在下一步中 ,对应 y 轴，左右两边再按照 y 轴的排序进行切分，中位点记载于左右枝的节点。得到下面的树，左边的 x 是指这该层的节点都是沿 x 轴进行分割的。

空间的切分如下

下一步中 ，对应 x 轴，所以下面再按照 x 坐标进行排序和切分，有

最后只剩下了叶子结点，就此完成了 kd 树的构造。

输入：已构造的kd树，目标点x

输出：x的k个最近邻集合L

KD-Tree的平均时间复杂度为 ，N为训练样本的数量。

KD-Tree试用于训练样本数远大于空间维度的k近邻搜索。当空间维数接近训练样本数时，他的效率会迅速下降，几乎接近线性扫描。

设我们想查询的点为 p=(−1,−消毕5)，设距离函数是普通的距离，我们想找距离目标点最近的 k=3 个点。如下：

首先我们按照构造好的KD-Tree，从根结点开始查找

和这个节点的 x 轴比较一下，p 的 x 轴更小。因此我们向左枝进行搜索：

接下来需要对比 y 轴

p 的 y 值更小，因此向左枝进行搜索：

这个节点只有一个子枝，就不需要对比了。由此找到了叶子节点 (−4.6,−10.55)。

在二维图上是蓝色的点

此时我们要执行第二步，将当前结点插入到集合L中，并记录下 L=[(−4.6,−10.55)]。访问过的节点就在二叉树上显示为被划掉的好了。

然后执行第三步，不是最顶端节点。我回退。上面的结点是 (−6.88,−5.4)。

执行 3a，因为我们记录下的点只有一个，小于 k=3，所以也将当前节点记录下，插入到集合L中，有 L=[(−4.6,−10.55),(−6.88,−5.4)].。 因为当前节点的左枝是空的，所以直接跳过，继续回退，判断不是顶部根节点

由于还是不够三个点，于是将当前点也插入到集合L中，有 L=[(−4.6,−10.55),(−6.88,−5.4),(1.24,−2.86)]。

此时发现，当前节点有其他的分枝，执行3b，计算得出 p 点和 L 中的三个点的距离分别是 6.62, 5.89, 3.10，但是 p 和当前节点的分割线的距离只有 2.14，小于与 L 的最大距离：

因此，在分割线的另一端可能有更近的点。于是我们在当前结点的另一个分枝从头执行步骤1。好，我们在红线这里：

此时处于x轴切分，因此要用 p 和这个节点比较 x 坐标:

p 的 x 坐标更大，因此探索右枝 (1.75,12.26)，并且发现右枝已经是最底部节点，执行步骤2与3a。

经计算，(1.75,12.26) 与 p 的距离是 17.48，要大于 p 与 L 的距离，因此我们不将其放入记录中。

然后 回退，判断出不是顶端节点，往上爬。

执行3a，这个节点与 p 的距离是 4.91，要小于 p 与 L 的最大距离 6.62。

因此，我们用这个新的节点替代 L 中离 p 最远的 (−4.6,−10.55)。

然后3b，我们比对 p 和当前节点的分割线的距离

这个距离小于 L 与 p 的最大距离，因此我们要到当前节点的另一个枝执行步骤1。当然，那个枝只有一个点。

计算距离发现这个点离 p 比 L 更远，因此不进行替代。

然后回退，不是根结点，我们向上爬

这个是已经访问过的了，所以再向上爬

再爬

此时到顶点了 。所以完了吗？当然不，还要执行3b呢。现在是步骤1的回合。

我们进行计算比对发现顶端节点与p的距离比L还要更远，因此不进行更新。

然后计算 p 和分割线的距离发现也是更远。

因此也不需要检查另一个分枝。

判断当前节点是顶点，因此计算完成！输出距离 p 最近的三个样本是 L=[(−6.88,−5.4),(1.24,−2.86),(−2.96,−2.5)]。

声明：此文章为本人学习笔记，参考于： https://zhuanlan.zhihu.com/p/23966698

---