uber / uber/h3

Add function for returning the H3 indices of each endpoint of a directed edge

Open
#808 5 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C
Stars
6.5k
Forks
627
Avg merge
3d 21h
Merged PRs (30d)
6

Description

After looking through the code, it appears that calculating the IJK coordinates for a face is part of the process for computing a cell boundary, and functions exist internally to convert these coordinates to H3 indices. I believe exposing a function to convert a directed edge to endpoint indices directly is an easy add to the library, and I have one drafted, but want to confirm this is not already implemented in a way I'm not spotting.

The use case that sparks this need is as follows:

  • I have a large dataset that's binned by H3 cells. My goal is to draw the boundaries between cells that don't share a value in the dataset - call it the color of a cell for the sake of illustration. Rendering this is trivial once I have a set of sequenced points similar to a GeoJSON LineString. For my purposes, the directed nature of the edges H3 has is fine - a boundary inside cell A, and a boundary inside cell B, where A and B are adjacent, are actually preferred.
  • The easy answer to this problem would be to set up a mapping from cell colors to cell indices, and then use polygonToCells to get a boundary. This works on a small scale. Unfortunately, the dataset I have is too large for this solution.
  • I'm already rendering underlying elevation data with a system that renders cells at resolution $N$ using chunks at resolution $\lfloor \sqrt{\text{max}(0, N - 1)} \rfloor$. This has proven to be performant enough for my purposes, even with elevation stored at the same resolution as cell color.
  • I could, per chunk, create a mapping of cell colors to indices and use polygonToCells as mentioned above. This process works fine. This will result in borders along the edge of a chunk, though, even when the adjacent cells share the same color.
  • I can, on a per chunk basis, get the boundary segments of all the directed edges that separate cells with two different colors, then assemble these into linestrings with the following algorithm:
    • Push the first segment onto the return list
    • For each subsequent segment in the raw list, check if it shares an endpoint with one in the return list, and either extend the return segment found or add the segment as a new segment in the return list.
    • Mark closed loops at the end to avoid rendering the same vertex twice (not essential.)
  • The above involves a lot of vector distance comparisons, even using squared magnitudes.

Creating/exposing the function mentioned will simplify this into a series of integer equality comparisons, and I suspect there are likely other use cases for allowing users to directly get the vertices associated with edges.

Preliminary testing indicates that the below seems to do the trick. I'll put together a proper pull request if this isn't duplicating effort.

/**
 * Provides the vertices at either end of the directed edge.
 * @param edge The directed edge H3Index
 * @param vStart The starting vertex H3Index
 * @param vEnd The starting vertex H3Index
 */
H3Error H3_EXPORT(directedEdgeToVertices)(H3Index edge, H3Index* vStart, H3Index* vEnd) {
    // Get the origin and neighbor direction from the edge
    Direction direction = H3_GET_RESERVED_BITS(edge);
    H3Index origin;
    H3Error originResult = H3_EXPORT(getDirectedEdgeOrigin)(edge, &origin);
    if (originResult) {
        return originResult;
    }

    // Get the start vertex for the edge
    int startVertex = vertexNumForDirection(origin, direction);
    if (startVertex == INVALID_VERTEX_NUM) {
        // This is not actually an edge (i.e. no valid direction),
        // so return no vertices.
        return E_DIR_EDGE_INVALID;
    }

    H3Error err = H3_EXPORT(cellToVertex)(origin, startVertex, vStart);
    if (err) {
        return err;
    }
    err = H3_EXPORT(cellToVertex)(origin, startVertex + 1, vEnd);
    if (err) {
        return err;
    }
    return E_SUCCESS;

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Review the existing directed-edge entry point getDirectedEdgeOrigin, the cellToVertex API, and the internal boundary conversion logic described in the issue. Confirm whether endpoint vertices can be exposed without duplicating existing behavior, then verify that valid directed edges return both endpoint indices and invalid edges return the appropriate error.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
api
Issue type
Feature
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.