4 releases (2 breaking)

0.3.1 May 1, 2023
0.3.0 Apr 28, 2023
0.2.0 Jan 29, 2023
0.1.0 Sep 21, 2022

#622 in Data structures

24 downloads per month

MIT/Apache

58KB
1K SLoC

CI Documentation

HexTree

hextree provides tree structures that represent geographic regions with H3 cells.

The primary structures are:

  • HexTreeMap: an H3 cell-to-value map.
  • HexTreeSet: an H3 cell set for hit-testing.

You can think of HexTreeMap vs. HexTreeSet as HashMap vs. HashSet.

How is this different from HashMap<H3Cell, V>?

The key feature of a hextree is that its keys (H3 cells) are hierarchical. For instance, if you previously inserted an entry for a low-res cell, but later query for a higher-res child cell, the tree returns the value for the lower res cell. Additionally, with compaction, trees can automatically coalesce adjacent high-res cells into their parent cell. For very large regions, the compaction process can continue to lowest resolution cells (res-0), possibly removing millions of redundant cells from the tree. For example, a set of 4,795,661 res-7 cells representing North America coalesces into a 42,383 element HexTreeSet.

A hextree's internal structure exactly matches the semantics of an H3 cell. The root of the tree has 122 resolution-0 nodes, followed by 15 levels of 7-ary nodes. The level of an occupied node, or leaf node, is the same as its corresponding H3 cell resolution.

Features

  • serde: support for serialization via serde.

License

Licensed under either of

at your option.

Contribution

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.

Dependencies

~170KB