Add hexLine function to return the line of indexes between a given start and end #165

nrabinowitz · 2018-12-13T19:33:15Z

Adds the hexLine function and exposes it in the API.
Adds property-based tests for all hexagons in res 0-2 and some base cells in res 3.
Adds ijkToCube and cubeToIjk helpers to translate from IJK to cube coordinate space

This uses the algorithm described on the Red Blob Games site, converting IJK to cube coordinates in order to use the cubeRound algo.

TODO:

Add to CHANGELOG
Add to docs

Fixes #163
Closes #162

nrabinowitz · 2018-12-13T19:37:29Z

src/h3lib/lib/localij.c

-            if ((isResClassIII(res) &&
-                 FAILED_DIRECTIONS_III[originLeadingDigit][dir]) ||
-                (!isResClassIII(res) &&
-                 FAILED_DIRECTIONS_II[originLeadingDigit][dir])) {


This part fixes #163. The change may exclude valid cases, but I think it's okay to be more conservative here. Would like feedback from @isaacbrodsky if available on how the Class III check was expected to work, but I don't think that has to block this change.

Unfortunately I'm not available to investigate this problem right now. I expect this to be safe (edit: meaning won't produce more invalid coordinates) to fail more directions as a temporary solution. I will definitely take a look at #163 when I'm able to.

Definitely want to defer to @isaacbrodsky on this piece, but my gut feeling of applying direction blocks for both hexagon orientations is not the right solution. Either these two should be merged (because there is no difference in reality), or the algorithm behind the FAILED_DIRECTIONS_* lookup tables needs to be debugged more closely to see why it missed a path.

Since @isaacbrodsky can't look into it at the moment, could we add a comment to revisit this problem in the future? (The only downside is that it might prevent usage of this new function in situations it would be valid in, but since there is no general-purpose fallback here even for cases where this would have failed, that doesn't really change the perceptible end-user behavior.)

Makes sense, I will add a TODO comment here explaining what was removed.

coveralls · 2018-12-13T19:39:36Z

Coverage remained the same at 100.0% when pulling ab0f50c on nrabinowitz:hex-line into 1fa9106 on uber:master.

dfellis · 2018-12-13T20:01:16Z

src/apps/testapps/testH3Line.c

+    }
+}
+
+SUITE(h3Distance) {


Nit: this should be h3Line.

Whoops, good catch. Will fix.

dfellis · 2018-12-13T20:09:16Z

src/h3lib/lib/localij.c

+ * @return 0 on success, or another value on failure.
+ */
+int H3_EXPORT(h3Line)(H3Index start, H3Index end, H3Index* out) {
+    int distance = H3_EXPORT(h3Distance)(start, end);


Unfortunate that this effectively has to be called twice (once for the mem allocation and once for the safeguard here).

Perhaps there can be two functions, here, one that takes the chunk of memory and it's size and one with this signature that takes just the chunk of memory, assumes that it's big enough, and calls h3Distance to determine the usable size (or fail out early).

This would allow h3Distance to conceivably be called only once by users wanting to squeeze as much performance out of these calls as they can (such as the potential polyfill algorithm to reduce memory consumption and maybe run quicker, too).

Well, h3Distance is constant time and pretty fast, so I'm not sure this is really an issue. polyfill, kRing, etc all have the same problem. But if we care, then the simplest solution is to require the caller to pass in the size of the memory allocation:

H3_EXPORT(h3Line)(H3Index start, H3Index end, H3Index* out, int numIndexes);

All callers ought to call h3LineSize in any case, and can just pass the result in. The only cost is a slightly uglier API that's inconsistent with kRing and others.

Well, if h3Distance doesn't add a significant amount of time, then we don't have to worry about it.

Only way to answer is with benchmarks, so I added one:

Current:

-- h3LineNear: 72.083000 microseconds per iteration (10000 iterations) -- h3LineFar: 3534.151000 microseconds per iteration (1000 iterations)

Pass in distance:

-- h3LineNear: 71.187000 microseconds per iteration (10000 iterations) -- h3LineFar: 3539.273000 microseconds per iteration (1000 iterations)

So you gain a few microseconds - not enough to make the API more complex.

For scale here, the near line is 40 hex long, the far line is 1824 hex long.

dfellis · 2018-12-13T20:16:40Z

src/h3lib/lib/localij.c

+    CoordIJK endIjk = {0};
+
+    // Convert H3 addresses to IJK coords
+    h3ToLocalIjk(start, start, &startIjk);


Just a comment on our experimentalH3ToLocalIj transforms: It's unfortunate that the coordinates are not offset by the origin coordinates in the calculation, then you would only have to call h3ToLocalIjk(start, end, &endIjk) because h3ToLocalIjk(start, start, &startIjk) would've been defined as (0, 0, 0). A bit less computation and the relative nature of the coordinate system would be more obvious to users.

@isaacbrodsky thoughts?

FWIW, I don't think it's any less computation, since you'd still be calculating h3ToLocalIjk(start, start, &startIjk) under the hood in order to get the coordinates for offset. In fact, it's probably worse, because calling h3ToLocalIjk repeatedly will perform the calculation of the offset every time - the only time you save work is when the origin is the same as the index you want to get coords for.

h3ToLocalIjk includes several branches and loops. I'd assume that three subtractions would be minimal in comparison to the rest of the function, and it would let you call that function once instead of twice and produce coordinates that are simpler to reason about.

But you'd need to get the coordinates to subtract, which is effectively an h3ToLocalIjk call on your origin, right? Right now, the origin is just used to get the base cell, and then the IJK is calculated for the target; if you offset by the origin, you'd need to calculate the IJK for the origin, the IJK for the target, and then translate by the origin. It's the additional IJK calculation that adds the perf impact, not the translation.

I could be wrong here, but pretty sure that in a case like h3Line, where you are finding the coordinates for indexes 1, 2, 3, ...N, you'd have N - 1 calls instead of the N we have now, but you'd actually be doing (N - 1) * 2 IJK calculations, instead of the N we do now.

dfellis · 2018-12-13T20:28:24Z

src/h3lib/lib/localij.c

+
+    CoordIJK currentIjk = {startIjk.i, startIjk.j, startIjk.k};
+    for (int n = 0; n <= distance; n++) {
+        cubeRound((float)startIjk.i + iStep * n, (float)startIjk.j + jStep * n,


Is there a reason to use float over double here? Less memory usage, but there's precision loss that could affect long lines at very high resolutions and make the line not completely contiguous, and there's no evidence double precision is any slower on modern hardware. Besides, with just a few variables in play being updated over and over again, I can't imagine doubles pushing the loop memory out of CPU cache.

No real reason other than thinking we didn't need the precision. Will update.

Add hexLine function to return the line of indexes between a given start and end

Nicholas Rabinowitz added 2 commits December 12, 2018 16:03

Add hexLine function

82f866b

Add caveats to h3Line description

be98a5c

nrabinowitz requested review from dfellis, jogly and isaacbrodsky December 13, 2018 19:33

nrabinowitz commented Dec 13, 2018

View reviewed changes

dfellis reviewed Dec 13, 2018

View reviewed changes

Nicholas Rabinowitz added 5 commits December 13, 2018 14:43

Code review updates, CHANGELOG

8f50efc

Add h3Line benchmark

4e70f3e

Fix formatting

e8d9019

Add h3Line and h3LineSize to docs

7fb0205

Add requested TODO comment

ab0f50c

dfellis approved these changes Dec 18, 2018

View reviewed changes

jogly approved these changes Dec 19, 2018

View reviewed changes

nrabinowitz merged commit b314e6d into uber:master Dec 19, 2018

nrabinowitz deleted the hex-line branch December 19, 2018 00:47

mrdvt92 pushed a commit to mrdvt92/h3 that referenced this pull request Jun 19, 2022

Merge pull request uber#165 from nrabinowitz/hex-line

837cf33

Add hexLine function to return the line of indexes between a given start and end

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add hexLine function to return the line of indexes between a given start and end #165

Add hexLine function to return the line of indexes between a given start and end #165

Add hexLine function to return the line of indexes between a given start and end #165

Add hexLine function to return the line of indexes between a given start and end #165

Conversation

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment