🗾

GoでGeometryを扱う

2023/05/30に公開

株式会社CastingONE でソフトウェアエンジニアをしている @takashabe です。普段はHR領域のSaaSをGoで書いています。
今回はサービス成長に伴い、マップUIから求人を検索できる機能のスケーラビリティ改善を行ったのでその紹介をしたいと思います。

背景

各テナント(求人を紹介する会社様)が求職者に公開できる求人数がざっと100倍くらいになりました。求職者の方はその求人をマップ上から探せるような機能です。

以下がその表示サンプルですが、マップ上の近しい場所にある求人はまとめて表示され、単一で表示できるものは付加情報を付けて表示するといったことをしています。

求人掲載サンプル

今回はこのマップに表示出来るオブジェクト数が単純に増えたという感じです。
これまではクライアントで処理出来る程度のオブジェクト数であったため、APIから公開求人を全件取得してクライアント側でオブジェクトをプロットしていくような設計でした。
しかし当然オブジェクト数が増えるとブラウザが耐えられないため、バックエンド側(Go)から画面に表示出来る分のオブジェクトのみを返すようにする必要がありました。

GoでGeometryを扱う

求人はマップに表示するための緯度経度情報を持っています。そのためクライアント側の座標周辺に位置する求人を良い感じに返せれば良さそうです。

GoでGeometryを扱うためのライブラリはいくつか存在しますが、5分くらいググったところ最も使いやすそうなものは paulmach/orb でした。

PointやBound, PolygonなどGeometryの表現で使用するオブジェクトは大体対応しており、各種オブジェクトから相互に変換したりGeoJSONの出力ができたりと試行錯誤しながら実装するのが大変やりやすかったです。
今回はクライアント上で表示される画面(矩形)の範囲を元に、その範囲に属する求人を返したいので、BoundからGeoJSONでデバッグする例を見てみましょう。

func bound() {
    // 大体皇居周辺の座標
    nePoint := orb.Point{139.7809654260254, 35.698836016401685}
    swPoint := orb.Point{139.7468906427002, 35.67771329985728}

    bound := orb.MultiPoint{nePoint, swPoint}.Bound()

    c := geojson.NewFeatureCollection()
    f := geojson.NewFeature(bound)
    f.Properties["name"] = "皇居周辺"
    c.Append(f)
    b, _ := c.MarshalJSON()
    println(string(b))
    // => {"features":[{"type":"Feature","geometry":{"type":"Polygon","coordinates":[[[139.7809654260254,35.698836016401685],[139.7468906427002,35.698836016401685],[139.7468906427002,35.67771329985728],[139.7809654260254,35.67771329985728],[139.7809654260254,35.698836016401685]]]},"properties":{"name":"皇居周辺"}}],"type":"FeatureCollection"}
}

ここで得られたGeoJSONを https://geojson.io に食わせると以下のようになります。

boundのgeojson例

基本的にはこのように基準となる座標を与え、意図する領域を描画することができるかGeoJSONで確認しつつ実装を進めていきました。

タイルごとにクラスタリングする

画面全体をカバーするBoundは出来ましたが、より実用的なアプリケーションを作るために地図上の右上にはN個の求人があり、左下にはM個の求人がある、のようにクラスタリングして表示したいところです。

ここでは全体のBoundを元に、そこに含まれるタイルごとに求人がいくつ含まれるかという方針で実装しました。

https://learn.microsoft.com/ja-jp/azure/azure-maps/zoom-levels-and-tile-grid

アイデアとしては以下のように全体のBoundに含まれるタイルを抽出する感じです。

func tiles() {
    nePoint := orb.Point{139.7809654260254, 35.698836016401685}
    swPoint := orb.Point{139.7468906427002, 35.67771329985728}
    zoom := maptile.Zoom(14)

    base := orb.MultiPoint{nePoint, swPoint}.Bound()

    tiles := []orb.Bound{}
    minTile := maptile.At(base.Min, zoom)
    maxTile := maptile.At(base.Max, zoom)
    minX, minY := float64(minTile.X), float64(minTile.Y)
    maxX, maxY := float64(maxTile.X), float64(maxTile.Y)
    for x := math.Min(minX, maxX); x <= math.Max(minX, maxX); x++ {
        for y := math.Min(minY, maxY); y <= math.Max(minY, maxY); y++ {
            // zoomレベルを元にタイルを作成し、そのタイルが全体のBoundに含まれれば対象タイルとする
            tb := maptile.New(uint32(x), uint32(y), zoom).Bound()
            if !containBoundAny(base, tb) {
                continue
            }
            tiles = append(tiles, tb)
        }
    }

    c := geojson.NewFeatureCollection()
    for _, t := range tiles {
        c.Append(geojson.NewFeature(t))
    }
    b, _ := c.MarshalJSON()
    println(string(b))
    // => {"features":[{"type":"Feature","geometry":{"type":"Polygon","coordinates":[[[139.74609375,35.69299463209881],[139.76806640625,35.69299463209881],[139.76806640625,35.71083783530009],[139.74609375,35.71083783530009],[139.74609375,35.69299463209881]]]},"properties":null},{"type":"Feature","geometry":{"type":"Polygon","coordinates":[[[139.74609375,35.67514743608467],[139.76806640625,35.67514743608467],[139.76806640625,35.69299463209881],[139.74609375,35.69299463209881],[139.74609375,35.67514743608467]]]},"properties":null},{"type":"Feature","geometry":{"type":"Polygon","coordinates":[[[139.76806640625,35.69299463209881],[139.7900390625,35.69299463209881],[139.7900390625,35.71083783530009],[139.76806640625,35.71083783530009],[139.76806640625,35.69299463209881]]]},"properties":null},{"type":"Feature","geometry":{"type":"Polygon","coordinates":[[[139.76806640625,35.67514743608467],[139.7900390625,35.67514743608467],[139.7900390625,35.69299463209881],[139.76806640625,35.69299463209881],[139.76806640625,35.67514743608467]]]},"properties":null}],"type":"FeatureCollection"}
}

このGeoJSONでは以下のような出力が得られました。

tilesのgeojson例

あとはこの得られたタイルを元にDBなりに問い合わせて、そのタイルに含まれる求人を引くようにすれば良さそうです。orbではDBに渡すための引数に変換してくれるwktパッケージがあるのでそれを用います。
MySQLでは以下のような感じになります。

db, _ := sqlx.ConnectContext(context.Background(), "mysql", "...")
for _, t := range tiles {
    rows, err := db.NamedQuery(`
        SELECT *
        FROM jobs
        AND ST_Within(
            ST_GeomFromText(concat('POINT(', longitude, ' ', latitude, ')'), 4326, 'axis-order=long-lat'),
            ST_GeomFromText(:polygon, 4326, 'axis-order=long-lat')
        )
        `,
        map[string]any{
            "polygon": wkt.MarshalString(t.ToPolygon()),
        },
    )
    // do something
    _ = rows
    _ = err
}

クラスタをタップして良い感じにズームする

ここまででクライアントの画面領域に合わせて、含まれるタイルごとに求人を返せるようになり大分良い感じになってきました。

最後に、クラスタリングされたオブジェクトをタップしたときにそのクラスタを画面いっぱいに表示できるようズームさせたいと思います。

ここでもタイルをベースに考えて、ズームレベルを増やしたときのタイルが画面表示領域に収まるかどうかを判定し、増加した分のズームレベルをベースにタイルを新たに作るということをしています。
タイル(orbのオブジェクト)を元に距離が取れるので、クライアントから受け取った画面表示領域の緯度経度をベースにpixel数を算出して良い感じに表示できるタイルを決定しています。

const maxZoomLevel = 22

func tileWithZoom() {
    nePoint := orb.Point{139.7809654260254, 35.698836016401685}
    swPoint := orb.Point{139.7468906427002, 35.67771329985728}
    zoom := maptile.Zoom(14)

    base := orb.MultiPoint{nePoint, swPoint}.Bound()

    // 画面領域に収まるzoom levelでタイルを作る
    nb, ok := nextZoomBound(base, zoom)
    if ok {
        for {
            // これ以上zoom出来ない
            if maxZoomLevel <= zoom {
                break
            }

            currentZoomTile := maptile.At(base.Center(), zoom).Bound()
            if containBoundSize(nb, currentZoomTile) {
                break
            }
            zoom = zoom + 1
        }
    }

    // 決定されたzoomを元にtilesを生成する
}

// zoom levelごとの表示できるメートル/pixel定義. 緯度により決定される
var meterPixelZoom = map[int]float64{
    ...
    15: 3.660,
    16: 1.830,
    17: 0.915,
    18: 0.457,
    ...
}

func nextZoomBound(b orb.Bound, currentZoom maptile.Zoom) (_ orb.Bound, ok bool) {
    if currentZoom >= maxZoomLevel {
        return orb.Bound{}, false
    }

    // 現在のboundsの辺とzoom levelからpixel概算値を出す
    xLs := orb.LineString{b.LeftTop(), orb.Point{b.Right(), b.Top()}}
    yLs := orb.LineString{b.LeftTop(), orb.Point{b.Left(), b.Bottom()}}
    xDistance := geo.Distance(xLs[0], xLs[1])
    yDistance := geo.Distance(yLs[0], yLs[1])
    xPixel := xDistance / meterPixelZoom[int(currentZoom)]
    yPixel := yDistance / meterPixelZoom[int(currentZoom)]

    // pixel値とメートル/pixel定数を元に次のzoom levelでのboundsを出す
    nextZoom := currentZoom + 1
    nePoint := geo.PointAtBearingAndDistance(xLs[0], geo.Bearing(xLs[0], xLs[1]), xPixel*meterPixelZoom[int(nextZoom)])
    swPoint := geo.PointAtBearingAndDistance(yLs[0], geo.Bearing(yLs[0], yLs[1]), yPixel*meterPixelZoom[int(nextZoom)])
    return orb.MultiPoint{b.LeftTop(), nePoint, swPoint, {nePoint.X(), swPoint.Y()}}.Bound(), true
}

// containBoundSize baseの面積にtaregetが完全に含まれるかどうか
func containBoundSize(base, target orb.Bound) bool {
    baseXl := geo.Distance(base.LeftTop(), orb.Point{base.Right(), base.Top()})
    targetXl := geo.Distance(target.LeftTop(), orb.Point{target.Right(), target.Top()})
    if baseXl < targetXl {
        return false
    }

    baseYl := geo.Distance(base.LeftTop(), orb.Point{base.Left(), base.Bottom()})
    targetYl := geo.Distance(target.LeftTop(), orb.Point{target.Left(), target.Bottom()})
    return baseYl > targetYl
}

まとめ

GoでGeometryを扱うためのライブラリ paulmach/orb の紹介とコードサンプルを紹介しました。
全体的にタイルなどのオブジェクトをゴニョゴニョするコードが多いので適宜GeoJSONを使ったデバッグが出来ることで非常に捗りました
またここでは紹介していないですが、クライアント側と繋いだときにレスポンスの座標範囲を塗りつぶしてプロットするなどデバッグしやすいようにしておくと便利でした。

いつもの

株式会社CastingONE ではGoでGeometryを扱いたいソフトウェアエンジニアを募集しています。もし興味があればTwitterからでも構わないのでお気軽にご連絡ください!

https://www.wantedly.com/projects/1130967

Discussion