DOCSEARCHbyAlgolia
Submit Docs

H3 Hexagonal Hierarchical Geospatial Indexing System

repository·master·Indexed 27 days ago

https://github.com/uber/h3

H3 is an open-source hexagonal hierarchical geospatial indexing system that partitions the world into hexagonal cells. The H3 Core Library, written in C, provides functionality for converting latitude/longitude coordinates to H3 cells, finding cell centers, boundary geometry, and neighbors. It is available via prebuilt bindings for Java, JavaScript, and Python, and includes command line tools for common indexing tasks.

Tokens
33.6K
Snippets
99
Records
198
Agent score
87%

What's inside H3

  1. Overview of H3 Geospatial Indexing

    master

    H3 is an open-source hexagonal hierarchical geospatial indexing system licensed under Apache 2. It partitions the world into hexagonal cells. The H3 Core Library, written in C, provides functionality for:

    • Converting latitude/longitude coordinates to H3 cells.
    • Finding the center of H3 cells.
    • Finding the boundary geometry of H3 cells.
    • Finding neighbors of H3 cells.

    Note that H3 provides exact logical containment but only approximate geometric containment across the cell hierarchy. This means points within child cells may occasionally belong to different parent cells because child cells are not always entirely geometrically contained by a single parent cell.

  2. Overview of the H3 Geospatial Indexing System

    master

    H3 is a discrete global grid system consisting of a multi-precision hexagonal tiling of the sphere with hierarchical indexes. It uses a spherical coordinate system (WGS84/EPSG:4326) and is based on an icosahedron projected onto a sphere using an inverse face-centered polyhedral gnomonic projection.

    Key characteristics:

    • Grid Structure: The grid is constructed by recursively creating higher precision hexagon grids. Because a sphere cannot be tiled entirely with hexagons, every resolution contains exactly 12 pentagons (one at each icosahedron vertex).
    • Resolutions: Resolution 0 consists of 122 base cells (110 hexagons and 12 pentagons). H3 provides 15 finer resolutions beyond resolution 0. The finest resolution (15) has cells with an area of less than 1 m².
    • Scaling: Each subsequent resolution uses an aperture 7 spacing, meaning each hexagon has 1/7th the area of its parent cell at the next coarser resolution.

  4. Understand the benefits of hexagonal aggregation with H3

    master

    H3 uses a hexagonal hierarchical geospatial indexing system for bucketing location data. Unlike square or triangular grids, hexagons provide several advantages for spatial analysis:

    • Equidistant Neighbors: All six immediate neighbors of a hexagon are at the same distance from the center, allowing for simpler and more accurate analysis of movement and gradients.
    • Circular Approximation: Hexagonal rings expand in a way that approximates circles, which is useful for modeling radial phenomena.
    • Optimal Space-Filling: Hexagons are more efficient at filling space with a smaller margin of error compared to square tiles.

    This makes H3 ideal for aggregating location data (e.g., car locations in a city) to create smooth spatial gradients.

  5. Understand H3 technical terminology

    master

    To use H3 accurately, especially when calling APIs that distinguish between different geometric shapes, follow these technical definitions:

    • H3Index: An unsigned 64-bit integer representing any H3 object (hexagon, pentagon, directed edge, etc.). It is often represented as a 15 or 16-character hexadecimal string (e.g., '8928308280fffff').
    • mode: An integer encoded within the H3Index that describes the type of object being represented.
    • cell (or H3 cell): A geometric/geographic unit polygon corresponding to an H3Index of mode 1. This is the general term for both hexagons and pentagons.
    • hexagon: An H3 cell that is a topological hexagon (has 6 neighbors). Note that some hexagons may not be geometric hexagons due to distortion.
    • pentagon: An H3 cell that is a topological pentagon (has 5 neighbors).
    • directed edge: A traversal from an origin cell to an adjacent destination cell, corresponding to an H3Index of mode 2.
    • grid: The graph where nodes are H3 cells and edges are pairs of adjacent cells.
    • base cell: One of the 122 cells at resolution 0 (110 hexagons and 12 pentagons). Every other cell in H3 is a child of a base cell. The base cell number (0–121) is encoded into the H3Index.
    • boundary: The list of geometric points enclosing an H3 cell. In the codebase, this is represented by the CellBoundary struct.
    • H3_NULL: A value equivalent to 0 that is guaranteed to never be a valid H3Index. It is used by functions to denote errors or missing data, similar to NaN for floating point numbers.

  6. Understand H3 Hierarchical Indexing and Aperture 7

    master

    H3 is a hierarchical geospatial index where every hexagonal cell (up to the maximum supported resolution) has seven child cells. This subdivision is known as aperture 7.

    Key Concepts:

    • Approximate Geographic Containment: Because hexagons do not subdivide perfectly into seven smaller hexagons, truncating the precision of an H3 index (moving up or down the hierarchy) provides an approximation of geographic containment. The borders of hexagons at a specific resolution remain exact.
    • Exact Logical Containment: While geographic containment is approximate, logical containment within the index is exact. You can use H3 as an exact logical index for data at a specific resolution.
    • Efficiency: Changing precision using functions like h3ToParent and h3ToChildren is highly efficient, utilizing bitwise operations.
    • Data Aggregation: The hierarchy allows for encoding spatial uncertainty. For example, you can index a location at a coarser resolution if GPS precision is low, or aggregate fine-grained data into parent cells when data density is low.

  8. Understand H3 Terminology and Concepts

    master

    To use H3 accurately, especially when dealing with edge cases like pentagons or icosahedron boundaries, use the following technical definitions:

    • H3Index: An unsigned 64-bit integer representing any H3 object (hexagon, pentagon, directed edge, etc.). It is often represented as a 15 or 16-character hexadecimal string (e.g., '8928308280fffff').
    • cell or H3 cell: A geometric/geographic unit polygon in the H3 grid (mode 1). This is the general term for both hexagons and pentagons.
    • hexagon: An H3 cell that is a topological hexagon (has 6 neighbors).
    • pentagon: An H3 cell that is a topological pentagon (has 5 neighbors).
    • directed edge: A traversal from an origin cell to an adjacent destination cell (mode 2).
    • grid: The graph where nodes are H3 cells and edges are pairs of adjacent cells.
    • base cell: One of the 122 cells at resolution 0. Every other cell is a child of a base cell. The "base cell number" (0–121) is encoded into the H3Index.
    • boundary: The list of lat/lng points enclosing an H3 cell. Note that a cell's boundary may contain more than 6 points if it is not a geometric hexagon due to distortion.
    • H3_NULL: A value equivalent to 0 used to denote an error or missing data in arrays of H3Index. It is guaranteed to never be a valid H3Index.

  9. Understand the relationship between Placekey and H3

    master

    Placekey is a system for encoding Points of Interest (POIs) that incorporates H3 within its identifier. A Placekey consists of two parts:

    1. What Part: Encodes the specific POI.
    2. Where Part: Encodes the location using an H3 cell index at resolution 10 (using an alternate string encoding).

    Placekey 'Where Parts' can be losslessly converted to and from their equivalent H3 indexes. For example, the Placekey zzw-22y@5vg-7gt-qzz has a 'Where Part' (5vg-7gt-qzz) that represents the H3 index 8a283082a677fff.

  10. Error handling in language bindings

    master
    Language bindings translate H3 error codes into the idiomatic error handling mechanism of that language. For example, Java bindings convert error codes into Java Exceptions. While it is preferable to retain the error code, it is acceptable to elide them in bindings, provided they include formatted error messages.

  11. Understand the H3 Cell Index (Mode 1)

    master

    An H3 Cell index (Mode 1) represents a specific cell (hexagon or pentagon) at a given resolution. The index is a 64-bit integer that encodes the hierarchy of the cell. The hierarchy starts with a resolution 0 base cell, followed by a sequence of digits (0-6) representing the child cells at each subsequent resolution level. For the 12 pentagonal cells, the indexing hierarchy produced by sub-digit 1 is removed at all resolutions.

    Key concepts:

    • Hierarchical Indexing: Each digit $d_i$ specifies one of the 7 cells centered on the parent cell.
    • Central Place Indexing: The assignment of digits 0-6 uses a Central Place Indexing arrangement.
    • Resolution: Cells are organized from resolution 0 up to 15.

  12. Convert a point to an H3 cell identifier

    master

    Use h3.latLngToCell(lat, lng, res) to find the H3 hexagonal cell that contains a specific latitude and longitude. The res parameter specifies the resolution of the cell.

    function example() {
  const lat = 37.7955;
  const lng = -122.3937;
  const res = 10;
  return h3.latLngToCell(lat, lng, res);
}