Refactor edge boundary, implement core vertex mode logic #391

nrabinowitz · 2020-09-08T00:34:58Z

Changes

Adds a new module, vertex.c, which will eventually hold vertex mode functions.
Implements vertexNumForDirection, which allows us to get the number (index, in the traditional sense) of the topological vertex in a given direction. The logic here is based on determining the number of rotations of the vertexes compared to a given "base" arrangement of direction-to-vertex. The base arrangement occurs when a cell is on the "home" face of its base cell. Additional rotations are required when the cell appears on a different face from its base cell's home face.
Most of the rotation information is included in faceIjkBaseCells, but that table is not optimized for this lookup, and there are additional rules for pentagons and polar pentagons. I've created a new lookup table to facilitate this operation, baseCellVertexRotations, along with a script to generate it.
Using vertexNumForDirection and a small refactor of faceIjkToGeoBoundary, allowing it to take a start vertex and sequence length, I've refactored getH3UnidirectionalEdgeBoundary to stop comparing geo coordinates and instead look up the vertex directly based on the direction.
Adds additional exhaustive tests down to res 6 to catch more edge cases.

Benefits

Fixes getH3UnidirectionalEdgeBoundary at resolutions > 12 (see changes in testH3UniEdge.c), which were broken due to inaccuracies in comparing geo coordinates.
Speeds up getH3UnidirectionalEdgeBoundary by about 3x:

Before

    -- getH3UnidirectionalEdgeBoundary: 58.733300 microseconds per iteration (10000 iterations)

After

    -- getH3UnidirectionalEdgeBoundary: 18.856600 microseconds per iteration (10000 iterations)

Future Work

Implementing vertexNumForDirection and a more efficient version of getH3UnidirectionalEdgeBoundary set us up nicely for Vertex Mode functions and a significantly more efficient version of h3SetToLinkedGeo.

coveralls · 2020-09-08T00:37:21Z

Coverage increased (+0.02%) to 99.149% when pulling 7acd21a on nrabinowitz:edge-boundary-refactor into 50e1206 on uber:master.

src/h3lib/lib/baseCells.c

nrabinowitz · 2020-09-08T00:41:03Z

src/h3lib/lib/faceijk.c

 * @param g The spherical coordinates of the cell boundary.
 */
-void _faceIjkToGeoBoundary(const FaceIJK* h, int res, int isPentagon,
+void _faceIjkToGeoBoundary(const FaceIJK* h, int res, int start, int length,


There are two main changes to _faceIjkToGeoBoundary:

It now takes start and length to allow it to efficiently return only a subset of the vertex sequence

The caller is now responsible for switching between _faceIjkToGeoBoundary and _faceIjkPentToGeoBoundary, instead of passing in isPentagon. This is in part to limit the number of arguments, and in part because requesting all vertexes now requires passing in different lengths for hexes and pentagons.

There was only one other callsite, so this was an easy refactor.

src/h3lib/lib/faceijk.c

dfellis

Only one minor nit from my end. This is great! :)

src/h3lib/include/vertex.h

isaacbrodsky · 2020-09-08T16:57:32Z

src/apps/miscapps/generateBaseCellVertexRotations.c

+            // Get the res 2 pentagon, whose neighbors have the same base cell
+            // and are unambiguously on the correct faces


Why is res 2 used here?

See the comment.

res 0 doesn't have any cells other than the base cell

res 1 cells cross two faces

res 2 cells are each on a single face, so there's no ambiguity about whether they have the right baseCell/face pair

I assume I could use any Class II resolution other than 0.

src/h3lib/lib/faceijk.c

src/h3lib/lib/vertex.c

…g over deleted pentagon subsequences

src/apps/miscapps/generatePentagonDirectionFaces.c

src/apps/testapps/testH3UniEdge.c

isaacbrodsky · 2020-09-14T21:13:31Z

src/apps/testapps/testVertex.c

+
+SUITE(Vertex) {
+    TEST(vertexNumForDirection_hex) {
+        H3Index origin = 0x823d6ffffffffff;


Does this need the L suffix?

Apparently not? We don't seem to be consistent, and there are a number of indexes in tests and benchmarks that don't include the L suffix and work fine. Is there a reason we thought it was required?

src/h3lib/lib/baseCells.c

src/h3lib/lib/vertex.c

isaacbrodsky · 2020-09-14T21:25:13Z

src/h3lib/lib/vertex.c

+ * Note that faces are in directional order, starting at J_AXES_DIGIT.
+ * This table is generated by the generatePentagonDirectionFaces script.
+ */
+static const PentagonDirectionFaces pentagonDirectionFaces[NUM_PENTAGONS] = {


aside: this table could be used to implement getPentagonIndexes rather than looping through the base cell table.

isaacbrodsky · 2020-09-14T21:26:36Z

src/h3lib/lib/vertex.c

+        // additional CCW rotation for polar neighbors or IK neighbors
+        if (fijk.face != baseFijk.face &&
+            (_isBaseCellPolarPentagon(baseCell) ||
+             fijk.face == dirFaces.faces[IK_AXES_DIGIT - 2])) {


I find this table a little confusing to use because it starts indexing directions starting with J (2) rather than 0 or 1. Perhaps at least extract the 2 to a reused constant for this function?

Will extract to a const. The alternative was adding two INVALID_FACE entries to each array in the table, which didn't seem worthwhile.

Added as a defined macro (I put this in the .c file itself, rather than the header file, because this seemed clearer and it didn't make sense to export it - let me know if you disagree).

src/h3lib/lib/vertex.c

Refactor edge boundary, implement core vertex mode logic

nrabinowitz requested review from dfellis, ajfriend and isaacbrodsky September 8, 2020 00:34

nrabinowitz commented Sep 8, 2020

View reviewed changes

src/h3lib/lib/baseCells.c Outdated Show resolved Hide resolved

nrabinowitz commented Sep 8, 2020

View reviewed changes

src/h3lib/lib/faceijk.c Outdated Show resolved Hide resolved

dfellis approved these changes Sep 8, 2020

View reviewed changes

src/h3lib/include/vertex.h Outdated Show resolved Hide resolved

isaacbrodsky reviewed Sep 8, 2020

View reviewed changes

nrabinowitz marked this pull request as draft September 8, 2020 18:20

nrabinowitz marked this pull request as ready for review September 8, 2020 21:27

Nicholas Rabinowitz added 19 commits September 11, 2020 23:24

Refactor getH3UnidirectionalEdgeBoundary to use directional matching

8c02d5e

Fix bug in pentagon-to-neighbor edges

16254ce

Move new logic into vertex module

d62902c

Better use of invalid codes

fc714a2

Latest fixes, iterate more res 5 cells

ec9a635

Add script to generate rotation table, fix logic around cells rotatin…

3526f2f

…g over deleted pentagon subsequences

Comment fixes, add tests for vertexNumForDirection

0b248db

comment fix

0a38c22

comment fix 2

653fa08

Tweaks to improve coverage

f3ad4b4

Formatting fix

87b27c1

More coverage tweaks

3a19457

Drop new lookup table, replace with pentagonDirectionFaces

f870593

Drop unused struct

9d59b18

Drop extern const

348ee88

Add tests, named const for _baseCellToCCWrot60

5f6df01

Improve coverage

a9ba40d

Fix coverage exclusion

c8123e1

format

b31386a

Nicholas Rabinowitz added 2 commits September 11, 2020 23:24

More attempts to fix coverage, remove unreachable case

6b99853

Rename BaseCellOrient to BaseCellRotation

4f59c03

nrabinowitz force-pushed the edge-boundary-refactor branch from 88b2b71 to 4f59c03 Compare September 12, 2020 06:25

isaacbrodsky reviewed Sep 14, 2020

View reviewed changes

Code review tweaks

7acd21a

isaacbrodsky approved these changes Sep 24, 2020

View reviewed changes

nrabinowitz merged commit f8bbc4b into uber:master Sep 24, 2020

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

Merge pull request uber#391 from nrabinowitz/edge-boundary-refactor

a37a99a

Refactor edge boundary, implement core vertex mode logic

		// Get the res 2 pentagon, whose neighbors have the same base cell
		// and are unambiguously on the correct faces

Refactor edge boundary, implement core vertex mode logic #391

Refactor edge boundary, implement core vertex mode logic #391

Uh oh!

Conversation

nrabinowitz commented Sep 8, 2020

Changes

Benefits

Future Work

Uh oh!

coveralls commented Sep 8, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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!

Uh oh!

Uh oh!

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!

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!

Uh oh!

Uh oh!

Uh oh!

coveralls commented Sep 8, 2020 •

edited

Loading