h3 Documentation

File: README.md Copy Chapter

H3: A Hexagonal Hierarchical Geospatial Indexing System

H3 is a geospatial indexing system using a hexagonal grid that can be (approximately) subdivided into finer and finer hexagonal grids, combining the benefits of a hexagonal grid with S2's hierarchical subdivisions.

Documentation is available at https://h3geo.org/. Developer documentation in Markdown format is available under the dev-docs directory.

• Post bug reports or feature requests to the GitHub Issues page
• Ask questions by posting to the H3 tag on StackOverflow
• There is also an H3 Slack workspace

Installing Copy Chapter

We recommend using prebuilt bindings if they are available for your programming language. Bindings for Java, JavaScript, Python, and others are available.

On macOS, you can install H3 using brew:

brew install h3

Otherwise, to build H3 from source, please see the following instructions.

Building from source Copy Section

Still here? To build the H3 C library, you'll need a C compiler (tested with gcc and clang), CMake, and Make. If you intend to contribute to H3, you must have clang-format installed and we recommend installing ccmake and LCOV to configure the cmake arguments to build and run the tests and generate the code coverage report. We also recommend using gcc for the code coverage as some versions of clang generate annotations that aren't compatible with lcov. Doxygen is needed to build the API documentation.

Install build-time dependencies

• Alpine

# Installing the bare build requirements
apk add cmake make gcc libtool musl-dev

• Debian/Ubuntu

# Installing the bare build requirements
sudo apt install cmake make gcc libtool
# Installing useful tools for development
sudo apt install clang-format cmake-curses-gui lcov doxygen

• macOS (using brew)

First make sure you have the developer tools installed and then

# Installing the bare build requirements
brew install cmake
# Installing useful tools for development
brew install clang-format lcov doxygen

• Windows (Visual Studio)

You will need to install CMake and Visual Studio, including the Visual C++ compiler. For building on Windows, please follow the Windows build instructions.

• FreeBSD

# Installing the build requirements
sudo pkg install bash cmake gmake doxygen lcov

Compilation

When checking out the H3 Git repository, by default you will check out the latest
development version of H3. When using H3 in an application, you will want to check
out the most recently released version:

git checkout v$(<VERSION)

From the repository root, you can compile H3 with:

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make

All subsequent make commands should be run from within the build directory.

Note: There are several ways to build H3 with CMake; the method above is just one example that restricts all build artifacts to the build directory.

You can install system-wide with:

sudo make install

If using the method above, from the repository root, you can clean all build artifacts with:

rm -rf build

Testing

After making the project, you can test with make test.
You can run a faster test suite that excludes the most expensive tests with make test-fast.

Coverage

You can generate a code coverage report if lcov is installed, and if the project was built with the CMAKE_BUILD_TYPE=Debug and ENABLE_COVERAGE=ON options.
For example, from a clean repository, you could run:

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Debug -DENABLE_COVERAGE=ON ..
make
make coverage

You can then view a detailed HTML coverage report by opening coverage/index.html in your browser.

Benchmarks

You can run timing benchmarks by building with the CMAKE_BUILD_TYPE=Release, and running make benchmarks:

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make
make benchmarks

Documentation

You can build developer documentation with make docs if Doxygen was installed when CMake was run. Index of the documentation will be dev-docs/_build/html/index.html.

After making the project, you can build KML files to visualize the hexagon grid with make kml. The files will be placed in KML.

To build the documentation website, see the website/ directory.

Usage Copy Chapter

From the command line Copy Section

To get the H3 index for some location:

./bin/latLngToCell --resolution 10 --latitude 40.689167 --longitude -74.044444

10 is the H3 resolution, between 0 (coarsest) and 15 (finest). The coordinates entered are the latitude and longitude, in degrees, you want the index for (these coordinates are the Statue of Liberty). You should get an H3 index as output, like 8a2a1072b59ffff.

You can then take this index and get some information about it, for example:

./bin/cellToBoundary --index 8a2a1072b59ffff

This will produce the vertices of the hexagon at this location:

8a2a1072b59ffff
{
   40.690058601 -74.044151762
   40.689907695 -74.045061792
   40.689270936 -74.045341418
   40.688785091 -74.044711031
   40.688935993 -74.043801021
   40.689572744 -74.043521377
}

You can get the center coordinate of the hexagon like so:

./bin/cellToLatLng --index 8a2a1072b59ffff

This will produce some coordinate:

40.6894218437 -74.0444313999

From C Copy Section

The above features of H3 can also be used from C. For example, you can compile and run examples/index.c like so:

cc -lh3 examples/index.c -o example
./example

You should get output like:

The index is: 8a2a1072b59ffff
Boundary vertex #0: 40.690059, -74.044152
Boundary vertex #1: 40.689908, -74.045062
Boundary vertex #2: 40.689271, -74.045341
Boundary vertex #3: 40.688785, -74.044711
Boundary vertex #4: 40.688936, -74.043801
Boundary vertex #5: 40.689573, -74.043521
Center coordinates: 40.689422, -74.044431

Contributing Copy Chapter

Pull requests and Github issues are welcome. Please see our contributing guide for more information.

Before we can merge your changes, you must agree to the Uber Contributor License Agreement.

Legal and Licensing Copy Chapter

H3 is licensed under the Apache 2.0 License.

DGGRID
Copyright (c) 2015 Southern Oregon University

File: src/apps/miscapps/README.md Copy Chapter

miscapps

These apps generate data, either static tables used in the library or test data used in regression tests.

Generate Test Data Copy Chapter

For a specific base cell at a specific res:

./bin/cellToLatLngHier -p 800bfffffffffff -r 8 > tests/inputfiles/bc05r08centers.txt
./bin/cellToBoundaryHier -p 800bfffffffffff -r 8 > tests/inputfiles/bc05r08cells.txt

For all cells at a given res:

./bin/h3ToHier -r 0 | xargs -I {} ./bin/cellToBoundaryHier -p {} -r 3 > tests/inputfiles/res03cells.txt

For a random sample of cells at a given res:

./bin/mkRandGeoBoundary -n 5000 -r 5 > tests/inputfiles/rand05cells.txt

File: src/apps/fuzzers/README.md Copy Chapter

Fuzzer harnesses for H3

This directory contains helper programs for testing the H3 library using the
American fuzzy lop/
AFL++ or
libFuzzer fuzzers.
Fuzzing is a technique for discovering crashes and other edge cases in code
such as the H3 core library.

Function coverage

The public API of H3 is covered in the following fuzzers:

Internal function coverage Copy Chapter

In addition to the public API, the following internal functions of H3 are covered in fuzzers:

libFuzzer Usage

libFuzzer is one of the supported fuzzing drivers.

This is the fuzzer used in oss-fuzz.

Build Copy Chapter

You must build H3 with Clang and enable support for libFuzzer.

CC=clang cmake -DENABLE_LIBFUZZER=ON .
make fuzzers

Run Copy Chapter

To begin fuzzing, execute the fuzzer binary:

fuzzerLatLngToCell

For command line options including how to specify a test corpus, consult the libFuzzer documentation.

AFL Usage

AFL/AFL++ are supported fuzzing drivers.

Installation Copy Chapter

apt install afl-clang

(There is also an afl-cov which looks interesting but isn't necessary.)

Build Copy Chapter

You must compile with the instrumented compiler:

CXX=afl-clang++ CC=afl-clang cmake .
make fuzzers

Generate a blank (zeroed) test case file. This will not be very a interesting test case but is usedful
for having files of the right size.

fuzzerLatLngToCell --generate bytes24

An individual fuzzer run is invoked as follows. The argument is a file containing the number of bytes needed.

fuzzerLatLngToCell bytes24

Run Copy Chapter

To begin running the fuzzer, run the following. The testcase directory (testcase_dir) should contain a file
with at least the right number of bytes that the fuzzer will read (this can be generated using the --generate
option above.)

afl-fuzz -i testcase_dir -o findings_dir -- fuzzerLatLngToCell @@

File: website/docs/core-library/cellToBoundaryDesc.md Copy Chapter

id: cellToBoundaryDesc title: Generate the cell boundary in latitude/longitude coordinates of an H3Index cell sidebar_label: Generate the cell boundary in latitude/longitude coordinates of an H3Index cell slug: /core-library/cellToBoundaryDesc Copy Chapter

This operation is performed by function cellToBoundary. See the comments in the function source code for more detail.

The conversion is performed as a series of coordinate system conversions described below. See the page Coordinate Systems used by the H3 Core Library for more information on each of these coordinate systems.

1. We note that the cell vertices are the center points of cells in an aperture 3 grid one resolution finer than the cell resolution, which we term a substrate grid. We precalculate the substrate ijk coordinates of a cell with ijk coordinates (0,0,0), adding additional aperture 3 and aperture 7 (if required, by Class III cell grid) substrate grid resolutions as required to transform the vertex coordinates into a Class II substrate grid.

2. The function _faceIjkToGeoBoundary calculates the ijk coordinates of the cell center point in the appropriate substrate grid (determined in the last step), and each of the substrate vertices is translated using the cell center point ijk. Each vertex ijk is then transformed onto the appropriate face and Hex2d coordinate system using the approach taken in finding a cell center point. If adjacent vertices lie on different icosahedron faces a point is introduced at the intersection of the cell edge and icosahedron face edge.

3. The Hex2d coordinates are then converted to latitude/longitude using _hex2dToGeo.

File: website/docs/core-library/cellToLatLngDesc.md Copy Chapter

id: cellToLatLngDesc title: Determine the latitude/longitude coordinates of the center point of an H3Index cell sidebar_label: Determine the latitude/longitude coordinates of the center point of an H3Index cell slug: /core-library/cellToLatLngDesc Copy Chapter

This operation is performed by function cellToLatLng. See the comments in the function source code for more detail.

The conversion is performed as a series of coordinate system conversions described below. See the page Coordinate Systems used by the H3 Core Library for more information on each of these coordinate systems.

1. The function _h3ToFaceIjk then converts the H3 index to the appropriate icosahedron face number and normalized ijk coordinate's on that face's coordinate system as follows:

• We start by assuming that the cell center point falls on the same icosahedron face as its base cell.
• It is possible that the cell center point lies on an adjacent face (termed an overage in the code), in which case we would need to use a projection centered on that adjacent face instead. We recall that normalized ijk coordinates have at most two non-zero components, and that in a face-centered Class II system the sum of those components is a resolution-specific constant value for cells that lie on the edge of that icosahedral face.
  We determine whether an overage exists by taking the sum of the ijk components, and if there is an overage the positive ijk components indicate which adjacent face the cell center lies on. A lookup operation is then performed to find the appropriate rotation and translation to transform the ijk coordinates into the adjacent face-centered ijk system.

2. The face-centered ijk coordinates are then converted into corresponding Hex2d coordinates using the function _ijkToHex2d.
3. The function _hex2dToGeo takes the Hex2d coordinates and scales them into face-centered gnomonic coordinates, and then performs an inverse gnomonic projection to get the latitude/longitude coordinates.

File: website/docs/core-library/compilation-options.md Copy Chapter

id: compilation-options title: Compilation options sidebar_label: Compilation options slug: /core-library/compilation-options Copy Chapter

A number of options in CMake can be set when compiling the H3 core library. These are relevant for building
different ways of using and testing the library and do not affect the underlying algorithms.

When configuring with CMake, an option may be specified using -D on the command line, like so for setting
CMAKE_BUILD_TYPE to Release:

cmake .. -DCMAKE_BUILD_TYPE=Release

Boolean options should be set to ON or OFF, like so:

cmake .. -DBUILD_TESTING=OFF

AUDIT_SOURCE_FILE_LIST Copy Chapter

Whether to glob the list of source files and compare it to the ALL_SOURCE_FILES and EXAMPLE_SOURCE_FILES lists
defined in CMake. This is a quality control measure to ensure that the source file list in CMakeLists.txt actually
matches the sources in the repository and is not missing any files.

BUILD_ALLOC_TESTS Copy Chapter

Whether to build the parts of the test suite that exercise the H3_ALLOC_PREFIX feature.

BUILD_BENCHMARKS Copy Chapter

Whether to build the benchmark suite.

BUILD_COUNTRY_BENCHMARKS Copy Chapter

Whether to build benchmarks that use Natural Earth geometries.

The geometries will be downloaded at build time using Node.

BUILD_FILTERS Copy Chapter

Whether to build the H3 command line filter executables.

BUILD_GENERATORS Copy Chapter

Whether to build generator executables used in the development of H3. This is not required for
building the library as the output of these generators is checked in.

BUILD_TESTING Copy Chapter

Whether to build the test suite.

BUILD_FUZZERS Copy Chapter

Whether to build the fuzzer suite.

ENABLE_LIBFUZZER Copy Chapter

Whether to build the fuzzers with libFuzzer (this expects to be used with Clang). If OFF, a main function suitable for use with American fuzzy lop is included.

CMAKE_BUILD_TYPE Copy Chapter

Should be set to Release for production builds, and Debug in development.

ENABLE_COVERAGE Copy Chapter

Whether to compile Debug builds with coverage instrumentation (compatible with GCC, Clang, and lcov). This also excludes defensive code in the library that should not be counted against coverage because it is unreachable.

ENABLE_DOCS Copy Chapter

Whether to build the Doxygen documentation. This is not the same as the H3 website,
but is rather the documentation for the internal C library functions.

ENABLE_FORMAT Copy Chapter

Whether to enable using clang-format-14 to format source files before building. This should be enabled
before submitting patches for H3 as continuous integration will fail if the formatting does not match.

Only this version of clang-format should be used to format the sources as new releases of clang-format
can change defaults, causing unintended churn of source code formatting.

ENABLE_LINTING Copy Chapter

Whether to enable using clang-tidy to lint source files when building. Only invoked when
Makefile or Ninja CMake generators
are used.

H3_ALLOC_PREFIX Copy Chapter

Used for directing the library to use a different set of functions for memory management.

H3_PREFIX Copy Chapter

Used for renaming the public API.

PRINT_TEST_FILES Copy Chapter

If enabled, CMake will print which CTest test case corresponds to which input file.

ENABLE_WARNINGS Copy Chapter

Whether to enable all compiler warnings. (i.e. -Wall)

WARNINGS_AS_ERRORS Copy Chapter

Whether to treat compiler warnings as errors. While a useful tool for ensuring software quality, this should not be enabled
for production builds as compiler warnings can change unexpectedly between versions. This is intended to be used with
ENABLE_WARNINGS on.

WRAP_VALGRIND Copy Chapter

Whether to wrap invocations of the test suite with valgrind (if available).

File: website/docs/core-library/coordsystems.md Copy Chapter

id: coordsystems title: Coordinate systems sidebar_label: Coordinate systems slug: /core-library/coordsystems Copy Chapter

The H3 Core Library uses the following coordinate systems internally.

IJK Coordinates Copy Chapter

Discrete hexagon planar grid systems naturally have 3 coordinate axes spaced 120° apart. We refer to such a system as an ijk coordinate system, for the three coordinate axes i, j, and k. A single ijk coordinate triplet is represented in the H3 Core Library using the structure type CoordIJK.

Using an ijk coordinate system to address hexagon grid cells provides multiple valid addresses for each cell. Normalizing an ijk address (function _ijkNormalize) creates a unique address consisting of the minimal positive ijk components; this always results in at most two non-zero components.

FaceIJK Coordinates Copy Chapter

The H3 Core Library centers an ijk coordinate system on each face of the icosahedron; the combination of a face number and ijk coordinates on that face's coordinate system is represented using the structure type FaceIJK.

Each grid resolution is rotated ~19.1° relative to the next coarser resolution. The rotation alternates between counterclockwise and clockwise at each successive resolution, so that each resolution will have one of two possible orientations: Class II or Class III (using a terminology coined by R. Buckminster Fuller). The base cells, which make up resolution 0, are Class II.

Hex2d Coordinates Copy Chapter

A Hex2d coordinate system is a cartesian coordinate system associated with a specific ijk coordinate system, where:

• the origin of the Hex2d system is centered on the origin cell of the ijk system,
• the positive x-axis of the Hex2d system is aligned with the i-axis of the ijk system, and
• 1.0 unit distance in the Hex2d system is the distance between adjacent cell centers in the ijk coordinate system.

Hex2d coordinates are represented using the structure type Vec2d.

Local IJ Coordinates Copy Chapter

Algorithms working with hexagons may want to refer to grid coordinates that are not interrupted by base cells or faces. These coordinates have 2 coordinate axes spaced 120° apart, with the coordinates anchored by an origin H3 index.

• local coordinates are only comparable when they have the same origin index.
• local coordinates are only valid near the origin. Pratically, this is within the same base cell or a neighboring base cell, except for pentagons.
• the coordinate space may have deleted or warped regions due to pentagon distortion.
• there may be multiple coordinates for the same index, with the same origin.
• the origin may not be at (0, 0) in the local coordinate space.

Local IJ coordinates are represented using the structure type CoordIJ and an associated origin H3Index.

File: website/docs/core-library/creating-bindings.md Copy Chapter

id: creating-bindings title: Creating bindings for H3 sidebar_label: Creating bindings slug: /core-library/creating-bindings Copy Chapter

H3 is a C library, in part to make it simpler to create bindings for different programming languages. Each language usually has its own way to bind to C functions, but this document can serve as a starting point and list of tips.

There may already be H3 bindings available for your language of choice.

Function naming Copy Chapter

The make binding-functions target produces a file binding-functions containing a list of function in the H3 public API, one per line. You can use this as part of your build process to check how much of the H3 public API your bindings expose. This list does not include memory management functions that are needed to allocate arrays to be passed to the H3 API.

Keeping similar names and purposes for functions can make it easier for your users to use the H3 API Reference.

Community Copy Chapter

When ready, make a pull request to add your binding to the H3 documentation website.

Documentation Copy Chapter

To be included in the H3 API reference, your binding should:

• Be reasonably up to date with uber/h3.
• Include bindings for the relevant functions in the output of make binding-functions. For example, stringToH3 may not be necessary if your bindings only supports string H3 indexes.
• Use the major and minor version of the version of H3 bound. For example, when binding H3 version 3.2.1, a valid binding version would be 3.2.0, but 4.2.1 would not be valid.

File: website/docs/core-library/custom-alloc.md Copy Chapter

id: custom-alloc title: Memory allocation sidebar_label: Memory allocation slug: /core-library/custom-alloc Copy Chapter

H3's approach to memory management is to rely on memory allocated by the caller as much as possible. This allows memory to be managed by an external framework.

In some cases (for example, polygonToCells), H3 allocates heap memory. When this is needed, it uses the standard C memory allocation functions.

Custom Memory Allocators Copy Chapter

:::caution

On some systems, such as Windows, the undefined symbols cannot be undefined at build time. Further changes to the H3 build are needed to provide custom implementations.

:::

:::caution

There are a few algorithms like kRing that still use the call stack to recurse and could run out of memory that way.

:::

H3 supports replacing the memory management functions (malloc, calloc, realloc, free) used by the library at build time. This can be used to integrate H3 within a managed framework.

When using custom memory allocators, H3 prefixes the names of memory allocation functions with the string you specify. The application linking H3 must have the prefixed replacement functions defined, or you must change the H3 build to link against the prefixed replacement functions.

When building H3, specify the H3_ALLOC_PREFIX option to your prefix of choice, as below:

cmake -DH3_ALLOC_PREFIX=my_prefix_ .

Then, in your application using H3, implement the following functions, replacing my_prefix_ with the prefix you chose above:

void* my_prefix_malloc(size_t size);
void* my_prefix_calloc(size_t num, size_t size);
void* my_prefix_realloc(void* ptr, size_t size);
void my_prefix_free(void* ptr);

:::info

H3 does not currently use realloc.

:::

Link to H3 as you would have without the custom allocators. The custom allocators will be used for allocating heap memory in H3.

File: website/docs/core-library/filters.md Copy Chapter

id: filters title: Unix-style Filters for H3 sidebar_label: Unix-style Filters for H3 slug: /core-library/filters Copy Chapter

The directory src/apps/filters contains unix-style stdin/stdout filters that perform conversions between integer H3 indexes and other useful types. It currently contains the filters listed in the table below. See the header comments in each application source code file for more information.

Filters are experimental and are not part of the semantic version of the H3 library.

All latitude/longitude coordinates are in decimal degrees. See the H3 Index Representations page for information on the integer H3Index.

Unix Command Line Examples Copy Chapter

• find the index for coordinates at resolution 5

  latLngToCell --resolution 5 --latitude 40.689167 --longitude -74.044444

• output the cell center point for H3Index 845ad1bffffffff

  cellToLatLng --index 845ad1bffffffff

• output the cell boundary for H3Index 845ad1bffffffff

  cellToBoundary --index 845ad1bffffffff

• find the components for the H3Index 845ad1bffffffff

  h3ToComponents --index 845ad1bffffffff

• output all indexes within distance 1 of the H3Index 845ad1bffffffff

  kRing -k 1 --origin 845ad1bffffffff

• output all hexagon indexes within distance 2 of the H3Index 845ad1bffffffff

  hexRange -k 2 --origin 845ad1bffffffff

Note that the filters cellToLatLng and cellToBoundary take optional arguments that allow them to generate kml output. See the header comments in the corresponding source code files for details.