go - 将 golang S2 几何库与 dynamodb 结合使用

Question

我正在寻找移植 dynamo-geo.js 的一部分库到 golang，以便查询距离给定点最近的点(存储在 DyanmoDB 中)。

查询radius是理想的，但如果通过 rectangle 查询是一种更简单的算法，我对此也很满意。

这是我想出的按半径查询的代码，但我似乎无法获得覆盖单元格的非空列表。

我的算法有什么问题？

// Query a circular area constructed by a center point and its radius.
// @see https://github.com/rh389/dynamodb-geo.js/blob/6c388b9070014a096885e00fff6c3fc933d9853f/src/GeoDataManager.ts#L229
func queryRadius(lat float64, lng float64, radiusMeters float64) (error) {
    earthRadiusMeters := 6367000.0

    // Step1: Get the bounding region (rectangle) from the center and the radius
    // @see https://github.com/rh389/dynamodb-geo.js/blob/6c388b9070014a096885e00fff6c3fc933d9853f/src/s2/S2Util.ts#L23
    centerLatLng := s2.LatLngFromDegrees(lat, lng)

    latReferenceUnit := 1.0
    if lat > 0.0 {
        latReferenceUnit = -1.0
    }
    latReferenceLatLng := s2.LatLngFromDegrees(lat+latReferenceUnit, lng)

    lngReferenceUnit := 1.0
    if lng > 0.0 {
        lngReferenceUnit = -1.0
    }
    lngReferenceLatLng := s2.LatLngFromDegrees(lat, lng+lngReferenceUnit)

    latForRadius := radiusMeters / centerLatLng.Distance(latReferenceLatLng).Radians() * earthRadiusMeters
    lngForRadius := radiusMeters / centerLatLng.Distance(lngReferenceLatLng).Radians() * earthRadiusMeters

    minLatLng := s2.LatLngFromDegrees(lat-latForRadius, lng-lngForRadius)
    maxLatLng := s2.LatLngFromDegrees(lat+latForRadius, lng+lngForRadius)

    boundingRect := s2.RectFromLatLng(minLatLng)
    boundingRect = boundingRect.AddPoint(maxLatLng)

    // Step2: Compute the CellIDs for the region we want to cover.
    // defaults per https://github.com/vekexasia/nodes2-ts/blob/1952d8c1f6cb4a862731ace2d5f74d472ec22e55/src/S2RegionCoverer.ts#L101
    rc := &s2.RegionCoverer{MaxLevel: 30, MaxCells: 8, LevelMod: 1}
    r := s2.Region(boundingRect.CapBound())
    coveringCells := rc.Covering(r)

    for _, c := range coveringCells {
        log.WithFields(log.Fields{
            "Covering Cell": c,
        }).Info("=>")
    }

    return nil
}

Answer 1

注意:这是对我的具体原始问题的答案，但是我一直无法找到我正在尝试解决的问题的完整解决方案(查询最近的点，存储在DyanmoDB，使用 S2 到达给定点)。如果/当我得到完整的解决方案时，我会更新这个答案。我目前被阻止 this issue 。任何帮助表示赞赏。

这是一个完整的 go 程序，它计算从点(以度为单位)和半径(以米为单位)的覆盖单元。

FWIW 从点和半径确定边界正方形的算法不是很准确。所以到Martin F用于提供边界框算法。

package main

import (
    "fmt"
    "math"
    "strconv"

    "github.com/golang/geo/s2"
)

const earthRadiusM = 6371000 // per https://nssdc.gsfc.nasa.gov/planetary/factsheet/earthfact.html
const hashLength = 8         // < 1km per https://github.com/rh389/dynamodb-geo.js/blob/master/test/integration/hashKeyLength.ts

func main() {
    lowPrefix := uint64(0)
    highPrefix := uint64(0)
    ctrLat := 52.225730 // Cambridge UK
    ctrLng := 0.149593

    boundingSq := squareFromCenterAndRadius(ctrLat, ctrLng, 500)
    fmt.Printf("\nBounding sq %+v\n", boundingSq)

    coveringCells := getCoveringCells(boundingSq)
    fmt.Printf("Covering Cells (%d):\n", len(coveringCells))

    for idx, cell := range coveringCells {
        // cell is the UUID of the center of this cell
        fullHash, hashPrefix := genCellIntPrefix(cell)
        if 0 == idx {
            lowPrefix = hashPrefix
            highPrefix = hashPrefix
        } else if hashPrefix < lowPrefix {
            lowPrefix = hashPrefix
        } else if hashPrefix > highPrefix {
            highPrefix = hashPrefix
        }

        fmt.Printf("\tID:%19v uint64: %-19d prefix: %-10d Range: %-19d - %-19d\n", cell, fullHash, hashPrefix, uint64(cell.RangeMin()), uint64(cell.RangeMax()))
    }

    fmt.Printf("\tPrefix Range from loop: %-10d - %-10d\n", lowPrefix, highPrefix)

    // TODO: Assuming covering cells are sorted.  Correct assumption?
    _, lowPrefix = genCellIntPrefix(coveringCells[0].RangeMin())
    _, highPrefix = genCellIntPrefix(coveringCells[len(coveringCells)-1].RangeMax())

    fmt.Printf("\tPrefix Range direct:    %-10d - %-10d\n", lowPrefix, highPrefix)
}

// Get bounding box square from center point and radius
// Boundnig box is not extremely accurate to the radiusMeters passed in
// @see https://gis.stackexchange.com/questions/80809/calculating-bounding-box-coordinates-based-on-center-and-radius
func squareFromCenterAndRadius(centerLatDegrees float64, centerLngDegrees float64, radiusMeters float32) s2.Rect {
    latLng := s2.LatLngFromDegrees(centerLatDegrees, centerLngDegrees)

    deltaLng := float64(360 * radiusMeters / earthRadiusM) //Search Radius, difference in lat
    deltaLat := deltaLng * math.Cos(latLng.Lng.Radians())  //Search Radius, difference in lng

    lowerLeftLatDeg := centerLatDegrees - deltaLat
    lowerLeftLngDeg := centerLngDegrees - deltaLng
    lowerLeft := s2.LatLngFromDegrees(lowerLeftLatDeg, lowerLeftLngDeg) // AKA s2.Rect.Lo

    upperRightLatDeg := centerLatDegrees + deltaLat
    upperRightLngDeg := centerLngDegrees + deltaLng
    upperRight := s2.LatLngFromDegrees(upperRightLatDeg, upperRightLngDeg) // AKA s2.Rect.Hi

    boundingSquare := s2.RectFromLatLng(lowerLeft).AddPoint(upperRight)

    return boundingSquare
}

func getCoveringCells(boundingRect s2.Rect) s2.CellUnion {
    // defaults per https://github.com/vekexasia/nodes2-ts/blob/1952d8c1f6cb4a862731ace2d5f74d472ec22e55/src/S2RegionCoverer.ts#L101
    rc := &s2.RegionCoverer{
        MinLevel: 12, // 3km^2 per http://s2geometry.io/resources/s2cell_statistics
        MaxLevel: 20, // 46m^2 per http://s2geometry.io/resources/s2cell_statistics
        MaxCells: 8,
        LevelMod: 1,
    }
    return rc.Covering(boundingRect)
}

func genCellIntPrefix(cell s2.CellID) (hash uint64, prefix uint64) {
    hash = uint64(cell)
    geohashString := strconv.FormatUint(hash, 10)
    denominator := math.Pow10(len(geohashString) - hashLength)
    prefix = hash / uint64(denominator)
    return
}

我绝不是GIS专家，因此欢迎任何改进建议/意见。