このエントリはSmartDrive Advent Calendar 2019の一環です。
Google が2017年に出したS2というジオメトリ系のライブラリがあり、それのGo実装があるので遊んでみました。
ライブラリの公式サイト
s2geometry.io
Go言語での実装
github.com
ジオメトリライブラリにはその目的によってアルゴリズム や実装がいくつかあると思いますが、よく使われる用途というと、緯度経度の情報の検索容易性 を上げたりデータのサイズダウンを意図したものが多いと思います。この手のライブラリでは、日本だとgeohexをご存知の方は多いのではないでしょうか。geohex のようなGeohash系アルゴリズム の基本的な考え方は、地図上を多角形のタイルで隙間なく敷き詰め、そのタイルの大きさが小さければ小さいほど情報の精度が上がっていく、というものです。そしてそのタイルを使った操作によって、計算を単純化 して求めやすくします。
さてS2についてですが、敷き詰めるものは「Cell」と表現されていて、これは四角形で構成されています。また大きな特徴として、Cellは二次元の地図ではなく真円に対して投影されています。これらを総合して、ある程度計算量を落としてアルゴリズム 自体を簡易にしつつ、その上で球全体の歪みを極力少なくするという辺りを狙って設計されているそうです。
S2についての更に詳しい解説は、Misreading Chat #50「Geodesic Discrete Global Grid Systems」 をお聞きいただけますよう、どうぞ宜しくお願いします。
個人的にですが、S2の魅力はそうしたスケーラブルさだけでなく、API の豊富さにもあると思っています。そこで、良くありそうな事例を具体的な数字やコードを交えて一つご紹介したいと思います。
弊社の現在の所在地は日比谷のNTTビルにありますが、ここを中心としていくつかの周辺駅をピックアップしておきます。
今回は、「日比谷駅 」「有楽町駅」「銀座駅 」「東銀座駅 」「新橋駅」「内幸町駅」「虎ノ門駅 」「霞ケ関駅 」「桜田門駅 」を探索対象とし、ピンを立てた座標を利用します(ピンの位置はGoogleMapでの検索結果を利用したものです。。。)。
ここから周囲500m以内の駅をピックアップしたいなと思ったとき、先ずは RegionCoverer
というAPI を利用します。
このRegionCoverer
というのは、ある地図上に指定した図形に対して、その図形を確実に埋めるセルのリストを返すものです。ただこの時、セルの総個数やレベル(セルの大きさ)の範囲は固定しておく必要があります。ここで注意すべきなのは、得られたセルのリストによって構成されるエリアというのは、必ずもともと指定した図形よりオーバーサイズになります。そのため、指定したセルのレベルによっては、本来500m以上離れたポイントなのに検知される、ということがあり得ます。
セルのレベルを上げ、総数を増やせば限りなく指定した図形に漸近していくのです。。。
当然ながら、RegionCoverer
API には制限があり、無限にセル数やレベルを指定することはできません。
500mより大幅に大きいセルのレベルを指定するとこうなる
またこのように、あまりにセルを大きくしすぎるとミスヒット が増える要因にもなるので、ここはアプリケーションの計算量と相談しながら調整していく必要があります。
この辺がほどほどかな
ここまでのスクリーンショット は、Sidewalk Labsによるデモサイトを利用させていただきました。これ、S2の雰囲気を知るのにとても分かりやすいです。
s2.sidewalklabs.com
今回はCellレベルをmin, maxともに14に設定して進めてみたいと思います。勿論、maxをもっと上げてより精度の高いエリアを割り出すこともできます。下記のコードの方針は、
まずはRegionCovererによって取得できたCellリストのそれぞれのトーク ンと、探索対象の地点のCellレベル14のトーク ンを比較する。マッチするCellがあったら次の段階に進む
中心点(オフィス)と各探索対象地点の距離を求める。もしその距離が500m以内であれば [HIT!!!]
をつける
となっています。
https://play.golang.org/p/ZSKFlauQKOl
package main
import (
"fmt"
"github.com/golang/geo/s1"
"github.com/golang/geo/s2"
)
type station struct {
name string
latlng s2.LatLng
}
func toSpecifiedCell(ll s2.LatLng) s2.CellID {
return s2.CellFromLatLng(ll).ID().Parent(14 )
}
const earthRadius float64 = 6378137
func main() {
office := s2.LatLngFromDegrees(35.671262 , 139.757476 )
stations := []station{
{"Hibiya" , s2.LatLngFromDegrees(35.674867 , 139.759596 )},
{"Yurakucho" , s2.LatLngFromDegrees(35.674865 , 139.762818 )},
{"Ginza" , s2.LatLngFromDegrees(35.671706 , 139.764472 )},
{"Higashi-ginza" , s2.LatLngFromDegrees(35.670010 , 139.766721 )},
{"Shimbashi" , s2.LatLngFromDegrees(35.666456 , 139.758267 )},
{"Uchisaiwaicho" , s2.LatLngFromDegrees(35.669388 , 139.755331 )},
{"Onarimon" , s2.LatLngFromDegrees(35.660473 , 139.751265 )},
{"Toranomon" , s2.LatLngFromDegrees(35.670113 , 139.750109 )},
{"Kasumigaseki" , s2.LatLngFromDegrees(35.674789 , 139.751890 )},
{"Sakuradamon" , s2.LatLngFromDegrees(35.677265 , 139.751376 )},
}
officePoint := s2.PointFromLatLng(office)
officeCap := s2.CapFromCenterAngle(officePoint, s1.Angle(500 /earthRadius))
regionCover := s2.RegionCoverer{
MinLevel: 14 ,
MaxLevel: 14 ,
MaxCells: 16 ,
}
coverings := map [s2.CellID]struct {}{}
for _, cellID := range regionCover.Covering(officeCap) {
coverings[cellID] = struct {}{}
}
for _, st := range stations {
if _, exists := coverings[toSpecifiedCell(st.latlng)]; !exists {
continue
}
stPoint := s2.PointFromLatLng(st.latlng)
angle := officePoint.Distance(stPoint)
distance := angle.Radians() * earthRadius
hit := ""
if distance <= 500 {
hit = " [HIT!!!]"
}
fmt.Printf("[%s] distance: %f%s \n " , st.name, distance, hit)
}
}
上記の算出ロジックにより、オフィスから500m以内にある駅は内幸町駅(約285m)と日比谷駅 (約445m)だと分かりました!
今回はCap
を利用した円形の探索を行いましたが、矩形やポリゴンでの探索も可能になっています。なお、上記の出力結果から御成門駅 と桜田門駅 が含まれていませんが、これはRegionCoverer.Covering
メソッドの結果に含まれるCellIDにこの2つの駅が所属するCellIDが含まれてないので、事前に除外されているという構図です。
今回のように中心点や探索対象が全てオンメモリにいるのであれば、以下のようなコードで同様の探索も可能です。コード量としてはこちらの方が少なくなります。
(探索対象の駅の各地点がofficeを中心としたCapの中にいるかどうかをContainsPoint
メソッドによって直接判定しています)
https://play.golang.org/p/GZgk7a2csCj
スマートドライブではこんな感じで、地図関連のライブラリについても定期的に調査していきたいと思っています。
弊社もまた全職種募集しておりますので、是非お気軽にお声がけいただく!
smartdrive.co.jp