# [quadtree_rs](https://crates.io/crates/quadtree_rs)

[![crates.io
badge](https://img.shields.io/crates/v/quadtree_rs.svg)](https://crates.io/crates/quadtree_rs)
[![docs.rs
badge](https://docs.rs/quadtree_rs/badge.svg)](https://docs.rs/quadtree_rs)
[![license](https://img.shields.io/crates/l/quadtree_rs.svg)](https://github.com/ambuc/quadtree/blob/master/LICENSE)

[Point/region Quadtree](https://en.wikipedia.org/wiki/Quadtree) with support for 
overlapping regions.

For documentation, see [docs.rs/quadtree_rs](https://docs.rs/quadtree_rs/).

# Quick Start

```rust
use quadtree_rs::{area::AreaBuilder, point::Point, Quadtree};

// Instantiate a new quadtree which associates String values with u64 
// coordinates.
let mut qt = Quadtree::<u64, String>::new(/*depth=*/4);

// A depth of four means a square with width (and height) 2^4.
assert_eq!(qt.width(), 16);

// Associate the value "foo" with a rectangle of size 2x1, anchored at (0, 0).
let region_a = AreaBuilder::default()
    .anchor(Point {x: 0, y: 0})
    .dimensions((2, 1))
    .build().unwrap();
qt.insert(region_a, "foo".to_string());

// Query over a region of size 2x2, anchored at (1, 0).
let region_b = AreaBuilder::default()
    .anchor(Point {x: 1, y: 0})
    .dimensions((2, 2))
    .build().unwrap();
let mut query = qt.query(region_b);

// The query region (region_b) intersects the region "foo" is associated with 
// (region_a), so the query iterator returns "foo" by reference.
assert_eq!(query.next().unwrap().value_ref(), "foo");
```

# Questions?

Please file an issue on GitHub.

# Authors

See [`Cargo.toml`](Cargo.toml).

# Contributing

See [`CONTRIBUTING.md`](CONTRIBUTING.md) and [`NOTES.md`](NOTES.md)

# License

This project is licensed under the Apache 2.0 license.

# Disclaimer

This is not an official Google product. 

# TODO
 - [ ] Pretty-print quadtree function which plots a density map
 - [ ] Benchmark tests