diff --git a/README.md b/README.md index 4aa7267..eaed8ed 100644 --- a/README.md +++ b/README.md @@ -91,7 +91,7 @@ func ExampleLatLngToCell() { | `gridDiskDistances` | `GridDiskDistances`, `Cell#GridDiskDistances` | | `gridRingUnsafe` | N/A | | `polygonToCells` | `PolygonToCells`, `GeoPolygon#Cells` | -| `cellsToMultiPolygon` | TODO | +| `cellsToMultiPolygon` | `CellsToMultiPolygon` | `degsToRads` | `DegsToRads` | | `radsToDegs` | `RadsToDegs` | | `greatCircleDistance` | `GreatCircleDistance* (3/3)` | diff --git a/h3.go b/h3.go index c0c871a..77fe71a 100644 --- a/h3.go +++ b/h3.go @@ -96,10 +96,6 @@ type ( GeoLoop GeoLoop Holes []GeoLoop } - - // LinkedGeoPolygon is a linked-list of GeoPolygons. - // TODO: not implemented. - LinkedGeoPolygon struct{} ) func NewLatLng(lat, lng float64) LatLng { @@ -246,8 +242,49 @@ func (p GeoPolygon) Cells(resolution int) []Cell { return PolygonToCells(p, resolution) } -func CellsToMultiPolygon(cells []Cell) *LinkedGeoPolygon { - panic("not implemented") +// CellsToMultiPolygon takes a set of cells and creates GeoPolygon(s) +// describing the outline(s) of a set of hexagons. Polygon outlines will follow +// GeoJSON MultiPolygon order: Each polygon will have one outer loop, which is first in +// the list, followed by any holes. +// +// It is expected that all hexagons in the set have the same resolution and that the set +// contains no duplicates. Behavior is undefined if duplicates or multiple resolutions are +// present, and the algorithm may produce unexpected or invalid output. +func CellsToMultiPolygon(cells []Cell) []GeoPolygon { + if len(cells) == 0 { + return nil + } + h3Indexes := cellsToC(cells) + cLinkedGeoPolygon := new(C.LinkedGeoPolygon) + C.cellsToLinkedMultiPolygon(&h3Indexes[0], C.int(len(h3Indexes)), cLinkedGeoPolygon) + ret := []GeoPolygon{} + + // traverse polygons for linked list of polygons + currPoly := cLinkedGeoPolygon + for currPoly != nil { + loops := []GeoLoop{} + + // traverse loops for a polygon + currLoop := currPoly.first + for currLoop != nil { + loop := []LatLng{} + + // traverse points for a loop + currPt := currLoop.first + for currPt != nil { + loop = append(loop, latLngFromC(currPt.vertex)) + currPt = currPt.next + } + + loops = append(loops, loop) + currLoop = currLoop.next + } + + ret = append(ret, GeoPolygon{GeoLoop: loops[0], Holes: loops[1:]}) + currPoly = currPoly.next + } + + return ret } // PointDistRads returns the "great circle" or "haversine" distance between diff --git a/h3_test.go b/h3_test.go index e3b4c58..c2ab758 100644 --- a/h3_test.go +++ b/h3_test.go @@ -387,6 +387,47 @@ func TestPolygonToCells(t *testing.T) { }) } +func TestCellsToMultiPolygon(t *testing.T) { + t.Parallel() + + // 7 cells in disk -> 1 polygon, 18-point loop, and no holes + cells := GridDisk(LatLngToCell(NewLatLng(0, 0), 10), 1) + res := CellsToMultiPolygon(cells) + assertEqual(t, len(res), 1) + assertEqual(t, len(res[0].GeoLoop), 18) + assertEqual(t, len(res[0].Holes), 0) + + // 6 cells in ring -> 1 polygon, 18-point loop, and 1 6-point hole + cells = GridDisk(LatLngToCell(NewLatLng(0, 0), 10), 1)[1:] + res = CellsToMultiPolygon(cells) + assertEqual(t, len(res), 1) + assertEqual(t, len(res[0].GeoLoop), 18) + assertEqual(t, len(res[0].Holes), 1) + assertEqual(t, len(res[0].Holes[0]), 6) + + // 2 hexagons connected -> 1 polygon, 10-point loop (2 shared points) and no holes + cells = GridDisk(LatLngToCell(NewLatLng(0, 0), 10), 1)[:2] + res = CellsToMultiPolygon(cells) + assertEqual(t, len(res), 1) + assertEqual(t, len(res[0].GeoLoop), 10) + assertEqual(t, len(res[0].Holes), 0) + + // 2 distinct disks -> 2 polygons, 2 18-point loops, and no holes + cells1 := GridDisk(LatLngToCell(NewLatLng(0, 0), 10), 1) + cells2 := GridDisk(LatLngToCell(NewLatLng(10, 10), 10), 1) + cells = append(cells1, cells2...) + res = CellsToMultiPolygon(cells) + assertEqual(t, len(res), 2) + assertEqual(t, len(res[0].GeoLoop), 18) + assertEqual(t, len(res[0].Holes), 0) + assertEqual(t, len(res[1].GeoLoop), 18) + assertEqual(t, len(res[1].Holes), 0) + + // empty + res = CellsToMultiPolygon([]Cell{}) + assertEqual(t, len(res), 0) +} + func TestGridPath(t *testing.T) { t.Parallel() path := lineStartCell.GridPath(lineEndCell)