HexTree provides tree structures for efficiently representing geographic regions using H3 cells. It takes advantage of H3's hierarchical structure to automatically compact large regions and provide fast spatial queries.
The primary structures are:
- HexTreeMap: an H3 cell-to-value map.
- HexTreeSet: an H3 cell set for spatial containment testing.
You can think of HexTreeMap vs. HexTreeSet as HashMap vs. HashSet.
HexTree leverages H3's hierarchical cell structure in two key ways:
Hierarchical Queries: When you query for a cell, the tree returns a value even if only a parent cell was inserted. For instance, if you insert a low-res cell but later query for a higher-res child cell, the tree returns the value from the parent.
Automatic Compaction: With compaction, the tree can automatically coalesce 7 adjacent child cells into their parent cell, dramatically reducing memory usage. For very large regions, compaction can continue recursively to the lowest resolution cells (res-0), possibly removing millions of redundant cells. For example, 4,795,661 res-7 cells representing North America compact into just 42,383 elements.
The internal structure mirrors H3's hierarchy: the root contains 122 resolution-0 base cells, with each level below being a 7-ary tree (matching H3's 7 possible child cells per parent). The tree supports up to 15 levels of resolution, where the depth of a leaf node corresponds to its H3 cell resolution.
serde: support for serialization via serde.disktree: on-disk memory-mapped storage for large trees (enablesserde,byteorder, andmemmap).
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
