From e223750f02b5d487d0792086937ecd119730fd27 Mon Sep 17 00:00:00 2001 From: Justin Hwang Date: Fri, 6 Jun 2025 13:34:02 -0400 Subject: [PATCH 1/5] feat: Implement GridDisksUnsafe, GridDiskDistancesUnsafe, GridDiskDistancesSafe (#84) Implements remaining bindings for C library functions. This includes: - GridDisksUnsafe - GridDiskDistancesUnsafe - GridDiskDistancesSafe which are listed in the API Reference[0]. - 0: https://h3geo.org/docs/api/traversal --- README.md | 101 +++++++++++++++++++++++---------------------- h3.go | 119 +++++++++++++++++++++++++++++++++++++++++++++++++++++ h3_test.go | 98 ++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 267 insertions(+), 51 deletions(-) diff --git a/README.md b/README.md index 63d77a4..eb5e58c 100644 --- a/README.md +++ b/README.md @@ -82,55 +82,58 @@ func ExampleLatLngToCell() { ## Bindings -| C API | Go API | -| ---------------------------- | -------------------------------------------------- | -| `latLngToCell` | `LatLngToCell`, `LatLng#Cell` | -| `cellToLatLng` | `CellToLatLng`, `Cell#LatLng` | -| `cellToBoundary` | `CellToBoundary`, `Cell#Boundary` | -| `gridDisk` | `GridDisk`, `Cell#GridDisk` | -| `gridDiskDistances` | `GridDiskDistances`, `Cell#GridDiskDistances` | -| `gridRingUnsafe` | N/A | -| `polygonToCells` | `PolygonToCells`, `GeoPolygon#Cells` | -| `cellsToMultiPolygon` | `CellsToMultiPolygon` -| `degsToRads` | `DegsToRads` | -| `radsToDegs` | `RadsToDegs` | -| `greatCircleDistance` | `GreatCircleDistance* (3/3)` | -| `getHexagonAreaAvg` | `HexagonAreaAvg* (3/3)` | -| `cellArea` | `CellArea* (3/3)` | -| `getHexagonEdgeLengthAvg` | `HexagonEdgeLengthAvg* (2/2)` | -| `exactEdgeLength` | `EdgeLength* (3/3)` | -| `getNumCells` | `NumCells` | -| `getRes0Cells` | `Res0Cells` | -| `getPentagons` | `Pentagons` | -| `getResolution` | `Resolution` | -| `getBaseCellNumber` | `BaseCellNumber`, `Cell#BaseCellNumber` | -| `stringToH3` | `IndexFromString`, `Cell#UnmarshalText` | -| `h3ToString` | `IndexToString`, `Cell#String`, `Cell#MarshalText` | -| `isValidCell` | `Cell#IsValid` | -| `cellToParent` | `Cell#Parent`, `Cell#ImmediateParent` | -| `cellToChildren` | `Cell#Children` `Cell#ImmediateChildren` | -| `cellToCenterChild` | `Cell#CenterChild` | -| `compactCells` | `CompactCells` | -| `uncompactCells` | `UncompactCells` | -| `isResClassIII` | `Cell#IsResClassIII` | -| `isPentagon` | `Cell#IsPentagon` | -| `getIcosahedronFaces` | `Cell#IcosahedronFaces` | -| `areNeighborCells` | `Cell#IsNeighbor` | -| `cellsToDirectedEdge` | `Cell#DirectedEdge` | -| `isValidDirectedEdge` | `DirectedEdge#IsValid` | -| `getDirectedEdgeOrigin` | `DirectedEdge#Origin` | -| `getDirectedEdgeDestination` | `DirectedEdge#Destination` | -| `directedEdgeToCells` | `DirectedEdge#Cells` | -| `originToDirectedEdges` | `Cell#DirectedEdges` | -| `directedEdgeToBoundary` | `DirectedEdge#Boundary` | -| `cellToVertex` | `CellToVertex` | -| `cellToVertexes` | `CellToVertexes` | -| `vertexToLatLng` | `VertexToLatLng` | -| `isValidVertex` | `IsValidVertex` | -| `gridDistance` | `GridDistance`, `Cell#GridDistance` | -| `gridPathCells` | `GridPath`, `Cell#GridPath` | -| `cellToLocalIj` | `CellToLocalIJ` | -| `localIjToCell` | `LocalIJToCell` | +| C API | Go API | +|------------------------------|-----------------------------------------------------------| +| `latLngToCell` | `LatLngToCell`, `LatLng#Cell` | +| `cellToLatLng` | `CellToLatLng`, `Cell#LatLng` | +| `cellToBoundary` | `CellToBoundary`, `Cell#Boundary` | +| `gridDisk` | `GridDisk`, `Cell#GridDisk` | +| `gridDisksUnsafe` | `GridDisksUnsafe` | +| `gridDiskDistances` | `GridDiskDistances`, `Cell#GridDiskDistances` | +| `gridDiskDistancesSafe` | `GridDiskDistancesSafe`, `Cell#GridDiskDistancesSafe` | +| `gridDiskDistancesUnsafe` | `GridDiskDistancesUnsafe`, `Cell#GridDiskDistancesUnsafe` | +| `gridRingUnsafe` | `GridRingUnsafe`, `Cell#GridRingUnsafe` | +| `polygonToCells` | `PolygonToCells`, `GeoPolygon#Cells` | +| `cellsToMultiPolygon` | `CellsToMultiPolygon` | +| `degsToRads` | `DegsToRads` | +| `radsToDegs` | `RadsToDegs` | +| `greatCircleDistance` | `GreatCircleDistance* (3/3)` | +| `getHexagonAreaAvg` | `HexagonAreaAvg* (3/3)` | +| `cellArea` | `CellArea* (3/3)` | +| `getHexagonEdgeLengthAvg` | `HexagonEdgeLengthAvg* (2/2)` | +| `exactEdgeLength` | `EdgeLength* (3/3)` | +| `getNumCells` | `NumCells` | +| `getRes0Cells` | `Res0Cells` | +| `getPentagons` | `Pentagons` | +| `getResolution` | `Resolution` | +| `getBaseCellNumber` | `BaseCellNumber`, `Cell#BaseCellNumber` | +| `stringToH3` | `IndexFromString`, `Cell#UnmarshalText` | +| `h3ToString` | `IndexToString`, `Cell#String`, `Cell#MarshalText` | +| `isValidCell` | `Cell#IsValid` | +| `cellToParent` | `Cell#Parent`, `Cell#ImmediateParent` | +| `cellToChildren` | `Cell#Children` `Cell#ImmediateChildren` | +| `cellToCenterChild` | `Cell#CenterChild` | +| `compactCells` | `CompactCells` | +| `uncompactCells` | `UncompactCells` | +| `isResClassIII` | `Cell#IsResClassIII` | +| `isPentagon` | `Cell#IsPentagon` | +| `getIcosahedronFaces` | `Cell#IcosahedronFaces` | +| `areNeighborCells` | `Cell#IsNeighbor` | +| `cellsToDirectedEdge` | `Cell#DirectedEdge` | +| `isValidDirectedEdge` | `DirectedEdge#IsValid` | +| `getDirectedEdgeOrigin` | `DirectedEdge#Origin` | +| `getDirectedEdgeDestination` | `DirectedEdge#Destination` | +| `directedEdgeToCells` | `DirectedEdge#Cells` | +| `originToDirectedEdges` | `Cell#DirectedEdges` | +| `directedEdgeToBoundary` | `DirectedEdge#Boundary` | +| `cellToVertex` | `CellToVertex` | +| `cellToVertexes` | `CellToVertexes` | +| `vertexToLatLng` | `VertexToLatLng` | +| `isValidVertex` | `IsValidVertex` | +| `gridDistance` | `GridDistance`, `Cell#GridDistance` | +| `gridPathCells` | `GridPath`, `Cell#GridPath` | +| `cellToLocalIj` | `CellToLocalIJ` | +| `localIjToCell` | `LocalIJToCell` | ## CGO diff --git a/h3.go b/h3.go index 781762c..aaddb8b 100644 --- a/h3.go +++ b/h3.go @@ -230,7 +230,35 @@ func (c Cell) GridDisk(k int) ([]Cell, error) { return GridDisk(c, k) } +// GridDisksUnsafe produces cells within grid distance k of all provided origin +// cells. +// +// k-ring 0 is defined as the origin cell, k-ring 1 is defined as k-ring 0 and +// all neighboring cells, and so on. +// +// Outer slice is ordered in the same order origins were passed in. Inner slices +// are in no particular order. +// +// This does not call through to the underlying C.gridDisksUnsafe implementation +// as it is slightly easier to do so to avoid unnecessary type conversions. +func GridDisksUnsafe(origins []Cell, k int) ([][]Cell, error) { + out := make([][]Cell, len(origins)) + gridDiskSize := maxGridDiskSize(k) + for i := range origins { + inner := make([]C.H3Index, gridDiskSize) + errC := C.gridDiskUnsafe(C.H3Index(origins[i]), C.int(k), &inner[0]) + if err := toErr(errC); err != nil { + return nil, err + } + out[i] = cellsFromC(inner, true, false) + } + return out, nil +} + // GridDiskDistances produces cells within grid distance k of the origin cell. +// This method optimistically tries the faster GridDiskDistancesUnsafe first. +// If a cell was a pentagon or was in the pentagon distortion area, it falls +// back to GridDiskDistancesSafe. // // k-ring 0 is defined as the origin cell, k-ring 1 is defined as k-ring 0 and // all neighboring cells, and so on. @@ -260,6 +288,9 @@ func GridDiskDistances(origin Cell, k int) ([][]Cell, error) { } // GridDiskDistances produces cells within grid distance k of the origin cell. +// This method optimistically tries the faster GridDiskDistancesUnsafe first. +// If a cell was a pentagon or was in the pentagon distortion area, it falls +// back to GridDiskDistancesSafe. // // k-ring 0 is defined as the origin cell, k-ring 1 is defined as k-ring 0 and // all neighboring cells, and so on. @@ -271,6 +302,94 @@ func (c Cell) GridDiskDistances(k int) ([][]Cell, error) { return GridDiskDistances(c, k) } +// GridDiskDistancesUnsafe produces cells within grid distance k of the origin cell. +// Output behavior is undefined when one of the cells returned by this +// function is a pentagon or is in the pentagon distortion area. +// +// k-ring 0 is defined as the origin cell, k-ring 1 is defined as k-ring 0 and +// all neighboring cells, and so on. +// +// Outer slice is ordered from origin outwards. Inner slices are in no +// particular order. Elements of the output array may be left zero, as can +// happen when crossing a pentagon. +func GridDiskDistancesUnsafe(origin Cell, k int) ([][]Cell, error) { + rsz := maxGridDiskSize(k) + outHexes := make([]C.H3Index, rsz) + outDists := make([]C.int, rsz) + + if err := toErr(C.gridDiskDistancesUnsafe(C.H3Index(origin), C.int(k), &outHexes[0], &outDists[0])); err != nil { + return nil, err + } + + ret := make([][]Cell, k+1) + for i := 0; i <= k; i++ { + ret[i] = make([]Cell, 0, ringSize(i)) + } + + for i, d := range outDists { + ret[d] = append(ret[d], Cell(outHexes[i])) + } + + return ret, nil +} + +// GridDiskDistancesUnsafe produces cells within grid distance k of the origin cell. +// Output behavior is undefined when one of the cells returned by this +// function is a pentagon or is in the pentagon distortion area. +// +// k-ring 0 is defined as the origin cell, k-ring 1 is defined as k-ring 0 and +// all neighboring cells, and so on. +// +// Outer slice is ordered from origin outwards. Inner slices are in no +// particular order. Elements of the output array may be left zero, as can +// happen when crossing a pentagon. +func (c Cell) GridDiskDistancesUnsafe(k int) ([][]Cell, error) { + return GridDiskDistancesUnsafe(c, k) +} + +// GridDiskDistancesSafe produces cells within grid distance k of the origin cell. +// This is the safe, but slow version of GridDiskDistances. +// +// k-ring 0 is defined as the origin cell, k-ring 1 is defined as k-ring 0 and +// all neighboring cells, and so on. +// +// Outer slice is ordered from origin outwards. Inner slices are in no +// particular order. Elements of the output array may be left zero, as can +// happen when crossing a pentagon. +func GridDiskDistancesSafe(origin Cell, k int) ([][]Cell, error) { + rsz := maxGridDiskSize(k) + outHexes := make([]C.H3Index, rsz) + outDists := make([]C.int, rsz) + + if err := toErr(C.gridDiskDistancesSafe(C.H3Index(origin), C.int(k), &outHexes[0], &outDists[0])); err != nil { + return nil, err + } + + ret := make([][]Cell, k+1) + for i := 0; i <= k; i++ { + ret[i] = make([]Cell, 0, ringSize(i)) + } + + for i, d := range outDists { + ret[d] = append(ret[d], Cell(outHexes[i])) + } + + return ret, nil +} + +// GridDiskDistancesSafe produces cells within grid distance k of the origin cell. +// This is the safe, but slow version of GridDiskDistances. +// +// k-ring 0 is defined as the origin cell, k-ring 1 is defined as k-ring 0 and +// all neighboring cells, and so on. +// +// Outer slice is ordered from origin outwards. Inner slices are in no +// particular order. Elements of the output array may be left zero, as can +// happen when crossing a pentagon. +func (c Cell) GridDiskDistancesSafe(k int) ([][]Cell, error) { + return GridDiskDistancesSafe(c, k) +} + // GridRing produces the "hollow" ring of cells at exactly grid distance k from the origin cell. // // k-ring 0 returns just the origin hexagon. diff --git a/h3_test.go b/h3_test.go index b7ee559..6fec0fe 100644 --- a/h3_test.go +++ b/h3_test.go @@ -203,6 +203,53 @@ func TestGridDisk(t *testing.T) { }) } +func TestGridDisksUnsafe(t *testing.T) { + t.Parallel() + + t.Run("two cells", func(t *testing.T) { + t.Parallel() + + gds, err := GridDisksUnsafe([]Cell{validCell, validCell}, len(validDiskDist3_1)-1) + assertNoErr(t, err) + assertEqual(t, 2, len(gds), "expected grid disks to have two arrays returned") + assertEqualDisks(t, + flattenDisks(validDiskDist3_1), + gds[0], + "expected grid disks[0] to be the same", + ) + assertEqualDisks(t, + flattenDisks(validDiskDist3_1), + gds[1], + "expected grid disks[1] to be the same", + ) + }) + + t.Run("pentagon", func(t *testing.T) { + t.Parallel() + + _, err := GridDisksUnsafe([]Cell{pentagonCell}, 1) + assertErr(t, err) + assertErrIs(t, err, ErrPentagon) + }) + + t.Run("invalid cell", func(t *testing.T) { + t.Parallel() + + c := Cell(-1) + _, err := GridDisksUnsafe([]Cell{c}, 1) + assertErr(t, err) + assertErrIs(t, err, ErrCellInvalid) + }) + + t.Run("invalid k", func(t *testing.T) { + t.Parallel() + + _, err := GridDisksUnsafe([]Cell{validCell}, -1) + assertErr(t, err) + assertErrIs(t, err, ErrDomain) + }) +} + func TestGridDiskDistances(t *testing.T) { t.Parallel() @@ -211,6 +258,10 @@ func TestGridDiskDistances(t *testing.T) { rings, err := validCell.GridDiskDistances(len(validDiskDist3_1) - 1) assertNoErr(t, err) assertEqualDiskDistances(t, validDiskDist3_1, rings) + + rings, err = validCell.GridDiskDistancesSafe(len(validDiskDist3_1) - 1) + assertNoErr(t, err) + assertEqualDiskDistances(t, validDiskDist3_1, rings) }) t.Run("pentagon centered", func(t *testing.T) { @@ -220,6 +271,11 @@ func TestGridDiskDistances(t *testing.T) { assertNoErr(t, err) assertEqual(t, 2, len(rings), "expected 2 rings") assertEqual(t, 5, len(rings[1]), "expected 5 cells in second ring") + + rings, err = GridDiskDistancesSafe(pentagonCell, 1) + assertNoErr(t, err) + assertEqual(t, 2, len(rings), "expected 2 rings") + assertEqual(t, 5, len(rings[1]), "expected 5 cells in second ring") }) }) @@ -228,6 +284,38 @@ func TestGridDiskDistances(t *testing.T) { assertErr(t, err) assertErrIs(t, err, ErrDomain) assertNil(t, rings) + + rings, err = GridDiskDistancesSafe(pentagonCell, -1) + assertErr(t, err) + assertErrIs(t, err, ErrDomain) + assertNil(t, rings) + }) +} + +func TestGridDiskDistancesUnsafe(t *testing.T) { + t.Parallel() + + t.Run("no pentagon", func(t *testing.T) { + t.Parallel() + rings, err := validCell.GridDiskDistancesUnsafe(len(validDiskDist3_1) - 1) + assertNoErr(t, err) + assertEqualDiskDistances(t, validDiskDist3_1, rings) + }) + + t.Run("pentagon centered", func(t *testing.T) { + t.Parallel() + assertNoPanic(t, func() { + _, err := GridDiskDistancesUnsafe(pentagonCell, 1) + assertErr(t, err) + assertErrIs(t, err, ErrPentagon) + }) + }) + + t.Run("invalid k-ring", func(t *testing.T) { + rings, err := GridDiskDistancesUnsafe(pentagonCell, -1) + assertErr(t, err) + assertErrIs(t, err, ErrDomain) + assertNil(t, rings) }) } @@ -1354,11 +1442,13 @@ func assertEqualDiskDistances(t *testing.T, expected, actual [][]Cell) { } } -func assertEqualDisks(t *testing.T, expected, actual []Cell) { +func assertEqualDisks(t *testing.T, expected, actual []Cell, msgAndArgs ...any) { t.Helper() if len(expected) != len(actual) { t.Errorf("disk size mismatch: %v != %v", len(expected), len(actual)) + logMsgAndArgs(t, msgAndArgs...) + return } @@ -1370,9 +1460,9 @@ func assertEqualDisks(t *testing.T, expected, actual []Cell) { for i, cell := range expected { if cell != actual[i] { t.Errorf("cell[%d]: %v != %v", i, cell, actual[i]) + logMsgAndArgs(t, msgAndArgs...) count++ - if count > 5 { t.Logf("... and more") break @@ -1516,3 +1606,7 @@ func TestToErr(t *testing.T) { assertErrIs(t, toErr(999), ErrUnknown) }) } + +func TestLatLngsToC_Nil(t *testing.T) { + assertEqual(t, nil, latLngsToC(nil)) +} From 41962bcb1b3d4286021ac1fd1b3419cd4da63179 Mon Sep 17 00:00:00 2001 From: Justin Hwang Date: Fri, 6 Jun 2025 14:19:00 -0400 Subject: [PATCH 2/5] feat: convert directly between C and Go arrays (#85) Co-authored-by: Joseph Gilley --- bench_test.go | 27 ++++++++++++++++++++++----- h3.go | 24 ++++++------------------ 2 files changed, 28 insertions(+), 23 deletions(-) diff --git a/bench_test.go b/bench_test.go index 91de0bf..6128691 100644 --- a/bench_test.go +++ b/bench_test.go @@ -14,6 +14,7 @@ var ( addr = cell.String() geoBndry CellBoundary cells []Cell + disks [][]Cell ) func BenchmarkToString(b *testing.B) { @@ -29,32 +30,48 @@ func BenchmarkFromString(b *testing.B) { } } -func BenchmarkToGeoRes15(b *testing.B) { +func BenchmarkCellToLatLng(b *testing.B) { for n := 0; n < b.N; n++ { geo, _ = CellToLatLng(cell) } } -func BenchmarkFromGeoRes15(b *testing.B) { +func BenchmarkLatLngToCell(b *testing.B) { for n := 0; n < b.N; n++ { cell, _ = LatLngToCell(geo, 15) } } -func BenchmarkToGeoBndryRes15(b *testing.B) { +func BenchmarkCellToBoundary(b *testing.B) { for n := 0; n < b.N; n++ { geoBndry, _ = CellToBoundary(cell) } } -func BenchmarkHexRange(b *testing.B) { +func BenchmarkGridDisk(b *testing.B) { for n := 0; n < b.N; n++ { cells, _ = cell.GridDisk(10) } } +func BenchmarkGridRing(b *testing.B) { + for range b.N { + cells, _ = cell.GridRing(10) + } +} + func BenchmarkPolyfill(b *testing.B) { for n := 0; n < b.N; n++ { - cells, _ = PolygonToCells(validGeoPolygonHoles, 15) + cells, _ = PolygonToCells(validGeoPolygonHoles, 13) + } +} + +func BenchmarkGridDisksUnsafe(b *testing.B) { + cells, _ = PolygonToCells(validGeoPolygonHoles, 12) + + b.ResetTimer() + + for n := 0; n < b.N; n++ { + disks, _ = GridDisksUnsafe(cells, 10) } } diff --git a/h3.go b/h3.go index aaddb8b..012e370 100644 --- a/h3.go +++ b/h3.go @@ -1176,18 +1176,14 @@ func intPow(n, m int) int { } func cellsFromC(chs []C.H3Index, prune, refit bool) []Cell { - // OPT: This could be more efficient if we unsafely cast the C array to a - // []H3Index. - out := make([]Cell, 0, len(chs)) - - for i := range chs { - if prune && chs[i] <= 0 { + in := unsafe.Slice((*Cell)(unsafe.Pointer(&chs[0])), len(chs)) + out := in[:0] + for i := range in { + if prune && in[i] <= 0 { continue } - - out = append(out, Cell(chs[i])) + out = append(out, in[i]) } - if refit { // Some algorithms require a maximum sized array, but only use a subset // of the memory. refit sizes the slice to the last non-empty element. @@ -1197,7 +1193,6 @@ func cellsFromC(chs []C.H3Index, prune, refit bool) []Cell { } } } - return out } @@ -1216,14 +1211,7 @@ func edgesFromC(chs []C.H3Index) []DirectedEdge { } func cellsToC(chs []Cell) []C.H3Index { - // OPT: This could be more efficient if we unsafely cast the array to a - // []C.H3Index. - out := make([]C.H3Index, len(chs)) - for i := range chs { - out[i] = C.H3Index(chs[i]) - } - - return out + return unsafe.Slice((*C.H3Index)(unsafe.Pointer(&chs[0])), len(chs)) } func intsFromC(chs []C.int) []int { From d6054b35875f8bbc6d665fc946b5d2d2e7ee8dcc Mon Sep 17 00:00:00 2001 From: Justin Hwang Date: Fri, 6 Jun 2025 14:28:44 -0400 Subject: [PATCH 3/5] feat: slightly optimize CellsToMultiPolygon and LatLng#String (#86) Before: ``` BenchmarkCellsToMultiPolygon-16 589149 2022 ns/op 344 B/op 8 allocs/op BenchmarkLatLng_String-16 6480610 184.2 ns/op 40 B/op 3 allocs/op ``` After: ``` BenchmarkCellsToMultiPolygon-16 600781 2006 ns/op 200 B/op 5 allocs/op BenchmarkLatLng_String-16 9569876 126.4 ns/op 24 B/op 1 allocs/op ``` --- bench_test.go | 33 ++++++++++++++--------- h3.go | 75 ++++++++++++++++++++++++++++++++++++++------------- 2 files changed, 76 insertions(+), 32 deletions(-) diff --git a/bench_test.go b/bench_test.go index 6128691..10c799f 100644 --- a/bench_test.go +++ b/bench_test.go @@ -10,46 +10,53 @@ var ( Lat: 37, Lng: -122, } - cell, _ = LatLngToCell(geo, 15) - addr = cell.String() - geoBndry CellBoundary - cells []Cell - disks [][]Cell + latlngStr string + cell, _ = LatLngToCell(geo, 15) + addr = cell.String() + geoBndry CellBoundary + cells []Cell + disks [][]Cell ) func BenchmarkToString(b *testing.B) { - for n := 0; n < b.N; n++ { + for range b.N { addr = cell.String() } } func BenchmarkFromString(b *testing.B) { - for n := 0; n < b.N; n++ { + for range b.N { //nolint:gosec // IndexFromString returns uint64 and fixing that to detect integer overflows will break package API. Let's skip it for now. cell = Cell(IndexFromString("850dab63fffffff")) } } +func BenchmarkLatLng_String(b *testing.B) { + for range b.N { + latlngStr = geo.String() + } +} + func BenchmarkCellToLatLng(b *testing.B) { - for n := 0; n < b.N; n++ { + for range b.N { geo, _ = CellToLatLng(cell) } } func BenchmarkLatLngToCell(b *testing.B) { - for n := 0; n < b.N; n++ { + for range b.N { cell, _ = LatLngToCell(geo, 15) } } func BenchmarkCellToBoundary(b *testing.B) { - for n := 0; n < b.N; n++ { + for range b.N { geoBndry, _ = CellToBoundary(cell) } } func BenchmarkGridDisk(b *testing.B) { - for n := 0; n < b.N; n++ { + for range b.N { cells, _ = cell.GridDisk(10) } } @@ -61,7 +68,7 @@ func BenchmarkGridRing(b *testing.B) { } func BenchmarkPolyfill(b *testing.B) { - for n := 0; n < b.N; n++ { + for range b.N { cells, _ = PolygonToCells(validGeoPolygonHoles, 13) } } @@ -71,7 +78,7 @@ func BenchmarkGridDisksUnsafe(b *testing.B) { b.ResetTimer() - for n := 0; n < b.N; n++ { + for range b.N { disks, _ = GridDisksUnsafe(cells, 10) } } diff --git a/h3.go b/h3.go index 012e370..bb5e6fe 100644 --- a/h3.go +++ b/h3.go @@ -32,7 +32,6 @@ import "C" import ( "errors" - "fmt" "math" "strconv" "strings" @@ -72,6 +71,15 @@ const ( RadsToDegs = 180.0 / math.Pi ) +const ( + latLngFloatPrecision = 5 + // latLngStringSize is the size to pre-allocate the buffer for. + // Given latLngFloatPrecision, a typical string is "(DD.DDDDD, -DDD.DDDDD)" + // which is ~25-30 bytes. 32 is a safe and efficient capacity to start with + // to avoid re-allocation. + latLngStringSize = 32 +) + // PolygonToCells containment modes const ( ContainmentCenter ContainmentMode = C.CONTAINMENT_CENTER // Cell center is contained in the shape @@ -122,7 +130,6 @@ var ( ) type ( - // Cell is an Index that identifies a single hexagon cell at a resolution. Cell int64 @@ -468,7 +475,7 @@ func PolygonToCells(polygon GeoPolygon, resolution int) ([]Cell, error) { // and then any newly found hexagons are used to test again until no new // hexagons are found. func PolygonToCellsExperimental(polygon GeoPolygon, resolution int, mode ContainmentMode, maxNumCellsReturn ...int64) ([]Cell, error) { - var maxNumCells int64 = math.MaxInt64 + maxNumCells := int64(math.MaxInt64) if len(maxNumCellsReturn) > 0 { maxNumCells = maxNumCellsReturn[0] } @@ -519,30 +526,55 @@ func CellsToMultiPolygon(cells []Cell) ([]GeoPolygon, error) { return nil, err } - ret := []GeoPolygon{} + currPoly := cLinkedGeoPolygon + var countPoly int + for currPoly != nil { + countPoly++ + currPoly = currPoly.next + } + + ret := make([]GeoPolygon, countPoly) // traverse polygons for linked list of polygons - currPoly := cLinkedGeoPolygon + currPoly = cLinkedGeoPolygon + countPoly = 0 for currPoly != nil { - loops := []GeoLoop{} + currLoop := currPoly.first + var countLoop int + for currLoop != nil { + countLoop++ + currLoop = currLoop.next + } + loops := make([]GeoLoop, countLoop) // traverse loops for a polygon - currLoop := currPoly.first + currLoop = currPoly.first + countLoop = 0 for currLoop != nil { - loop := []LatLng{} + currPt := currLoop.first + var countPt int + for currPt != nil { + countPt++ + currPt = currPt.next + } + loop := make([]LatLng, countPt) // traverse points for a loop - currPt := currLoop.first + currPt = currLoop.first + countPt = 0 for currPt != nil { - loop = append(loop, latLngFromC(currPt.vertex)) + loop[countPt] = latLngFromC(currPt.vertex) + countPt++ currPt = currPt.next } - loops = append(loops, loop) + loops[countLoop] = loop + countLoop++ currLoop = currLoop.next } - ret = append(ret, GeoPolygon{GeoLoop: loops[0], Holes: loops[1:]}) + ret[countPoly] = GeoPolygon{GeoLoop: loops[0], Holes: loops[1:]} + countPoly++ currPoly = currPoly.next } @@ -669,7 +701,7 @@ func EdgeLengthM(e DirectedEdge) (float64, error) { func NumCells(resolution int) int { // NOTE: this is a mathematical operation, no need to call into H3 library. // See h3api.h for formula derivation. - return 2 + 120*intPow(7, (resolution)) //nolint:mnd // math formula + return 2 + 120*intPow(7, resolution) //nolint:mnd // math formula } // Res0Cells returns all the cells at resolution 0. @@ -1059,11 +1091,10 @@ func maxGridDiskSize(k int) int { } func latLngFromC(cg C.LatLng) LatLng { - g := LatLng{} - g.Lat = RadsToDegs * float64(cg.lat) - g.Lng = RadsToDegs * float64(cg.lng) - - return g + return LatLng{ + Lat: RadsToDegs * float64(cg.lat), + Lng: RadsToDegs * float64(cg.lng), + } } func cellBndryFromC(cb *C.CellBoundary) CellBoundary { @@ -1229,7 +1260,13 @@ func intsFromC(chs []C.int) []int { } func (g LatLng) String() string { - return fmt.Sprintf("(%.5f, %.5f)", g.Lat, g.Lng) + buf := make([]byte, 0, latLngStringSize) + buf = append(buf, '(') + buf = strconv.AppendFloat(buf, g.Lat, 'f', latLngFloatPrecision, 64) //nolint:mnd // float bit size + buf = append(buf, ',', ' ') + buf = strconv.AppendFloat(buf, g.Lng, 'f', latLngFloatPrecision, 64) //nolint:mnd // float bit size + buf = append(buf, ')') + return string(buf) } func (g LatLng) toCPtr() *C.LatLng { From 5cc4d5ce2074603df084d075f3f7098ef1599a4c Mon Sep 17 00:00:00 2001 From: Joseph Gilley Date: Fri, 6 Jun 2025 11:40:27 -0700 Subject: [PATCH 4/5] chore: housekeeping on docs --- CHANGELOG.md | 7 +++---- CONTRIBUTING.md | 6 ++++++ README.md | 4 +--- 3 files changed, 10 insertions(+), 7 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index c6e660f..bcd4690 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -1,12 +1,11 @@ # Changelog -All notable changes to this project will be documented in this file. The -format is based on [Keep a Changelog](http://keepachangelog.com/en/1.0.0/). - This project tracks the **major** and **minor** versions set upstream by [`h3`](github.com/uber/h3), and introduces backwards-compatible updates and/or fixes via **patches** with patch version bumps. +**Changelog notes for versions above v4 are under [Releases](https://github.com/uber/h3-go/releases).** + ## 4.0.0 All new functions to match H3 v4. @@ -84,4 +83,4 @@ See for upstream changes, and the ### Added -* everything! first commit. \ No newline at end of file +* everything! first commit. diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md index e1e1021..e466ac3 100644 --- a/CONTRIBUTING.md +++ b/CONTRIBUTING.md @@ -32,6 +32,12 @@ Generate coverage: go test -coverprofile=c.out && go tool cover -html=c.out ``` +### Using VSCode + +`golangci-lint` version 2 requires the pre-release version of the `golang.go` extension: + +https://golangci-lint.run/welcome/integrations/#visual-studio-code + ## Other ways to contribute You may also be interested in [contributing to the @uber/h3 diff --git a/README.md b/README.md index eb5e58c..1ee3b15 100644 --- a/README.md +++ b/README.md @@ -5,9 +5,7 @@ [![Go Report Card](https://goreportcard.com/badge/github.com/uber/h3-go/v4)](https://goreportcard.com/report/github.com/uber/h3-go) [![License](https://img.shields.io/badge/License-Apache%202.0-blue.svg)](LICENSE) [![GoDoc](http://img.shields.io/badge/go-doc-blue.svg)](https://godoc.org/github.com/uber/h3-go) -[![H3 Version](https://img.shields.io/badge/h3-v4.1.0-blue.svg)](https://github.com/uber/h3/releases/tag/v4.1.0) - -

H3-Go is looking for a maintainer familiar with Go, C, and H3. Volunteers welcome! Please get in touch with us on the H3 Slack.

+[![H3 Version](https://img.shields.io/badge/h3-v4.2.1-blue.svg)](https://github.com/uber/h3/releases/tag/v4.2.1) # H3-Go From c363d48fe46f9e99c78a781da0122192f8eac3e9 Mon Sep 17 00:00:00 2001 From: Joseph Gilley Date: Fri, 6 Jun 2025 11:44:11 -0700 Subject: [PATCH 5/5] doc: add vscode setup instructions to contrib notes --- .gitignore | 5 ++++- CONTRIBUTING.md | 6 ++++++ 2 files changed, 10 insertions(+), 1 deletion(-) diff --git a/.gitignore b/.gitignore index 1351d0e..eb67729 100644 --- a/.gitignore +++ b/.gitignore @@ -30,5 +30,8 @@ _testmain.go # Intellij project files .idea +# VSCode +.vscode + # Test coverage file -covprofile \ No newline at end of file +covprofile diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md index e466ac3..32203cf 100644 --- a/CONTRIBUTING.md +++ b/CONTRIBUTING.md @@ -34,6 +34,12 @@ go test -coverprofile=c.out && go tool cover -html=c.out ### Using VSCode +Add VSCode configuration, or merge recommended settings into your existing settings: + +```sh +git cherry-pick vscode +``` + `golangci-lint` version 2 requires the pre-release version of the `golang.go` extension: https://golangci-lint.run/welcome/integrations/#visual-studio-code