Giter VIP home page Giter VIP logo

hextree's Introduction

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.

hextree's People

Contributors

jaykickliter avatar madninja avatar vagabond avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar

Forkers

isgasho

hextree's Issues

Do not re-export h3ron crate

The reexport is causing problems for at least one user of the crate. Also, it seems like reexporting crates is not as recommeneded as it used to be?

Add `Skip` node variant

Starting with a theoretical example: we have a hex tree with nothing but res15 cells. Visiting them takes 15 pointer dereferences to from their respective res0 root cell. We can change that to a single pointer deref if we adding the concept of "skipping" to nodes.

Improve construction speed

Major goal: it would be awesome it we could both construct a compacted tree and drain it to a vec faster than calling libh3's compact() function. My gut feeling is the bottle neck currently lays non-deterministic alloction of behavior of a hexset. I do have a PR that improves things, but it probably needs some work. See #4

Implement Key/Value iterator

Set/maps should implement .iter[_mut]() which returns an iterator over all cells.

Note to potential implementor: Nodes do not store their keys (cells). It's not necessary, since the structure mimics the semantics of H3. We'll need to reconstruct cell values as part of the tree walk. I suspect this could be a pretty big bottleneck, but it's better than the larger performance hit we'd incur if nodes did store a copy of their cell.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.