Maxkit: Geospatial Index in MongoDB

MongoDB 自 2.6 版開始就支援儲存座標點的欄位，並能為該欄位建立 Geospatial Indexes，提供使用者快速搜尋附近的座標點資料的資料查詢功能。例如最簡單的應用：找到我附近的夥伴或是找到家裡附近的餐廳。

座標點 [longitude, latitude]

座標點的資料是兩個浮點數字組成的，先寫 longitude 經度，再寫 latitude 緯度，在思考座標點資料時，必須要用平面座標來看，原點在正中央，x軸往右為正數，y軸往上為正數，這跟跟矩陣的元素表示方法不同，先列後行。

[longitude, latitude]

基本 2d 平面查詢

要測試最基本的平面查詢，我們先產生 100 個座標點的測試資料，其實座標點資料就只是單純的兩個數字而已，重要的是，在建立 index 時，要指定用 2d 的 index：

db.ex.drop()
for( var i=0; i<100; i++ ) {
    db.ex.insert({pos:[i%10, Math.floor(i/10)]})
}

db.ex.ensureIndex({pos:"2d"})

用 $near 查詢時，回傳的資料點會依照距離遠近的順序傳送回來。

> db.ex.find({pos:{$near:[5,5]}})
{ "_id" : ObjectId("565e634fbd3fd37d48c0a691"), "pos" : [ 5, 5 ] }
{ "_id" : ObjectId("565e634fbd3fd37d48c0a690"), "pos" : [ 4, 5 ] }
{ "_id" : ObjectId("565e634fbd3fd37d48c0a69b"), "pos" : [ 5, 6 ] }
{ "_id" : ObjectId("565e634fbd3fd37d48c0a687"), "pos" : [ 5, 4 ] }
{ "_id" : ObjectId("565e634fbd3fd37d48c0a692"), "pos" : [ 6, 5 ] }
{ "_id" : ObjectId("565e634fbd3fd37d48c0a686"), "pos" : [ 4, 4 ] }
.....

以下這個圖形將所有座標點都以一個圓點表示，原點[0,0]位於左下角。

以下是有距離範圍的查詢，但回傳的資料點，並不保證依照距離由小到大排列

position:{$within:[$center, $box, $ploygon, $centerSphere]}

首先是 $center 的測試，我們測試一個半徑為 2 的圓形涵蓋的範圍：

> db.ex.find( {pos:{$within:{$center:[[5,5],2]}}} , {_id:0} )
{ "pos" : [ 4, 4 ] }
{ "pos" : [ 3, 5 ] }
{ "pos" : [ 4, 5 ] }
{ "pos" : [ 5, 3 ] }
{ "pos" : [ 5, 4 ] }
{ "pos" : [ 5, 5 ] }
{ "pos" : [ 4, 6 ] }
{ "pos" : [ 5, 6 ] }
{ "pos" : [ 5, 7 ] }
{ "pos" : [ 6, 4 ] }
{ "pos" : [ 6, 5 ] }
{ "pos" : [ 7, 5 ] }
{ "pos" : [ 6, 6 ] }

$box 是一個矩形

> db.ex.find( {pos:{$within:{$box:[[5,5],[6,6]]}}} , {_id:0} )
{ "pos" : [ 5, 5 ] }
{ "pos" : [ 5, 6 ] }
{ "pos" : [ 6, 5 ] }
{ "pos" : [ 6, 6 ] }

$polygon 則是一個多邊形

> db.ex.find( {pos:{$within:{$polygon:[[3,4],[5,7], [7,3]]}}} , {_id:0} )
{ "pos" : [ 3, 4 ] }
{ "pos" : [ 4, 4 ] }
{ "pos" : [ 4, 5 ] }
{ "pos" : [ 5, 4 ] }
{ "pos" : [ 5, 5 ] }
{ "pos" : [ 5, 6 ] }
{ "pos" : [ 5, 7 ] }
{ "pos" : [ 6, 4 ] }
{ "pos" : [ 7, 3 ] }
{ "pos" : [ 6, 5 ] }

Geospatial Indexes

剛剛的 2d 查詢，看起來還蠻簡單的，但 MongoDB 的 Geospatial Indexes 不光只支援這個功能而已。

MongoDB 支援兩種平面的模型 surface type 1. Spherical: 2dsphere index 座標點是放在像地球一樣的球面上，由於是球面的關係，距離跟相對關係的計算，跟一般的平面座標是不同的 2. Flat: 2d index 傳統的平面座標

如果是一般的 2d index，座標點的儲存只支援 legacy coordinate pairs的表示方式，也就是 [x,y]，前面是 longitude 經度，後面是 latitude 緯度。

但如果是 2dsphere index，除了支援 legacy coordinate pairs 的資料外，還可以用 GeoJSON object 的表示方式儲存，預設是以 WGS84 datum，也就是 Degrees, Minutes, Seconds 的地理位置表示方式。

WGS 84 座標點表示系統有五種，可以用 PGC Coordinate Converter 進行轉換的計算，比較常見的有兩種 DMS 及 DD，但要注意的是 GeoJSON 預設是先寫緯度，再寫經度，但 MongoDB 卻是前面是 longitude 經度，後面是 latitude 緯度。

DMS (Degrees, Minutes, Seconds) ex: 24° 15' 28.0800" N, 120° 53' 36.6000" E
DD (Decimal Degrees) ex: 24.2578, 120.8935

GeoJSON 是以 JSON 表示地理資料結構的格式，由兩個部份組成：

type: 有以下這些類型 Point, LineString, Polygon, MultiPoint, MultiLineString, and MultiPolygon, GeometryCollection
coordinates 是這個類型資料的座標點的集合

我們可以透過 http://geojsonlint.com/ 測試 GeoJSON，並將結果顯示在地圖上。

// Point
{
  "type": "Point",
  "coordinates": [
    120.8935,  
    24.2578 
  ]
}

// LineString
{
  "type": "LineString",
  "coordinates": [
    [120.7000,24.2000],
    [120.6900,24.1900],
    [120.6815,24.1833],
    [120.5900,24.1500]
  ]
}

透過 GeoJSON Editor 用線跟多邊形，把文心森林公園框起來：

{
  "type" : "GeometryCollection",
  "geometries" : [
    {
      "type" : "Polygon",
      "coordinates": [
          [
            [
              120.64390238374472,
              24.146822125175643
            ],
            [
              120.64660605043173,
              24.146743804632557
            ],
            [
              120.64653094857931,
              24.14385570109112
            ],
            [
              120.64319428056479,
              24.144188570589225
            ],
            [
              120.64390238374472,
              24.146822125175643
            ]
          ]
        ]
    },
    {
      "type" : "LineString",
      "coordinates": [
          [
            120.64390238374472,
            24.14681233511038
          ],
          [
            120.64656313508749,
            24.146753594703075
          ],
          [
            120.64652021974325,
            24.14385570109112
          ],
          [
            120.64322646707296,
            24.144188570589225
          ],
          [
            120.64390238374472,
            24.14681233511038
          ]
        ]
     }
  ]
}

geospatial query operators

geospatial index 有兩種，geospatial index 不能當作 shard key index，而且在 sharded collection 中，不能使用 $near, $nearSphere，可以用 $geoNear aggregation 取代。

2d 支援平面幾何的計算 legacy coordinate pairs [longitude, latitude]
2dsphere 支援球面的計算可儲存 GeoJSON 或是 legacy coordinate pairs

MongoDB 的 Query Selectors 有以下這4種

$geoWithin Inclusion 在 GeoJSON geomerty 的裡面的圖形，2d 及 2dsphere indexes 都有支援
$geoIntersects Intersect 跟 GeoJSON geomerty 的相交的圖形, 只有 2dsphere index 支援
$near Proximity 接近某個點的 geospatial objects，2d 及 2dsphere indexes 都有支援
$nearSphere Proximity 在球面上，接近某個點的 geospatial objects，2d 及 2dsphere 都支援

Geometry Specifiers 有以下這幾種

$geometry 以 GeoJSON 格式指定的 geometry
$minDistance 最短距離，用在 $near, $nearSphere，只能用在 2dsphere index
$maxDistance 最長距離，用在 $near, $nearSphere, 2d 及 2dsphere 都支援
$center 圓形，用在 $geoWithin queries 裡面, 2d 支援
$centerSphere 圓形，用在 $geoWithin queries 裡面，可用 [x,y] 或 GeoJSON 格式，2d 及 2dsphere 都支援
$box 矩形，用在 $geoWithin queries 裡面, 2d 支援
$polygon 用 [x,y] 描述的多邊形，用在 $geoWithin queries 裡面, 2d 支援