KDTree+UTM

update 時間：2020，7，25
在自動駕駛平臺中，高精地圖數(shù)據(jù)坐標(biāo)通常采用平面坐標(biāo)，如UTM，目的是方便坐標(biāo)的轉(zhuǎn)換以及幾何計算。
因此，地圖數(shù)據(jù)模塊為了能夠方便的提供給其他模塊使用，建議輸出UTM或者車身坐標(biāo)系。
在Apollo中，Map數(shù)據(jù)源數(shù)據(jù)采用UTM坐標(biāo)存儲，在程序啟動時會在內(nèi)存中構(gòu)建KDTree空間索引。
KDTree空間索引支持快速的最近鄰搜索，并且可以直接利用平面坐標(biāo)構(gòu)建KDTree。這為后續(xù)坐標(biāo)計算提供了便利。
而s2geometry，雖然同樣支持平面坐標(biāo)索引，但其平面坐標(biāo)單位并非是“meter”，而是采用一種s2geometry內(nèi)定的一種平面坐標(biāo)。
綜上，采用KDTree索引+UTM坐標(biāo)是一種更為方便與高效的組合。

update 2020年7月17日09:32:50

最近鄰搜索

上面方法構(gòu)造的空間索引，是不支持最近鄰搜索的。因此，我們構(gòu)建s2ShapeIndex索引，這是s2geometry提供的一種內(nèi)存空間索引，支持最近鄰搜索。這就需要我們在程序啟動時，把數(shù)據(jù)加載到內(nèi)存里，再構(gòu)建內(nèi)存空間索引。暫時沒有找到s2geometry最近鄰搜索的其他方法。
以下原文：

在之前的文章，使用sqlite3+spatialte+wxsqlite3的方案實現(xiàn)了一個地圖數(shù)據(jù)查詢的接口。后來基于性能和數(shù)據(jù)處理靈活度的考慮，對接口庫進(jìn)行了重構(gòu)，改為使用sqlite3+s2geometry+protobuf。
這里簡單介紹一下方案

開始

總體分為兩步，1. 數(shù)據(jù)導(dǎo)入 2. 數(shù)據(jù)檢索

1. 數(shù)據(jù)導(dǎo)入

1. 設(shè)計高精度地圖數(shù)據(jù)protobuf的格式，可以參考apollo 的map模塊。
2. 拿到原始地圖數(shù)據(jù)，格式可能是mif/shp 等。用GDAL加載數(shù)據(jù)，解析成protobuf的message。
3. 使用s2gemetry對message構(gòu)建空間索引。將空間索引和message的id關(guān)聯(lián)，存儲至表A
4. message序列化后存儲至表B

2. 數(shù)據(jù)檢索

1. 空間檢索范圍作為入?yún)ⅰ?/li>
2. 再次使用s2gemetry計算空間檢索范圍內(nèi)的索引值。利用s2geometry空間索引計算方法，再結(jié)合表A和表B，即能夠空間范圍內(nèi)取得message數(shù)據(jù)。

結(jié)束

優(yōu)化：

1. 可以在程序啟動時將索引表 表A 的內(nèi)容提前加載到內(nèi)存中。
2. 使用s2geometry生成更細(xì)化的空間索引，空間換取時間。