Implement vertex mode by nrabinowitz · Pull Request #417 · uber/h3

nrabinowitz · 2021-01-05T17:33:10Z

This implements a new H3 index mode, VERTEX_MODE, which allows an H3 index to represent a shared vertex. This allows us to represent a vertex with an index rather than a geo coord, which is beneficial to some algorithms, and will allow us to fix issues in the current codebase that stem from trying to compare geo coords from different cells that might vary due to FPE.

Public functions implemented

cellToVertex(cell, vertexNum) - gets the H3Index representation of a single vertex for a cell. This vertex will have the same index for all three adjoining cells.
cellToVertexes(cell, out) - gets all vertexes for the given cell.
vertexToPoint(vertex, out) - gets the GeoCoord for the given vertex

To implement in a later PR

isValidVertex(vertex)
vertexToCells(vertex, out)
cellToCanonicalBoundary(cell)

This PR also includes benchmarks for cellToVertexes (pretty fast - on my machine, 130 microseconds for all vertexes in a 2-ring) and exhaustive tests for cellToVertexes and vertexToPoint up to res 4.

nrabinowitz · 2021-01-05T17:45:38Z

src/h3lib/lib/algos.c

+ * TODO: This is currently a brute-force algorithm, but as it's O(6) that's
+ * probably acceptible.
+ */
+Direction directionForNeighbor(H3Index origin, H3Index destination) {


I broke this out from getH3UnidirectionalEdge for reuse. I tried several much more clever approaches to getting the direction, but they all ended up being significantly slower than just checking all neighbors 🤷‍♂️

ajfriend · 2021-01-05T18:39:58Z

src/h3lib/include/h3api.h.in

+ * Functions for cellToVertexes
+ * @{
+ */
+/** @brief Returns a single vertex for a given cell, as an H3 index */


Should this be "array of vertexes"? And what do folks think about using the word "returns" when the function is void and doesn't actually return anything? Do we have a more accurate alternative? Maybe "writes out"?

Whoops, copy/pasta error. Updated to Returns all vertexes for a given cell, as H3 indexes - "returns" seems to be what we use elsewhere, and makes more sense for the bindings (returning via modifiying the out array is basically an implementation detail).

ajfriend · 2021-01-05T18:42:13Z

src/h3lib/include/h3api.h.in

+ * @{
+ */
+/** @brief Returns a single vertex for a given cell, as an H3 index */
+DECLSPEC H3Index H3_EXPORT(cellToVertex)(H3Index origin, int vertexNum);


Would getCellVertex be a better name, since this function isn't actually mapping a sell to a single vertex?

That's what I originally had, but I was trying to follow the naming RFC - this is similar in meaning to cellToBoundary or directedEdgeToCells I think, a transformation rather than a property lookup.

Though I see what you're saying, it's one of many not 1:1. Hrm. Open to opinions, but cellToVertexes definitely makes sense and I like the parallel structure.

What about cellToVertices? Should we spell it the right way or the "programmer way"? ;)

We (I? I can't remember if this was a discussion) decided a while back to use vertexes consistently in the codebase. Both are technically correct (see https://www.merriam-webster.com/dictionary/vertex), and I think vertexes is easier to remember, use in parallel structure, better for non-native English speakers, etc.

coveralls · 2021-01-05T19:03:28Z

Coverage increased (+0.05%) to 99.242% when pulling edfb4dc on nrabinowitz:vertex-mode into 29e353f on uber:master.

src/apps/benchmarks/benchmarkVertex.c

src/apps/testapps/testVertex.c

src/apps/testapps/testVertexExhaustive.c

isaacbrodsky · 2021-01-07T17:25:44Z

src/h3lib/include/constants.h

 /** H3 index modes */
 #define H3_HEXAGON_MODE 1
 #define H3_UNIEDGE_MODE 2
+#define H3_EDGE_MODE 3


the edge mode is reserved I presume?

Yes - I added H3_EDGE_MODE proactively because it made more sense for it to be sequentially next to H3_UNIEDGE_MODE, and we're pretty sure we're going to add it. Could remove here, I just thought it would look funny to have H3_UNIEDGE_MODE, H3_VERTEX_MODE, and H3_EDGE_MODE in that order.

isaacbrodsky · 2021-01-07T17:26:18Z

src/h3lib/include/constants.h

 #define H3_HEXAGON_MODE 1
 #define H3_UNIEDGE_MODE 2
+#define H3_EDGE_MODE 3
+#define H3_VERTEX_MODE 4


Please add the new mode to the specification in docs

Updated the Indexing docs, reformatting, clarifying a bit, and adding the new mode.

isaacbrodsky · 2021-01-07T17:28:13Z

src/h3lib/lib/algos.c

 }

+/**
+ * Get the direction for a given neighbor. This is effectively the reverse


This gives the direction to move from origin to destination?
Please add a comment about what this does in error cases

Will update comment

Did you want more error explanation than Returns INVALID_DIGIT if the cells are not neighbors? This is the only error case AFAIK, though invalid indexes might incorrectly return a direction (depending on what h3NeighborRotations does with invalid indexes).

src/h3lib/lib/vertex.c

isaacbrodsky · 2021-01-07T17:36:01Z

src/h3lib/lib/vertex.c

+ * @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) {


as part of the return code work I imagine these function signatures will get updated. Can't do that in this PR because some needed types are not present.

Possibly? There isn't an error case for this function if cell is valid (and, per similar discussions, I'm not verifying that here). I'm actually not certain what would happen here if an invalid cell is passed in (likely the output is undefined, possibly it's all H3_NULL)

As with #359 I'd like to make all public functions have a mechanism to return error information since we don't have an exception capacity otherwise.

Right, that makes sense. So we'd include the mechanism even when unused.

dfellis

Only minor comments. Look great!

docs/core-library/h3indexing.md

dfellis · 2021-01-08T19:36:19Z

src/h3lib/include/h3api.h.in

+ * @{
+ */
+/** @brief Returns a single vertex for a given cell, as an H3 index */
+DECLSPEC H3Index H3_EXPORT(cellToVertex)(H3Index origin, int vertexNum);


What about cellToVertices? Should we spell it the right way or the "programmer way"? ;)

isaacbrodsky · 2021-01-08T22:54:54Z

docs/core-library/h3indexing.md

+### 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". The components of the H3 Vertex index are packed into a 64-bit integer in order, highest bit first, as follows:


Comment that the owner is used to calculate the canonical index of the vertex? Otherwise not clear what "owner" means.

Nicholas Rabinowitz and others added 12 commits December 29, 2020 08:36

WIP on Vertex Mode indexes

37829ea

WIP on getCellVertex, works on all but res 0

38bdeb5

Vertex mode fully functional

1ea7019

WIP on Vertex Mode, fix calculation of left neighbor

bc62457

Use directionForNeighbor to calculate vertex

335915a

Add getCellVertexes, improve tests

4e90554

Fix left/right, implement faster(?) neighbor vertex lookup

23a1c6b

Add benchmark

c4a464c

Remove apparently ineffective optimization

fd0e92b

Make functions public, move exhaustive tests to separate suite

9a7eb9a

Improve coverage

86b3f10

Rename functions, remove adjustForPentagon

86f39a2

nrabinowitz requested review from ajfriend and dfellis January 5, 2021 17:33

Rename in .in file

202331c

nrabinowitz commented Jan 5, 2021

View reviewed changes

ajfriend reviewed Jan 5, 2021

View reviewed changes

Nick Rabinowitz added 3 commits January 5, 2021 10:49

Fix compile issue

198a478

Fix API description

21cdbc4

Fixing function name

a4eafef

isaacbrodsky reviewed Jan 7, 2021

View reviewed changes

Code review tweaks, updated CHANGELOG and indexing docs

9486f8f

dfellis approved these changes Jan 8, 2021

View reviewed changes

Reserved -> Mode-Dependent

0d47450

isaacbrodsky approved these changes Jan 8, 2021

View reviewed changes

Clarify owner in indexing docs

edfb4dc

nrabinowitz merged commit 5988d7c into uber:master Jan 9, 2021

Conversation

nrabinowitz commented Jan 5, 2021

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

coveralls commented Jan 5, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dfellis left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

coveralls commented Jan 5, 2021 •

edited

Loading