h3 icon indicating copy to clipboard operation
h3 copied to clipboard

Add vertex index modes

Open nrabinowitz opened this issue 6 years ago • 1 comments

The proposal is to add two new index modes (set in the mode bits): H3_VERTEX_MODE and H3_ICOSAEDGE_VERTEX_MODE, to represent a shared vertex with an H3 index. The intent is that each vertex shared by 3 cells (or two in the case of edge distortion vertexes) would be represented by a single index.

The advantages of this approach:

  • Shared vertices can be compared between hexagons with a strict equality check
  • Vertices can be represented and stored without the trig calls required to produce a lat/lon point
  • Vertex to lat/lon can be guaranteed to return the same result across different cells that share the vertex

At a minimum, this should open up significant performance and accuracy gains in h3SetToLinkedGeo and getH3UnidirectionalEdgeBoundary, and there are likely other uses as well.

The format of the index would be:

  • The H3 index of the "owner" cell. The owner would be one of the cells that share the vertex, determined by rules TBD that would identify the same owner regardless of which of the neighbors was being queried. The main work here is determining which cell owns a given vertex, particularly across cell and icosahedron edges.
  • The mode set to H3_VERTEX_MODE (for corner vertices shared by 3 cells) or H3_ICOSAEDGE_VERTEX_MODE (for edge distortion vertices shared by 2 cells)
  • The reserved bits used to identify the index of the vertex on the owner cell, using the index order used by h3ToGeoBoundary (we only have 3 reserved bits, which is why we need two different vertex modes)

We'd want a small suite of functions for dealing with the vertices, including:

  • void getH3Vertex(H3Index h3, H3Vertex *vertices)
  • H3Vertex getH3Vertex(H3Index h3, int vertIndex)
  • GeoCoord h3VertexToGeoCoord(H3Vertex vertex)

nrabinowitz avatar Jul 18 '18 18:07 nrabinowitz

Proposed stupidly simple algorithm for determining ownership:

  • Find all three neighbors (or two for distortion vertices) that share a vertex
  • Use the one with the numerically lowest index as the owner

There might be somewhat faster options, but I'm not sure we can avoid getting the neighbors in any case to deal with edges, and it has the advantage of obviously working for pentagons and base cells.

nrabinowitz avatar Jul 29 '18 16:07 nrabinowitz

Completed in H3 v4.0.0.

isaacbrodsky avatar Aug 23 '22 16:08 isaacbrodsky