0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

地図アプリの作り方 --Geohash--

Posted at

なぜGeohashが必要なのか

地図上で検索してピンを立てる機能を作るのに必要

image.png

Geohash超概要

Geo: 地理情報(緯度経度)
Hash: 文字列に変換

つまり、緯度経度を文字列に変換したもの

検索システムの愚直な実装

愚直に検索システムを実装することを考える。
このような構成のテーブルを想定する。

image.png

地図の表示地点に近い店舗をSQLで検索する。

  • 地図表示地点の緯度経度は map_center_lat, map_center_lng とする
  • 表示領域は -Δlat ~ Δlat, -Δlng ~ Δlng とする

SELECT * FROM RESTAURANT
WHERE
    map_center_lat > (lat - delta_lat) -- 緯度絞り込み1
    AND map_center_lat < (lat + delta_lat) -- 緯度絞り込み2
    AND map_center_lng > (lng - delta_lng) -- 経度絞り込み1
    AND map_center_lng < (lng + delta_lng) -- 緯度絞り込み2
    -- 今回は地理情報処理の話なので店舗の検索は省略

課題

  • 条件式が4つ必要
  • 範囲を絞り込むΔlat, Δlngが感覚的にわかりにくい

Geohashを使って検索システムを実装する

このような構成のテーブルを想定する。

image.png

地図の表示地点に近い店舗をSQLで検索する。

  • 地図表示地点の緯度経度をエンコードしたものを map_geohash とする
SELECT * RESTAURANT
WHERE geohash = map_geohash

これだけで地図に表示されている座標のGeohashと同じ、つまり近い場所にあるものを検索することができる。
Geohashの桁数を落として検索すれば検索範囲を広げることができる。

実装して動かしてみる。

mappp.gif

Geohash 計算方法

1. 緯度経度を二進数に変換

緯度は -90 ~ 90 のレンジがあるので、このレンジを二分探索する。
-90 ~ 90 の中間は0, ターゲットの値が右にあるので1桁目は 1 -- ①
0 ~ 90 の中間は45, ターゲットの値が左にあるので2桁目は 0 -- ②
必要な桁数まで繰り返す

タイトルなし.png

つまり、桁が増えるごとに精度が倍々になる。
経度も同様の方法で算出する。

2. 二進数の緯度経度をミックス

二進数緯度と二進数経度をミックスして一つにする。
緯度は奇数ビット、経度は偶数ビット

タイトルなし2.png

3. Base32 でエンコーディング

2でミックスした二進数を5ビットずつに区切ってBase32でエンコーディングする

011100001011010

01110 / 00010 / 11010

OC2

image.png
ref: RFC3548 https://datatracker.ietf.org/doc/html/rfc3548

Geohash のエレガントさ

  • 「ある座標に近いものを検索する」という複雑な問題を「同じ文字列を検索する」という単純な問題に置き換えることができる
  • 検索文字列を短くすれば広範囲、長くすれば狭い範囲の検索ができる
    • 感覚的にわかりやすい
  • Geohashにインデックスを貼ることで検索の高速化ができる
  • 緯度経度表現より桁数が短くなる
    • 東京都庁
    • 35.6896068,139.6891424
    • xn7749ke

ちなみに、GoogleではPlus codeというジオエンコーディングが用いられており、これはGeohashと似たような性質を持つ。

image.png

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?