diff --git a/CHANGELOG.md b/CHANGELOG.md index 3e1ea2f76..10898cbf9 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -8,6 +8,10 @@ The public API of this library consists of the functions declared in file ## [Unreleased] ### Added +- Vertex mode and associated functions: + - `cellToVertex(cell, vertexNum)` + - `cellToVertexes(cell, out)` + - `vertexToPoint(vertex, out)` - closed-form implementation of `numHexagons` ### Breaking changes diff --git a/CMakeLists.txt b/CMakeLists.txt index 9b917caaa..fe7dac05d 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -182,6 +182,7 @@ set(OTHER_SOURCE_FILES src/apps/testapps/testH3SetToVertexGraph.c src/apps/testapps/testBBox.c src/apps/testapps/testVertex.c + src/apps/testapps/testVertexExhaustive.c src/apps/testapps/testPolygon.c src/apps/testapps/testVec2d.c src/apps/testapps/testVec3d.c @@ -214,6 +215,7 @@ set(OTHER_SOURCE_FILES src/apps/benchmarks/benchmarkKRing.c src/apps/benchmarks/benchmarkH3Line.c src/apps/benchmarks/benchmarkH3UniEdge.c + src/apps/benchmarks/benchmarkVertex.c src/apps/benchmarks/benchmarkH3Api.c) set(ALL_SOURCE_FILES @@ -605,6 +607,7 @@ if(H3_IS_ROOT_PROJECT AND BUILD_TESTING) # The "Exhaustive" part of the test name is used by the test-fast to exclude these files. # test-fast exists so that Travis CI can run Valgrind on tests without taking a very long time. add_h3_test(testH3UniEdgeExhaustive src/apps/testapps/testH3UniEdgeExhaustive.c) + add_h3_test(testVertexExhaustive src/apps/testapps/testVertexExhaustive.c) add_h3_test(testH3ToLocalIjExhaustive src/apps/testapps/testH3ToLocalIjExhaustive.c) add_h3_test(testH3LineExhaustive src/apps/testapps/testH3LineExhaustive.c) add_h3_test(testH3DistanceExhaustive src/apps/testapps/testH3DistanceExhaustive.c) @@ -633,6 +636,7 @@ if(BUILD_BENCHMARKS) add_h3_benchmark(benchmarkKRing src/apps/benchmarks/benchmarkKRing.c) add_h3_benchmark(benchmarkH3Line src/apps/benchmarks/benchmarkH3Line.c) add_h3_benchmark(benchmarkH3UniEdge src/apps/benchmarks/benchmarkH3UniEdge.c) + add_h3_benchmark(benchmarkVertex src/apps/benchmarks/benchmarkVertex.c) add_h3_benchmark(benchmarkH3SetToLinkedGeo src/apps/benchmarks/benchmarkH3SetToLinkedGeo.c) add_h3_benchmark(benchmarkPolyfill src/apps/benchmarks/benchmarkPolyfill.c) if(ENABLE_REQUIRES_ALL_SYMBOLS) diff --git a/docs/core-library/h3indexing.md b/docs/core-library/h3indexing.md index eea6c80ec..5d90329b3 100644 --- a/docs/core-library/h3indexing.md +++ b/docs/core-library/h3indexing.md @@ -13,44 +13,57 @@ Child hexagons are linearly smaller than their parent hexagons. ## H3Index Representation -The **H3Index** is the integer representation of an **H3** index, which can be placed into multiple modes to indicate the concept being indexed. +An **H3Index** is the integer representation of an **H3** index, which may be one of multiple modes to indicate the concept being indexed. -* Mode 1 is an **H3** Cell (Hexagon/Pentagon) index. -* Mode 2 is an **H3** Unidirectional Edge (Cell A -> Cell B) index. -* Mode 3 is planned to be a bidirectional edge (Cell A <-> Cell B). * Mode 0 is reserved and indicates an invalid **H3** index. - * This mode remains, partially, for backwards compatibility with an older version of H3. +* Mode 1 is an **H3 Cell** (Hexagon/Pentagon) index. +* Mode 2 is an **H3 Unidirectional Edge** (Cell A -> Cell B) index. +* Mode 3 is planned to be a bidirectional edge (Cell A <-> Cell B). +* Mode 4 is an **H3 Vertex** (i.e. a single vertex of an H3 Cell). + +The canonical string representation of an **H3Index** is the hexadecimal representation of the integer, using lowercase letters. The string representation is variable length (no zero padding) and is not prefixed or suffixed. + +### Invalid Index Mode 0 contains a special index, `H3_NULL`, which is unique: it is bit-equivalent to `0`. This index indicates, *specifically*, an invalid, missing, or uninitialized **H3** index; it is analogous to `NaN` in floating point. It should be used instead of an arbitrary Mode 0 index, due to its uniqueness and easy identifiability. -The components of the **H3** cell index (mode 1) are packed into a 64-bit integer in order, highest bit first, as follows: +### H3 Cell Index + +An H3 Cell index (mode 1) represents a cell (hexagon or pentagon) in the H3 grid system at a particular resolution. The components of the H3 Cell index are packed into a 64-bit integer in order, highest bit first, as follows: * 1 bit reserved and set to 0, -* 4 bits to indicate the index mode, +* 4 bits to indicate the H3 Cell index mode, * 3 bits reserved and set to 0, * 4 bits to indicate the cell resolution 0-15, -* 7 bits to indicate the base cell 0-121, and +* 7 bits to indicate the base cell 0-121, * 3 bits to indicate each subsequent digit 0-6 from resolution 1 up to the resolution of the cell (45 bits total are reserved for resolutions 1-15) -The components of the **H3** unidirectional edge index (mode 2) are packed into a 64-bit integer in order, highest bit first, as follows: +The three bits for each unused digit are set to 7. + +### H3 Unidirectional Edge Index + +An H3 Undirectional Edge index (mode 2) represents a single directed edge between two cells (an "origin" cell and a neighboring "destination" cell). The components of the H3 Unidirectional Edge index are packed into a 64-bit integer in order, highest bit first, as follows: * 1 bit reserved and set to 0, -* 4 bits to indicate the index mode, -* 3 bits to indicate the edge 1-6 of the cell to traverse, -* 4 bits to indicate the cell resolution 0-15, -* 7 bits to indicate the base cell 0-121, and -* 3 bits to indicate each subsequent digit 0-6 from resolution 1 up to the resolution of the cell (45 bits total are reserved for resolutions 1-15) +* 4 bits to indicate the H3 Unidirectional Edge index mode, +* 3 bits to indicate the edge (1-6) of the origin cell, +* Subsequent bits matching the index bits of the origin cell. -The canonical string representation of an **H3Index** is the hexadecimal representation of the integer, using lowercase letters. The string representation is variable length (no zero padding) and is not prefixed or suffixed. +### H3 Vertex Index -The three bits for each unused digit are set to 7. +An H3 Vertex index (mode 4) represents a single topological vertex in H3 grid system, shared by three cells. Note that this does not include the distortion vertexes occasionally present in a cell's geo boundary. An H3 Vertex is arbitrarily assigned one of the three neighboring cells as its "owner", which is used to calculate the canonical index and geo coordinate for the vertex. The components of the H3 Vertex index are packed into a 64-bit integer in order, highest bit first, as follows: + +* 1 bit reserved and set to 0, +* 4 bits to indicate the H3 Vertex index mode, +* 3 bits to indicate the vertex number (0-5) of vertex on the owner cell, +* Subsequent bits matching the index bits of the owner cell. ## Bit layout of H3Index -The layout of an **H3Index** is shown below in table form. The interpretation of the "Reserved/edge" field differs depending on the mode of the index. +The layout of an **H3Index** is shown below in table form. The interpretation of the "Reserved" field differs depending on the mode of the index. @@ -76,7 +89,7 @@ The layout of an **H3Index** is shown below in table form. The interpretation of - + diff --git a/src/apps/benchmarks/benchmarkH3UniEdge.c b/src/apps/benchmarks/benchmarkH3UniEdge.c index 0c66e8b0a..37e6b2c90 100644 --- a/src/apps/benchmarks/benchmarkH3UniEdge.c +++ b/src/apps/benchmarks/benchmarkH3UniEdge.c @@ -27,8 +27,9 @@ GeoBoundary outBoundary; H3_EXPORT(getH3UnidirectionalEdgesFromHexagon)(hex, edges); BENCHMARK(getH3UnidirectionalEdgeBoundary, 10000, { - for (int i = 0; i < 6; i++) + for (int i = 0; i < 6; i++) { H3_EXPORT(getH3UnidirectionalEdgeBoundary)(edges[i], &outBoundary); + } }); END_BENCHMARKS(); diff --git a/src/apps/benchmarks/benchmarkVertex.c b/src/apps/benchmarks/benchmarkVertex.c new file mode 100644 index 000000000..857c0ba99 --- /dev/null +++ b/src/apps/benchmarks/benchmarkVertex.c @@ -0,0 +1,55 @@ +/* + * Copyright 2021 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. + */ +#include "benchmark.h" +#include "h3api.h" +#include "vertex.h" + +// Fixtures. Cells are arbitrary, except that ring2 is all hexagons and +// ring2Pent is centered on a pentagon. +H3Index ring2[] = { + 0x89283081083ffff, 0x8928308109bffff, 0x8928308108bffff, 0x8928308108fffff, + 0x89283081087ffff, 0x89283081097ffff, 0x89283081093ffff, 0x89283081467ffff, + 0x8928308146fffff, 0x892830810d7ffff, 0x892830810c7ffff, 0x89283081013ffff, + 0x89283081017ffff, 0x892830810bbffff, 0x892830810b3ffff, 0x8928308154bffff, + 0x8928308155bffff, 0x8928308142fffff, 0x8928308142bffff}; +int ring2Count = 19; + +H3Index ring2Pent[] = { + 0x8508008bfffffff, 0x8508000ffffffff, 0x85080077fffffff, 0x85080047fffffff, + 0x85080017fffffff, 0x85080003fffffff, 0x8508000bfffffff, 0x85080073fffffff, + 0x85080057fffffff, 0x850800abfffffff, 0x8508008ffffffff, 0x85080013fffffff, + 0x8508001bfffffff, 0x850800c7fffffff, 0x850800cffffffff, 0x850800bbfffffff}; +int ring2PentCount = 16; + +BEGIN_BENCHMARKS(); + +H3Index* vertexes = calloc(6, sizeof(H3Index)); + +BENCHMARK(cellToVertexes, 10000, { + for (int i = 0; i < ring2Count; i++) { + H3_EXPORT(cellToVertexes)(ring2[i], vertexes); + } +}); + +BENCHMARK(cellToVertexesPent, 10000, { + for (int i = 0; i < ring2PentCount; i++) { + H3_EXPORT(cellToVertexes)(ring2Pent[i], vertexes); + } +}); + +free(vertexes); + +END_BENCHMARKS(); diff --git a/src/apps/testapps/testVertex.c b/src/apps/testapps/testVertex.c index c2d976219..3db905162 100644 --- a/src/apps/testapps/testVertex.c +++ b/src/apps/testapps/testVertex.c @@ -1,5 +1,5 @@ /* - * Copyright 2020 Uber Technologies, Inc. + * Copyright 2020-2021 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. @@ -15,8 +15,6 @@ */ /** @file * @brief tests H3 vertex functions. - * - * usage: `testVertex` */ #include "test.h" @@ -63,4 +61,28 @@ SUITE(Vertex) { vertexNumForDirection(pentagon, K_AXES_DIGIT) == INVALID_VERTEX_NUM, "K direction on pentagon should return invalid vertex"); } -} \ No newline at end of file + + TEST(directionForVertexNum_hex) { + H3Index origin = 0x823d6ffffffffff; + bool seenDirs[NUM_DIGITS] = {false}; + for (int vertexNum = 0; vertexNum < NUM_HEX_VERTS; vertexNum++) { + Direction dir = directionForVertexNum(origin, vertexNum); + t_assert(dir > 0 && dir < INVALID_DIGIT, "direction appears valid"); + t_assert(!seenDirs[dir], "direction appears only once"); + seenDirs[dir] = true; + } + } + + TEST(directionForVertexNum_badVerts) { + H3Index origin = 0x823d6ffffffffff; + + t_assert(directionForVertexNum(origin, -1) == INVALID_DIGIT, + "negative vertex should return invalid direction"); + t_assert(directionForVertexNum(origin, 6) == INVALID_DIGIT, + "invalid vertex should return invalid direction"); + + H3Index pentagon = 0x823007fffffffff; + t_assert(directionForVertexNum(pentagon, 5) == INVALID_DIGIT, + "invalid pent vertex should return invalid direction"); + } +} diff --git a/src/apps/testapps/testVertexExhaustive.c b/src/apps/testapps/testVertexExhaustive.c new file mode 100644 index 000000000..be7282793 --- /dev/null +++ b/src/apps/testapps/testVertexExhaustive.c @@ -0,0 +1,133 @@ +/* + * Copyright 2020-2021 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 vertex functions, exhaustively checking all cells at res 0-4 + */ + +#include "test.h" +#include "utility.h" +#include "vertex.h" + +static void directionForVertexNum_symmetry_assertions(H3Index h3) { + int numVerts = H3_EXPORT(h3IsPentagon)(h3) ? NUM_PENT_VERTS : NUM_HEX_VERTS; + for (int i = 0; i < numVerts; i++) { + Direction dir = directionForVertexNum(h3, i); + int vertexNum = vertexNumForDirection(h3, dir); + t_assert( + vertexNum == i, + "directionForVertexNum and vertexNumForDirection are symmetrical"); + } +} + +static void cellToVertex_point_assertions(H3Index h3) { + GeoBoundary gb; + H3_EXPORT(h3ToGeoBoundary)(h3, &gb); + int numVerts = H3_EXPORT(h3IsPentagon)(h3) ? NUM_PENT_VERTS : NUM_HEX_VERTS; + + // This test won't work if there are distortion vertexes in the boundary + if (numVerts < gb.numVerts) return; + + GeoCoord coord; + for (int i = 0; i < numVerts; i++) { + H3Index vertex = H3_EXPORT(cellToVertex)(h3, i); + H3_EXPORT(vertexToPoint)(vertex, &coord); + int almostEqual = + geoAlmostEqualThreshold(&gb.verts[i], &coord, 0.000001); + t_assert(almostEqual, "Vertex coordinates match boundary vertex"); + } +} + +static void cellToVertex_uniqueness_assertions(H3Index h3) { + H3Index originVerts[NUM_HEX_VERTS] = {0}; + H3_EXPORT(cellToVertexes)(h3, originVerts); + + for (int v1 = 0; v1 < NUM_HEX_VERTS - 1; v1++) { + for (int v2 = v1 + 1; v2 < NUM_HEX_VERTS; v2++) { + if (originVerts[v1] == originVerts[v2]) { + t_assert(false, "vertex should be unique"); + } + } + } +} + +static void cellToVertex_neighbor_assertions(H3Index h3) { + H3Index neighbors[7] = {0}; + H3Index originVerts[NUM_HEX_VERTS] = {0}; + H3Index neighborVerts[NUM_HEX_VERTS] = {0}; + + H3_EXPORT(kRing)(h3, 1, neighbors); + H3_EXPORT(cellToVertexes)(h3, originVerts); + + for (int i = 0; i < 7; i++) { + H3Index neighbor = neighbors[i]; + if (neighbor == H3_NULL || neighbor == h3) continue; + H3_EXPORT(cellToVertexes)(neighbor, neighborVerts); + + // calculate the set intersection + int intersection = 0; + for (int v1 = 0; v1 < NUM_HEX_VERTS; v1++) { + for (int v2 = 0; v2 < NUM_HEX_VERTS; v2++) { + if (neighborVerts[v1] == originVerts[v2]) { + intersection++; + } + } + } + + t_assert(intersection == 2, + "Neighbor shares 2 unique vertexes with origin"); + } +} + +SUITE(Vertex) { + TEST(directionForVertexNum_symmetry) { + iterateAllIndexesAtRes(0, directionForVertexNum_symmetry_assertions); + iterateAllIndexesAtRes(1, directionForVertexNum_symmetry_assertions); + iterateAllIndexesAtRes(2, directionForVertexNum_symmetry_assertions); + iterateAllIndexesAtRes(3, directionForVertexNum_symmetry_assertions); + iterateAllIndexesAtRes(4, directionForVertexNum_symmetry_assertions); + } + + TEST(cellToVertex_point) { + iterateAllIndexesAtRes(0, cellToVertex_point_assertions); + iterateAllIndexesAtRes(1, cellToVertex_point_assertions); + iterateAllIndexesAtRes(2, cellToVertex_point_assertions); + iterateAllIndexesAtRes(3, cellToVertex_point_assertions); + iterateAllIndexesAtRes(4, cellToVertex_point_assertions); + + // Res 5: normal base cell + iterateBaseCellIndexesAtRes(5, cellToVertex_point_assertions, 0); + // Res 5: pentagon base cell + iterateBaseCellIndexesAtRes(5, cellToVertex_point_assertions, 14); + // Res 5: polar pentagon base cell + iterateBaseCellIndexesAtRes(5, cellToVertex_point_assertions, 117); + } + + TEST(cellToVertex_neighbors) { + iterateAllIndexesAtRes(0, cellToVertex_neighbor_assertions); + iterateAllIndexesAtRes(1, cellToVertex_neighbor_assertions); + iterateAllIndexesAtRes(2, cellToVertex_neighbor_assertions); + iterateAllIndexesAtRes(3, cellToVertex_neighbor_assertions); + iterateAllIndexesAtRes(4, cellToVertex_neighbor_assertions); + } + + TEST(cellToVertex_uniqueness) { + iterateAllIndexesAtRes(0, cellToVertex_uniqueness_assertions); + iterateAllIndexesAtRes(1, cellToVertex_uniqueness_assertions); + iterateAllIndexesAtRes(2, cellToVertex_uniqueness_assertions); + iterateAllIndexesAtRes(3, cellToVertex_uniqueness_assertions); + iterateAllIndexesAtRes(4, cellToVertex_uniqueness_assertions); + } +} diff --git a/src/h3lib/include/algos.h b/src/h3lib/include/algos.h index 9a7b4578b..24ff04349 100644 --- a/src/h3lib/include/algos.h +++ b/src/h3lib/include/algos.h @@ -29,6 +29,9 @@ // neighbor along the ijk coordinate system of the current face, rotated H3Index h3NeighborRotations(H3Index origin, Direction dir, int* rotations); +// IJK direction of neighbor +Direction directionForNeighbor(H3Index origin, H3Index destination); + // k-ring implementation void _kRingInternal(H3Index origin, int k, H3Index* out, int* distances, int maxIdx, int curK); diff --git a/src/h3lib/include/constants.h b/src/h3lib/include/constants.h index 9328c7786..53d9b65e3 100644 --- a/src/h3lib/include/constants.h +++ b/src/h3lib/include/constants.h @@ -80,5 +80,7 @@ /** H3 index modes */ #define H3_HEXAGON_MODE 1 #define H3_UNIEDGE_MODE 2 +#define H3_EDGE_MODE 3 +#define H3_VERTEX_MODE 4 #endif diff --git a/src/h3lib/include/h3api.h.in b/src/h3lib/include/h3api.h.in index 6410fa97c..160d85982 100644 --- a/src/h3lib/include/h3api.h.in +++ b/src/h3lib/include/h3api.h.in @@ -610,6 +610,30 @@ DECLSPEC void H3_EXPORT(getH3UnidirectionalEdgeBoundary)(H3Index edge, GeoBoundary *gb); /** @} */ +/** @defgroup cellToVertex cellToVertex + * Functions for cellToVertex + * @{ + */ +/** @brief Returns a single vertex for a given cell, as an H3 index */ +DECLSPEC H3Index H3_EXPORT(cellToVertex)(H3Index origin, int vertexNum); +/** @} */ + +/** @defgroup cellToVertexes cellToVertexes + * Functions for cellToVertexes + * @{ + */ +/** @brief Returns all vertexes for a given cell, as H3 indexes */ +DECLSPEC void H3_EXPORT(cellToVertexes)(H3Index origin, H3Index *vertexes); +/** @} */ + +/** @defgroup vertexToPoint vertexToPoint + * Functions for vertexToPoint + * @{ + */ +/** @brief Returns a single vertex for a given cell, as an H3 index */ +DECLSPEC void H3_EXPORT(vertexToPoint)(H3Index vertex, GeoCoord *coord); +/** @} */ + /** @defgroup h3Distance h3Distance * Functions for h3Distance * @{ diff --git a/src/h3lib/include/vertex.h b/src/h3lib/include/vertex.h index f11b8dfd9..07f89d4c6 100644 --- a/src/h3lib/include/vertex.h +++ b/src/h3lib/include/vertex.h @@ -1,5 +1,5 @@ /* - * Copyright 2020 Uber Technologies, Inc. + * Copyright 2020-2021 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. @@ -38,7 +38,7 @@ typedef struct { /** Max number of faces a base cell's descendants may appear on */ #define MAX_BASE_CELL_FACES 5 -int vertexRotations(H3Index cell); int vertexNumForDirection(const H3Index origin, const Direction direction); +Direction directionForVertexNum(const H3Index origin, const int vertexNum); #endif diff --git a/src/h3lib/lib/algos.c b/src/h3lib/lib/algos.c index d3b482194..e4cf5d78c 100644 --- a/src/h3lib/lib/algos.c +++ b/src/h3lib/lib/algos.c @@ -411,6 +411,31 @@ H3Index h3NeighborRotations(H3Index origin, Direction dir, int* rotations) { return out; } +/** + * Get the direction from the origin to a given neighbor. This is effectively + * the reverse operation for h3NeighborRotations. Returns INVALID_DIGIT if the + * cells are not neighbors. + * + * TODO: This is currently a brute-force algorithm, but as it's O(6) that's + * probably acceptible. + */ +Direction directionForNeighbor(H3Index origin, H3Index destination) { + bool isPentagon = H3_EXPORT(h3IsPentagon)(origin); + // Checks each neighbor, in order, to determine which direction the + // destination neighbor is located. Skips CENTER_DIGIT since that + // would be the origin; skips deleted K direction for pentagons. + H3Index neighbor; + for (Direction direction = isPentagon ? J_AXES_DIGIT : K_AXES_DIGIT; + direction < NUM_DIGITS; direction++) { + int rotations = 0; + neighbor = h3NeighborRotations(origin, direction, &rotations); + if (neighbor == destination) { + return direction; + } + } + return INVALID_DIGIT; +} + /** * hexRange produces indexes within k distance of the origin index. * Output behavior is undefined when one of the indexes returned by this diff --git a/src/h3lib/lib/h3UniEdge.c b/src/h3lib/lib/h3UniEdge.c index 32e7e7e17..c75a7e716 100644 --- a/src/h3lib/lib/h3UniEdge.c +++ b/src/h3lib/lib/h3UniEdge.c @@ -102,36 +102,20 @@ int H3_EXPORT(h3IndexesAreNeighbors)(H3Index origin, H3Index destination) { */ H3Index H3_EXPORT(getH3UnidirectionalEdge)(H3Index origin, H3Index destination) { - // Short-circuit and return an invalid index value if they are not neighbors - if (H3_EXPORT(h3IndexesAreNeighbors)(origin, destination) == 0) { + // Determine the IJK direction from the origin to the destination + Direction direction = directionForNeighbor(origin, destination); + + // The direction will be invalid if the cells are not neighbors + if (direction == INVALID_DIGIT) { return H3_NULL; } - // Otherwise, determine the IJK direction from the origin to the destination + // Create the edge index for the neighbor direction H3Index output = origin; H3_SET_MODE(output, H3_UNIEDGE_MODE); + H3_SET_RESERVED_BITS(output, direction); - bool isPentagon = H3_EXPORT(h3IsPentagon)(origin); - - // Checks each neighbor, in order, to determine which direction the - // destination neighbor is located. Skips CENTER_DIGIT since that - // would be this index. - H3Index neighbor; - // Excluding from branch coverage as we never hit the end condition - // LCOV_EXCL_BR_START - for (Direction direction = isPentagon ? J_AXES_DIGIT : K_AXES_DIGIT; - direction < NUM_DIGITS; direction++) { - // LCOV_EXCL_BR_STOP - int rotations = 0; - neighbor = h3NeighborRotations(origin, direction, &rotations); - if (neighbor == destination) { - H3_SET_RESERVED_BITS(output, direction); - return output; - } - } - - // This should be impossible, return H3_NULL in this case; - return H3_NULL; // LCOV_EXCL_LINE + return output; } /** diff --git a/src/h3lib/lib/vertex.c b/src/h3lib/lib/vertex.c index b6bbfdf3d..1f77cec57 100644 --- a/src/h3lib/lib/vertex.c +++ b/src/h3lib/lib/vertex.c @@ -1,5 +1,5 @@ /* - * Copyright 2020 Uber Technologies, Inc. + * Copyright 2020-2021 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. @@ -19,6 +19,10 @@ #include "vertex.h" +#include +#include + +#include "algos.h" #include "baseCells.h" #include "faceijk.h" #include "geoCoord.h" @@ -45,7 +49,7 @@ static const PentagonDirectionFaces pentagonDirectionFaces[NUM_PENTAGONS] = { * compared to the directional layout of its neighbors. * @return Number of CCW rotations for the cell */ -int vertexRotations(H3Index cell) { +static int vertexRotations(H3Index cell) { // Get the face and other info for the origin FaceIJK fijk; _h3ToFaceIjk(cell, &fijk); @@ -61,7 +65,8 @@ int vertexRotations(H3Index cell) { if (_isBaseCellPentagon(baseCell)) { // Find the appropriate direction-to-face mapping PentagonDirectionFaces dirFaces; - for (int p = 0; p < NUM_PENTAGONS; p++) { + // Excluding from branch coverage as we never hit the end condition + for (int p = 0; p < NUM_PENTAGONS; p++) { // LCOV_EXCL_BR_LINE if (pentagonDirectionFaces[p].baseCell == baseCell) { dirFaces = pentagonDirectionFaces[p]; break; @@ -132,3 +137,135 @@ int vertexNumForDirection(const H3Index origin, const Direction direction) { NUM_HEX_VERTS; } } + +/** @brief Vertex number to hexagon direction relationships (same face). + */ +static const Direction vertexNumToDirectionHex[NUM_HEX_VERTS] = { + IJ_AXES_DIGIT, J_AXES_DIGIT, JK_AXES_DIGIT, + K_AXES_DIGIT, IK_AXES_DIGIT, I_AXES_DIGIT}; + +/** @brief Vertex number to pentagon direction relationships (same face). + */ +static const Direction vertexNumToDirectionPent[NUM_PENT_VERTS] = { + IJ_AXES_DIGIT, J_AXES_DIGIT, JK_AXES_DIGIT, IK_AXES_DIGIT, I_AXES_DIGIT}; + +/** + * Get the direction for a given vertex number. This returns the direction for + * the neighbor between the given vertex number and the next number in sequence. + * @returns The direction for this vertex, or INVALID_DIGIT if the vertex + * number is invalid. + */ +Direction directionForVertexNum(const H3Index origin, const int vertexNum) { + int isPentagon = H3_EXPORT(h3IsPentagon)(origin); + // Check for invalid vertexes + if (vertexNum < 0 || + vertexNum > (isPentagon ? NUM_PENT_VERTS : NUM_HEX_VERTS) - 1) + return INVALID_DIGIT; + + // Determine the vertex rotations for this cell + int rotations = vertexRotations(origin); + + // Find the appropriate direction, rotating CW if necessary + return isPentagon ? vertexNumToDirectionPent[(vertexNum + rotations) % + NUM_PENT_VERTS] + : vertexNumToDirectionHex[(vertexNum + rotations) % + NUM_HEX_VERTS]; +} + +/** + * Get a single vertex for a given cell, as an H3 index, or + * H3_NULL if the vertex is invalid + * @param cell Cell to get the vertex for + * @param vertexNum Number (index) of the vertex to calculate + */ +H3Index H3_EXPORT(cellToVertex)(H3Index cell, int vertexNum) { + int cellIsPentagon = H3_EXPORT(h3IsPentagon)(cell); + int cellNumVerts = cellIsPentagon ? NUM_PENT_VERTS : NUM_HEX_VERTS; + + // Get the left neighbor of the vertex, with its rotations + Direction left = directionForVertexNum(cell, vertexNum); + if (left == INVALID_DIGIT) return H3_NULL; + int rRotations = 0; + H3Index leftNeighbor = h3NeighborRotations(cell, left, &rRotations); + + // Get the right neighbor of the vertex, with its rotations + // Note that vertex - 1 is the right side, as vertex numbers are CCW + Direction right = directionForVertexNum( + cell, (vertexNum - 1 + cellNumVerts) % cellNumVerts); + // This case should be unreachable; invalid verts fail the left side first + if (right == INVALID_DIGIT) return H3_NULL; // LCOV_EXCL_LINE + int lRotations = 0; + H3Index rightNeighbor = h3NeighborRotations(cell, right, &lRotations); + + // Determine the owner. By convention, this is the cell with the + // lowest numerical index. + H3Index owner = cell; + if (leftNeighbor < owner) owner = leftNeighbor; + if (rightNeighbor < owner) owner = rightNeighbor; + + // Determine the vertex number for the owner cell + int ownerVertexNum = vertexNum; + + if (owner == leftNeighbor) { + Direction dir = directionForNeighbor(owner, cell); + // For the left neighbor, we need the second vertex of the + // edge, which may involve looping around the vertex nums + ownerVertexNum = vertexNumForDirection(owner, dir) + 1; + if (ownerVertexNum == NUM_HEX_VERTS || + (H3_EXPORT(h3IsPentagon)(owner) && + ownerVertexNum == NUM_PENT_VERTS)) { + ownerVertexNum = 0; + } + } else if (owner == rightNeighbor) { + Direction dir = directionForNeighbor(owner, cell); + ownerVertexNum = vertexNumForDirection(owner, dir); + } + + // Create the vertex index + H3Index vertex = owner; + H3_SET_MODE(vertex, H3_VERTEX_MODE); + H3_SET_RESERVED_BITS(vertex, ownerVertexNum); + + return vertex; +} + +/** + * Get all vertexes for the given cell + * @param cell Cell to get the vertexes for + * @param vertexes Array to hold vertex output. Must have length >= 6. + */ +void H3_EXPORT(cellToVertexes)(H3Index cell, H3Index* vertexes) { + // Get all vertexes. If the cell is a pentagon, will fill the final slot + // with H3_NULL. + for (int i = 0; i < NUM_HEX_VERTS; i++) { + vertexes[i] = H3_EXPORT(cellToVertex)(cell, i); + } +} + +/** + * Get the geocoordinates of an H3 vertex + * @param vertex H3 index describing a vertex + * @param coord Output geo coordinate + */ +void H3_EXPORT(vertexToPoint)(H3Index vertex, GeoCoord* coord) { + // Get the vertex number and owner from the vertex + int vertexNum = H3_GET_RESERVED_BITS(vertex); + H3Index owner = vertex; + H3_SET_MODE(owner, H3_HEXAGON_MODE); + H3_SET_RESERVED_BITS(owner, 0); + + // Get the single vertex from the boundary + GeoBoundary gb; + FaceIJK fijk; + _h3ToFaceIjk(owner, &fijk); + int res = H3_GET_RESOLUTION(owner); + + if (H3_EXPORT(h3IsPentagon)(owner)) { + _faceIjkPentToGeoBoundary(&fijk, res, vertexNum, 1, &gb); + } else { + _faceIjkToGeoBoundary(&fijk, res, vertexNum, 1, &gb); + } + + // Copy from boundary to output coord + *coord = gb.verts[0]; +}
0x30 Reserved ModeReserved/edgeMode-Dependent Resolution Base cell