diff --git a/CHANGELOG.md b/CHANGELOG.md index 1d4d4b431..81a7213f4 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -6,6 +6,11 @@ The public API of this library consists of the functions declared in file [h3api.h](./src/h3lib/include/h3api.h). ## [Unreleased] +### Added +- `h3Distance` function for determining the grid distance between H3 indexes (#83) +- Internal `h3ToIjk` function for getting IJK+ coordinates from an index (#83) +- Internal `ijkDistance` function for determining the grid distance between IJK+ coordinates (#83) +- `h3ToIjk` filter application for experimenting with `h3ToIjk` (#83) ## [3.0.8] - 2018-07-18 ### Added diff --git a/CMakeLists.txt b/CMakeLists.txt index 28561550f..490094d17 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -127,6 +127,7 @@ set(EXAMPLE_SOURCE_FILES examples/edge.c) set(OTHER_SOURCE_FILES src/apps/filters/h3ToGeo.c + src/apps/filters/h3ToIjk.c src/apps/filters/h3ToComponents.c src/apps/filters/geoToH3.c src/apps/filters/h3ToGeoBoundary.c @@ -157,6 +158,7 @@ set(OTHER_SOURCE_FILES src/apps/testapps/mkRandGeo.c src/apps/testapps/testH3Api.c src/apps/testapps/testH3SetToLinkedGeo.c + src/apps/testapps/testH3ToIjk.c src/apps/miscapps/h3ToGeoBoundaryHier.c src/apps/miscapps/h3ToGeoHier.c src/apps/miscapps/generateBaseCellNeighbors.c @@ -279,6 +281,7 @@ endmacro() add_h3_executable(geoToH3 src/apps/filters/geoToH3.c ${APP_SOURCE_FILES}) add_h3_executable(h3ToComponents src/apps/filters/h3ToComponents.c ${APP_SOURCE_FILES}) add_h3_executable(h3ToGeo src/apps/filters/h3ToGeo.c ${APP_SOURCE_FILES}) +add_h3_executable(h3ToIjk src/apps/filters/h3ToIjk.c ${APP_SOURCE_FILES}) add_h3_executable(h3ToGeoBoundary src/apps/filters/h3ToGeoBoundary.c ${APP_SOURCE_FILES}) add_h3_executable(hexRange src/apps/filters/hexRange.c ${APP_SOURCE_FILES}) add_h3_executable(kRing src/apps/filters/kRing.c ${APP_SOURCE_FILES}) @@ -454,6 +457,7 @@ if(BUILD_TESTING) add_h3_test(testBBox src/apps/testapps/testBBox.c) add_h3_test(testVec2d src/apps/testapps/testVec2d.c) add_h3_test(testVec3d src/apps/testapps/testVec3d.c) + add_h3_test(testH3ToIjk src/apps/testapps/testH3ToIjk.c) add_h3_test_with_arg(testH3NeighborRotations src/apps/testapps/testH3NeighborRotations.c 0) add_h3_test_with_arg(testH3NeighborRotations src/apps/testapps/testH3NeighborRotations.c 1) diff --git a/src/apps/applib/include/utility.h b/src/apps/applib/include/utility.h index 647aa4883..6731a9c8e 100644 --- a/src/apps/applib/include/utility.h +++ b/src/apps/applib/include/utility.h @@ -1,5 +1,5 @@ /* - * Copyright 2016-2017 Uber Technologies, Inc. + * Copyright 2016-2018 Uber Technologies, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -42,4 +42,8 @@ void geoBoundaryPrint(const GeoBoundary* b); void geoBoundaryPrintln(const GeoBoundary* b); int readBoundary(FILE* f, GeoBoundary* b); +void iterateAllIndexesAtRes(int res, void (*callback)(H3Index)); +void iterateAllIndexesAtResPartial(int res, void (*callback)(H3Index), + int maxBaseCell); + #endif diff --git a/src/apps/applib/lib/utility.c b/src/apps/applib/lib/utility.c index 9de57e517..f3dd833fe 100644 --- a/src/apps/applib/lib/utility.c +++ b/src/apps/applib/lib/utility.c @@ -1,5 +1,5 @@ /* - * Copyright 2016-2017 Uber Technologies, Inc. + * Copyright 2016-2018 Uber Technologies, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -18,10 +18,13 @@ */ #include "utility.h" +#include #include +#include #include #include #include "geoCoord.h" +#include "h3Index.h" #include "h3api.h" void error(const char* msg) { @@ -163,3 +166,34 @@ int readBoundary(FILE* f, GeoBoundary* b) { return 0; } + +/** + * Call the callback for every index at the given resolution. + */ +void iterateAllIndexesAtRes(int res, void (*callback)(H3Index)) { + iterateAllIndexesAtResPartial(res, callback, NUM_BASE_CELLS); +} + +/** + * Call the callback for every index at the given resolution in base + * cell 0 up to the given base cell number. + */ +void iterateAllIndexesAtResPartial(int res, void (*callback)(H3Index), + int baseCells) { + assert(baseCells <= NUM_BASE_CELLS); + for (int i = 0; i < baseCells; i++) { + H3Index bc; + setH3Index(&bc, 0, i, 0); + int childrenSz = H3_EXPORT(maxUncompactSize)(&bc, 1, res); + STACK_ARRAY_CALLOC(H3Index, children, childrenSz); + H3_EXPORT(uncompact)(&bc, 1, children, childrenSz, res); + + for (int j = 0; j < childrenSz; j++) { + if (children[j] == 0) { + continue; + } + + (*callback)(children[j]); + } + } +} diff --git a/src/apps/filters/h3ToIjk.c b/src/apps/filters/h3ToIjk.c new file mode 100644 index 000000000..b03a5a956 --- /dev/null +++ b/src/apps/filters/h3ToIjk.c @@ -0,0 +1,76 @@ +/* + * Copyright 2018 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief stdin/stdout filter that converts from H3 indexes to relative IJK + * coordinates. This is experimental. + * + * usage: `h3ToIjk [origin]` + * + * The program reads H3 indexes from stdin and outputs the corresponding + * IJK coordinates to stdout, until EOF is encountered. The H3 indexes + * should be in integer form. `-1 -1 -1` is printed if the IJK coordinates + * could not be obtained. + * + * `origin` indicates the origin (or anchoring) index for the IJK coordinate + * space. + */ + +#include +#include +#include +#include "coordijk.h" +#include "h3Index.h" +#include "h3api.h" +#include "utility.h" + +void doCell(H3Index h, H3Index origin) { + CoordIJK ijk; + if (h3ToIjk(origin, h, &ijk)) { + printf("-1 -1 -1\n"); + } else { + printf("%d %d %d\n", ijk.i, ijk.j, ijk.k); + } +} + +int main(int argc, char *argv[]) { + // check command line args + if (argc != 2) { + fprintf(stderr, "usage: %s [origin]\n", argv[0]); + exit(1); + } + + H3Index origin; + + if (!sscanf(argv[1], "%" PRIx64, &origin)) + error("origin could not be read"); + + if (!H3_EXPORT(h3IsValid)(origin)) error("origin is invalid"); + + // process the indexes on stdin + char buff[BUFF_SIZE]; + while (1) { + // get an index from stdin + if (!fgets(buff, BUFF_SIZE, stdin)) { + if (feof(stdin)) + break; + else + error("reading H3 index from stdin"); + } + + H3Index h3 = H3_EXPORT(stringToH3)(buff); + doCell(h3, origin); + } +} diff --git a/src/apps/testapps/testH3ToIjk.c b/src/apps/testapps/testH3ToIjk.c new file mode 100644 index 000000000..2727a31fa --- /dev/null +++ b/src/apps/testapps/testH3ToIjk.c @@ -0,0 +1,234 @@ +/* + * Copyright 2018 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief tests H3 index to IJK+ grid functions. + * + * usage: `testH3ToIjk` + */ + +#include +#include +#include +#include "algos.h" +#include "baseCells.h" +#include "constants.h" +#include "h3Index.h" +#include "h3api.h" +#include "stackAlloc.h" +#include "test.h" +#include "utility.h" + +static const int MAX_DISTANCES[] = {1, 2, 5, 12, 19, 26}; + +void h3Distance_identity_assertions(H3Index h3) { + int r = H3_GET_RESOLUTION(h3); + + t_assert(H3_EXPORT(h3Distance)(h3, h3) == 0, "distance to self is 0"); + + CoordIJK ijk; + t_assert(h3ToIjk(h3, h3, &ijk) == 0, "failed to get ijk"); + if (r == 0) { + t_assert(_ijkMatches(&ijk, &UNIT_VECS[0]) == 1, "not at 0,0,0 (res 0)"); + } else if (r == 1) { + t_assert(_ijkMatches(&ijk, &UNIT_VECS[H3_GET_INDEX_DIGIT(h3, 1)]) == 1, + "not at expected coordinates (res 1)"); + } else if (r == 2) { + CoordIJK expected = UNIT_VECS[H3_GET_INDEX_DIGIT(h3, 1)]; + _downAp7r(&expected); + _neighbor(&expected, H3_GET_INDEX_DIGIT(h3, 2)); + t_assert(_ijkMatches(&ijk, &expected) == 1, + "not at expected coordinates (res 2)"); + } else { + t_assert(0, "wrong resolution"); + } +} + +void h3Distance_neighbors_assertions(H3Index h3) { + CoordIJK origin = {0}; + t_assert(h3ToIjk(h3, h3, &origin) == 0, "got ijk for origin"); + + for (int d = 1; d < 7; d++) { + if (d == 1 && h3IsPentagon(h3)) { + continue; + } + + int rotations = 0; + H3Index offset = h3NeighborRotations(h3, d, &rotations); + + CoordIJK ijk = {0}; + t_assert(h3ToIjk(h3, offset, &ijk) == 0, "got ijk for destination"); + CoordIJK invertedIjk = {0}; + _neighbor(&invertedIjk, d); + for (int i = 0; i < 3; i++) { + _ijkRotate60ccw(&invertedIjk); + } + _ijkAdd(&invertedIjk, &ijk, &ijk); + _ijkNormalize(&ijk); + + t_assert(_ijkMatches(&ijk, &origin), "back to origin"); + } +} + +void h3Distance_kRing_assertions(H3Index h3) { + int r = H3_GET_RESOLUTION(h3); + if (r > 5) { + t_assert(false, "wrong res"); + } + int maxK = MAX_DISTANCES[r]; + + int sz = H3_EXPORT(maxKringSize)(maxK); + STACK_ARRAY_CALLOC(H3Index, neighbors, sz); + STACK_ARRAY_CALLOC(int, distances, sz); + + H3_EXPORT(kRingDistances)(h3, maxK, neighbors, distances); + + for (int i = 0; i < sz; i++) { + if (neighbors[i] == 0) { + continue; + } + + int calculatedDistance = H3_EXPORT(h3Distance)(h3, neighbors[i]); + + // Don't consider indexes where h3Distance reports failure to + // generate + t_assert(calculatedDistance == distances[i] || calculatedDistance == -1, + "kRingDistances matches h3Distance"); + } +} + +BEGIN_TESTS(h3ToIjk); + +TEST(testIndexDistance) { + H3Index bc = 0; + setH3Index(&bc, 1, 17, 0); + H3Index p = 0; + setH3Index(&p, 1, 14, 0); + H3Index p2; + setH3Index(&p2, 1, 14, 2); + H3Index p3; + setH3Index(&p3, 1, 14, 3); + H3Index p4; + setH3Index(&p4, 1, 14, 4); + H3Index p5; + setH3Index(&p5, 1, 14, 5); + H3Index p6; + setH3Index(&p6, 1, 14, 6); + + t_assert(H3_EXPORT(h3Distance)(bc, p) == 3, "distance onto pentagon"); + t_assert(H3_EXPORT(h3Distance)(bc, p2) == 2, "distance onto p2"); + t_assert(H3_EXPORT(h3Distance)(bc, p3) == 3, "distance onto p3"); + // TODO works correctly but is rejected due to possible pentagon distortion. + // t_assert(H3_EXPORT(h3Distance)(bc, p4) == 3, "distance onto p4"); + // t_assert(H3_EXPORT(h3Distance)(bc, p5) == 4, "distance onto p5"); + t_assert(H3_EXPORT(h3Distance)(bc, p6) == 2, "distance onto p6"); +} + +TEST(testIndexDistance2) { + H3Index origin = 0x820c4ffffffffffL; + // Destination is on the other side of the pentagon + H3Index destination = 0x821ce7fffffffffL; + + // TODO doesn't work because of pentagon distortion. Both should be 5. + t_assert(H3_EXPORT(h3Distance)(destination, origin) == -1, + "distance in res 2 across pentagon"); + t_assert(H3_EXPORT(h3Distance)(origin, destination) == -1, + "distance in res 2 across pentagon (reversed)"); +} + +TEST(ijkDistance) { + CoordIJK z = {0, 0, 0}; + CoordIJK i = {1, 0, 0}; + CoordIJK ik = {1, 0, 1}; + CoordIJK ij = {1, 1, 0}; + CoordIJK j2 = {0, 2, 0}; + + t_assert(ijkDistance(&z, &z) == 0, "identity distance 0,0,0"); + t_assert(ijkDistance(&i, &i) == 0, "identity distance 1,0,0"); + t_assert(ijkDistance(&ik, &ik) == 0, "identity distance 1,0,1"); + t_assert(ijkDistance(&ij, &ij) == 0, "identity distance 1,1,0"); + t_assert(ijkDistance(&j2, &j2) == 0, "identity distance 0,2,0"); + + t_assert(ijkDistance(&z, &i) == 1, "0,0,0 to 1,0,0"); + t_assert(ijkDistance(&z, &j2) == 2, "0,0,0 to 0,2,0"); + t_assert(ijkDistance(&z, &ik) == 1, "0,0,0 to 1,0,1"); + t_assert(ijkDistance(&i, &ik) == 1, "1,0,0 to 1,0,1"); + t_assert(ijkDistance(&ik, &j2) == 3, "1,0,1 to 0,2,0"); + t_assert(ijkDistance(&ij, &ik) == 2, "1,0,1 to 1,1,0"); +} + +TEST(h3Distance_identity) { + iterateAllIndexesAtRes(0, h3Distance_identity_assertions); + iterateAllIndexesAtRes(1, h3Distance_identity_assertions); + iterateAllIndexesAtRes(2, h3Distance_identity_assertions); +} + +TEST(h3Distance_neighbors) { + iterateAllIndexesAtRes(0, h3Distance_neighbors_assertions); + iterateAllIndexesAtRes(1, h3Distance_neighbors_assertions); + iterateAllIndexesAtRes(2, h3Distance_neighbors_assertions); +} + +TEST(h3Distance_kRing) { + iterateAllIndexesAtRes(0, h3Distance_kRing_assertions); + iterateAllIndexesAtRes(1, h3Distance_kRing_assertions); + iterateAllIndexesAtRes(2, h3Distance_kRing_assertions); + // Don't iterate all of res 3, to save time + iterateAllIndexesAtResPartial(3, h3Distance_kRing_assertions, 27); + // These would take too long, even at partial execution + // iterateAllIndexesAtResPartial(4, h3Distance_kRing_assertions, 20); + // iterateAllIndexesAtResPartial(5, h3Distance_kRing_assertions, 20); +} + +TEST(h3DistanceBaseCells) { + H3Index bc1 = H3_INIT; + setH3Index(&bc1, 0, 15, 0); + + H3Index bc2 = H3_INIT; + setH3Index(&bc2, 0, 8, 0); + + H3Index bc3 = H3_INIT; + setH3Index(&bc3, 0, 31, 0); + + H3Index pent1 = H3_INIT; + setH3Index(&pent1, 0, 4, 0); + + t_assert(H3_EXPORT(h3Distance)(bc1, pent1) == 1, + "distance to neighbor is 1 (15, 4)"); + t_assert(H3_EXPORT(h3Distance)(bc1, bc2) == 1, + "distance to neighbor is 1 (15, 8)"); + t_assert(H3_EXPORT(h3Distance)(bc1, bc3) == 1, + "distance to neighbor is 1 (15, 31)"); + t_assert(H3_EXPORT(h3Distance)(pent1, bc3) == -1, + "distance to neighbor is invalid"); + + CoordIJK ijk; + t_assert(h3ToIjk(pent1, bc1, &ijk) == 0, "failed to get ijk (4, 15)"); + t_assert(_ijkMatches(&ijk, &UNIT_VECS[2]) == 1, "not at 0,1,0"); +} + +TEST(h3DistanceFailed) { + H3Index h3 = 0x832830fffffffffL; + H3Index edge = H3_EXPORT(getH3UnidirectionalEdge(h3, 0x832834fffffffffL)); + H3Index h3res2 = 0x822837fffffffffL; + + t_assert(H3_EXPORT(h3Distance)(edge, h3) == -1, "edges cannot be origins"); + t_assert(H3_EXPORT(h3Distance)(h3, edge) == -1, + "edges cannot be destinations"); + t_assert(H3_EXPORT(h3Distance)(h3, h3res2) == -1, + "cannot compare at different resolutions"); +} + +END_TESTS(); diff --git a/src/apps/testapps/testKRing.c b/src/apps/testapps/testKRing.c index 2610ee624..d76f135e3 100644 --- a/src/apps/testapps/testKRing.c +++ b/src/apps/testapps/testKRing.c @@ -19,11 +19,53 @@ * usage: `testKRing` */ +#include #include #include "algos.h" #include "baseCells.h" #include "h3Index.h" #include "test.h" +#include "utility.h" + +void kRing_equals_kRingInternal_assertions(H3Index h3) { + for (int k = 0; k < 3; k++) { + int kSz = H3_EXPORT(maxKringSize)(k); + + STACK_ARRAY_CALLOC(H3Index, neighbors, kSz); + STACK_ARRAY_CALLOC(int, distances, kSz); + H3_EXPORT(kRingDistances) + (h3, k, neighbors, distances); + + STACK_ARRAY_CALLOC(H3Index, internalNeighbors, kSz); + STACK_ARRAY_CALLOC(int, internalDistances, kSz); + _kRingInternal(h3, k, internalNeighbors, internalDistances, kSz, 0); + + int found = 0; + int internalFound = 0; + for (int iNeighbor = 0; iNeighbor < kSz; iNeighbor++) { + if (neighbors[iNeighbor] != 0) { + found++; + + for (int iInternal = 0; iInternal < kSz; iInternal++) { + if (internalNeighbors[iInternal] == neighbors[iNeighbor]) { + internalFound++; + + t_assert(distances[iNeighbor] == + internalDistances[iInternal], + "External and internal agree on " + "distance"); + + break; + } + } + + t_assert(found == internalFound, + "External and internal implementations " + "produce same output"); + } + } + } +} BEGIN_TESTS(kRing); @@ -263,67 +305,7 @@ TEST(kRing_equals_kRingInternal) { // since kRingDistances will sometimes use a different implementation. for (int res = 0; res < 2; res++) { - for (int i = 0; i < NUM_BASE_CELLS; i++) { - H3Index bc; - setH3Index(&bc, 0, i, 0); - int childrenSz = H3_EXPORT(maxUncompactSize)(&bc, 1, res); - H3Index *children = calloc(childrenSz, sizeof(H3Index)); - H3_EXPORT(uncompact)(&bc, 1, children, childrenSz, res); - - for (int j = 0; j < childrenSz; j++) { - if (children[j] == 0) { - continue; - } - - for (int k = 0; k < 3; k++) { - int kSz = H3_EXPORT(maxKringSize)(k); - - H3Index *neighbors = calloc(kSz, sizeof(H3Index)); - int *distances = calloc(kSz, sizeof(int)); - H3_EXPORT(kRingDistances) - (children[j], k, neighbors, distances); - - H3Index *internalNeighbors = calloc(kSz, sizeof(H3Index)); - int *internalDistances = calloc(kSz, sizeof(int)); - _kRingInternal(children[j], k, internalNeighbors, - internalDistances, kSz, 0); - - int found = 0; - int internalFound = 0; - for (int iNeighbor = 0; iNeighbor < kSz; iNeighbor++) { - if (neighbors[iNeighbor] != 0) { - found++; - - for (int iInternal = 0; iInternal < kSz; - iInternal++) { - if (internalNeighbors[iInternal] == - neighbors[iNeighbor]) { - internalFound++; - - t_assert(distances[iNeighbor] == - internalDistances[iInternal], - "External and internal agree on " - "distance"); - - break; - } - } - - t_assert(found == internalFound, - "External and internal implementations " - "produce same output"); - } - } - - free(neighbors); - free(distances); - free(internalNeighbors); - free(internalDistances); - } - } - - free(children); - } + iterateAllIndexesAtRes(res, kRing_equals_kRingInternal_assertions); } } diff --git a/src/h3lib/include/baseCells.h b/src/h3lib/include/baseCells.h index d6c79ef67..97031184b 100644 --- a/src/h3lib/include/baseCells.h +++ b/src/h3lib/include/baseCells.h @@ -52,5 +52,6 @@ int _faceIjkToBaseCellCCWrot60(const FaceIJK* h); void _baseCellToFaceIjk(int baseCell, FaceIJK* h); bool _baseCellIsCwOffset(int baseCell, int testFace); int _getBaseCellNeighbor(int baseCell, Direction dir); +Direction _getBaseCellDirection(int originBaseCell, int destinationBaseCell); #endif diff --git a/src/h3lib/include/coordijk.h b/src/h3lib/include/coordijk.h index 4173afade..b25c57fff 100644 --- a/src/h3lib/include/coordijk.h +++ b/src/h3lib/include/coordijk.h @@ -101,5 +101,6 @@ void _ijkRotate60ccw(CoordIJK* ijk); void _ijkRotate60cw(CoordIJK* ijk); Direction _rotate60ccw(Direction digit); Direction _rotate60cw(Direction digit); +int ijkDistance(const CoordIJK* a, const CoordIJK* b); #endif diff --git a/src/h3lib/include/h3Index.h b/src/h3lib/include/h3Index.h index 9429e5d62..bc1593aac 100644 --- a/src/h3lib/include/h3Index.h +++ b/src/h3lib/include/h3Index.h @@ -157,5 +157,6 @@ Direction _h3LeadingNonZeroDigit(H3Index h); H3Index _h3RotatePent60ccw(H3Index h); H3Index _h3Rotate60ccw(H3Index h); H3Index _h3Rotate60cw(H3Index h); +int h3ToIjk(H3Index origin, H3Index h3, CoordIJK* out); #endif diff --git a/src/h3lib/include/h3api.h b/src/h3lib/include/h3api.h index 421044980..7a847fb00 100644 --- a/src/h3lib/include/h3api.h +++ b/src/h3lib/include/h3api.h @@ -1,5 +1,5 @@ /* - * Copyright 2016-2017 Uber Technologies, Inc. + * Copyright 2016-2018 Uber Technologies, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -441,6 +441,14 @@ void H3_EXPORT(getH3UnidirectionalEdgesFromHexagon)(H3Index origin, void H3_EXPORT(getH3UnidirectionalEdgeBoundary)(H3Index edge, GeoBoundary *gb); /** @} */ +/** @defgroup h3Distance h3Distance + * Functions for h3Distance + * @{ + */ +/** @brief Returns grid distance between two indexes */ +int H3_EXPORT(h3Distance)(H3Index origin, H3Index h3); +/** @} */ + #ifdef __cplusplus } // extern "C" #endif diff --git a/src/h3lib/include/mathExtensions.h b/src/h3lib/include/mathExtensions.h index 58bf0c347..650d6a982 100644 --- a/src/h3lib/include/mathExtensions.h +++ b/src/h3lib/include/mathExtensions.h @@ -1,5 +1,5 @@ /* - * Copyright 2017 Uber Technologies, Inc. + * Copyright 2017-2018 Uber Technologies, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -20,6 +20,11 @@ #ifndef MATHEXTENSIONS_H #define MATHEXTENSIONS_H +/** + * MAX returns the maximum of two values. + */ +#define MAX(a, b) (((a) > (b)) ? (a) : (b)) + // Internal functions int _ipow(int base, int exp); diff --git a/src/h3lib/lib/baseCells.c b/src/h3lib/lib/baseCells.c index 9d8cf5b78..92b41cba8 100644 --- a/src/h3lib/lib/baseCells.c +++ b/src/h3lib/lib/baseCells.c @@ -867,3 +867,16 @@ bool _baseCellIsCwOffset(int baseCell, int testFace) { int _getBaseCellNeighbor(int baseCell, Direction dir) { return baseCellNeighbors[baseCell][dir]; } + +/** @brief Return the direction from the origin base cell to the neighbor. + * Returns INVALID_DIGIT if the base cells are not neighbors. + */ +Direction _getBaseCellDirection(int originBaseCell, int neighboringBaseCell) { + for (Direction dir = CENTER_DIGIT; dir < NUM_DIGITS; dir++) { + int testBaseCell = _getBaseCellNeighbor(originBaseCell, dir); + if (testBaseCell == neighboringBaseCell) { + return dir; + } + } + return INVALID_DIGIT; +} diff --git a/src/h3lib/lib/coordijk.c b/src/h3lib/lib/coordijk.c index 289258742..d1ac77bc7 100644 --- a/src/h3lib/lib/coordijk.c +++ b/src/h3lib/lib/coordijk.c @@ -25,6 +25,7 @@ #include #include "constants.h" #include "geoCoord.h" +#include "mathExtensions.h" /** * Sets an IJK coordinate to the specified component values. @@ -490,3 +491,17 @@ void _downAp3r(CoordIJK* ijk) { _ijkNormalize(ijk); } + +/** + * Finds the distance between the two coordinates. Returns result. + * + * @param c1 The first set of ijk coordinates. + * @param c2 The second set of ijk coordinates. + */ +int ijkDistance(const CoordIJK* c1, const CoordIJK* c2) { + CoordIJK diff; + _ijkSub(c1, c2, &diff); + _ijkNormalize(&diff); + CoordIJK absDiff = {abs(diff.i), abs(diff.j), abs(diff.k)}; + return MAX(absDiff.i, MAX(absDiff.j, absDiff.k)); +} \ No newline at end of file diff --git a/src/h3lib/lib/h3Index.c b/src/h3lib/lib/h3Index.c index adbe46cf8..0245a89ad 100644 --- a/src/h3lib/lib/h3Index.c +++ b/src/h3lib/lib/h3Index.c @@ -18,6 +18,7 @@ * (see h3api.h for the main library entry functions) */ #include "h3Index.h" +#include #include #include #include @@ -486,6 +487,31 @@ H3Index _h3RotatePent60ccw(H3Index h) { return h; } +/** + * Rotate an H3Index 60 degrees clockwise about a pentagonal center. + * @param h The H3Index. + */ +H3Index _h3RotatePent60cw(H3Index h) { + // rotate in place; skips any leading 1 digits (k-axis) + + int foundFirstNonZeroDigit = 0; + for (int r = 1, res = H3_GET_RESOLUTION(h); r <= res; r++) { + // rotate this digit + H3_SET_INDEX_DIGIT(h, r, _rotate60cw(H3_GET_INDEX_DIGIT(h, r))); + + // look for the first non-zero digit so we + // can adjust for deleted k-axes sequence + // if necessary + if (!foundFirstNonZeroDigit && H3_GET_INDEX_DIGIT(h, r) != 0) { + foundFirstNonZeroDigit = 1; + + // adjust for deleted k-axes sequence + if (_h3LeadingNonZeroDigit(h) == K_AXES_DIGIT) h = _h3Rotate60cw(h); + } + } + return h; +} + /** * Rotate an H3Index 60 degrees counter-clockwise. * @param h The H3Index. @@ -740,3 +766,222 @@ void H3_EXPORT(h3ToGeoBoundary)(H3Index h3, GeoBoundary* gb) { * a Class II grid. */ int isResClassIII(int res) { return res % 2; } + +/** + * Produces ijk+ coordinates for an index anchored by an origin. + * + * The coordinate space used by this function may have deleted + * regions or warping due to pentagonal distortion. + * + * Coordinates are only comparable if they come from the same + * origin index. + * + * @param origin An anchoring index for the ijk+ coordinate system. + * @param index Index to find the coordinates of + * @param out ijk+ coordinates of the index will be placed here on success + * @return 0 on success, or another value on failure. + */ +int h3ToIjk(H3Index origin, H3Index h3, CoordIJK* out) { + if (H3_GET_MODE(origin) != H3_HEXAGON_MODE || + H3_GET_MODE(h3) != H3_HEXAGON_MODE) { + // Only hexagon mode is relevant, since we can't + // encode directionality in CoordIJK. + return 1; + } + + int res = H3_GET_RESOLUTION(origin); + + if (res != H3_GET_RESOLUTION(h3)) { + return 1; + } + + int originBaseCell = H3_GET_BASE_CELL(origin); + int baseCell = H3_GET_BASE_CELL(h3); + + // Direction from origin base cell to index base cell + Direction dir = 0; + Direction revDir = 0; + if (originBaseCell != baseCell) { + dir = _getBaseCellDirection(originBaseCell, baseCell); + if (dir == INVALID_DIGIT) { + // Base cells are not neighbors, can't unfold. + return 2; + } + revDir = _getBaseCellDirection(baseCell, originBaseCell); + assert(revDir != INVALID_DIGIT); + } + + int originOnPent = _isBaseCellPentagon(originBaseCell); + int indexOnPent = _isBaseCellPentagon(baseCell); + + FaceIJK indexFijk = {0}; + if (dir != CENTER_DIGIT) { + // Rotate index into the orientation of the origin base cell. + // cw because we are undoing the rotation into that base cell. + int baseCellRotations = baseCellNeighbor60CCWRots[originBaseCell][dir]; + if (indexOnPent) { + for (int i = 0; i < baseCellRotations; i++) { + h3 = _h3RotatePent60cw(h3); + + revDir = _rotate60cw(revDir); + if (revDir == K_AXES_DIGIT) revDir = _rotate60cw(revDir); + } + } else { + for (int i = 0; i < baseCellRotations; i++) { + h3 = _h3Rotate60cw(h3); + + revDir = _rotate60cw(revDir); + } + } + } + // Face is unused. This produces coordinates in base cell coordinate space. + _h3ToFaceIjkWithInitializedFijk(h3, &indexFijk); + + // Origin leading digit -> index leading digit -> rotations 60 cw + // Either being 1 (K axis) is invalid. + // No good default at 0. + const int PENTAGON_ROTATIONS[7][7] = { + {0, -1, 0, 0, 0, 0, 0}, // 0 + {-1, -1, -1, -1, -1, -1, -1}, // 1 + {0, -1, 0, 0, 0, 1, 0}, // 2 + {0, -1, 0, 0, 1, 1, 0}, // 3 + {0, -1, 0, 5, 0, 0, 0}, // 4 + {0, -1, 5, 5, 0, 0, 0}, // 5 + {0, -1, 0, 0, 0, 0, 0}, // 6 + }; + // Simply prohibit many pentagon distortion cases rather than handling them. + const bool FAILED_DIRECTIONS_II[7][7] = { + {false, false, false, false, false, false, false}, // 0 + {false, false, false, false, false, false, false}, // 1 + {false, false, false, false, true, false, false}, // 2 + {false, false, false, false, false, false, true}, // 3 + {false, false, false, true, false, false, false}, // 4 + {false, false, true, false, false, false, false}, // 5 + {false, false, false, false, false, true, false}, // 6 + }; + const bool FAILED_DIRECTIONS_III[7][7] = { + {false, false, false, false, false, false, false}, // 0 + {false, false, false, false, false, false, false}, // 1 + {false, false, false, false, false, true, false}, // 2 + {false, false, false, false, true, false, false}, // 3 + {false, false, true, false, false, false, false}, // 4 + {false, false, false, false, false, false, true}, // 5 + {false, false, false, true, false, false, false}, // 6 + }; + + if (dir != CENTER_DIGIT) { + assert(baseCell != originBaseCell); + assert(!(originOnPent && indexOnPent)); + + int pentagonRotations = 0; + int directionRotations = 0; + + if (originOnPent) { + int originLeadingDigit = _h3LeadingNonZeroDigit(origin); + + if ((isResClassIII(res) && + FAILED_DIRECTIONS_III[originLeadingDigit][dir]) || + (!isResClassIII(res) && + FAILED_DIRECTIONS_II[originLeadingDigit][dir])) { + // TODO this part of the pentagon might not be unfolded + // correctly. + return 3; + } + + directionRotations = PENTAGON_ROTATIONS[originLeadingDigit][dir]; + pentagonRotations = directionRotations; + } else if (indexOnPent) { + int indexLeadingDigit = _h3LeadingNonZeroDigit(h3); + + if ((isResClassIII(res) && + FAILED_DIRECTIONS_III[indexLeadingDigit][revDir]) || + (!isResClassIII(res) && + FAILED_DIRECTIONS_II[indexLeadingDigit][revDir])) { + // TODO this part of the pentagon might not be unfolded + // correctly. + return 4; + } + + pentagonRotations = PENTAGON_ROTATIONS[revDir][indexLeadingDigit]; + } + + assert(pentagonRotations >= 0); + assert(directionRotations >= 0); + + for (int i = 0; i < pentagonRotations; i++) { + _ijkRotate60cw(&indexFijk.coord); + } + + CoordIJK offset = {0}; + _neighbor(&offset, dir); + // Scale offset based on resolution + for (int r = res - 1; r >= 0; r--) { + if (isResClassIII(r + 1)) { + // rotate ccw + _downAp7(&offset); + } else { + // rotate cw + _downAp7r(&offset); + } + } + + for (int i = 0; i < directionRotations; i++) { + _ijkRotate60cw(&offset); + } + + // Perform necessary translation + _ijkAdd(&indexFijk.coord, &offset, &indexFijk.coord); + _ijkNormalize(&indexFijk.coord); + } else if (originOnPent && indexOnPent) { + // If the origin and index are on pentagon, and we checked that the base + // cells are the same or neighboring, then they must be the same base + // cell. + assert(baseCell == originBaseCell); + + int originLeadingDigit = _h3LeadingNonZeroDigit(origin); + int indexLeadingDigit = _h3LeadingNonZeroDigit(h3); + + if (FAILED_DIRECTIONS_III[originLeadingDigit][indexLeadingDigit] || + FAILED_DIRECTIONS_II[originLeadingDigit][indexLeadingDigit]) { + // TODO this part of the pentagon might not be unfolded + // correctly. + return 5; + } + + int withinPentagonRotations = + PENTAGON_ROTATIONS[originLeadingDigit][indexLeadingDigit]; + + for (int i = 0; i < withinPentagonRotations; i++) { + _ijkRotate60cw(&indexFijk.coord); + } + } + + *out = indexFijk.coord; + return 0; +} + +/** + * Produces the grid distance between the two indexes. + * + * This function may fail to find the distance between two indexes, for + * example if they are very far apart. It may also fail when finding + * distances for indexes on opposite sides of a pentagon. + * + * @param origin Index to find the distance from. + * @param index Index to find the distance to. + * @return The distance, or a negative number if the library could not + * compute the distance. + */ +int H3_EXPORT(h3Distance)(H3Index origin, H3Index h3) { + CoordIJK originIjk, h3Ijk; + if (h3ToIjk(origin, origin, &originIjk)) { + // Only possible if origin is invalid, for example if it's a + // unidirectional edge. + return -1; + } + if (h3ToIjk(origin, h3, &h3Ijk)) { + return -1; + } + + return ijkDistance(&originIjk, &h3Ijk); +}