Struct spaceindex::rtree::RTree

pub struct RTree<ND> { /* fields omitted */ }

Methods

impl<ND> RTree<ND>

pub fn new(dimension: usize) -> Self

Creates a new RTree with the given number of dimensions.

Example

use spaceindex::rtree::RTree;

let mut tree = RTree::new(2);
tree.insert(((0.0, 0.0), (2.0, 4.0)), 1);

pub fn insert<'a, IR: IntoRegion<'a>>(
    &mut self,
    region: IR,
    data: ND
) -> Result<(), ShapelikeError>

Attempts to insert a given object into the tree.

Errors

This function will return an error if region does not have the same dimension as this tree.

Example

use spaceindex::rtree::RTree;

let mut tree = RTree::new(2);
tree.insert(((-1.0, 0.0), (3.0, 3.0)), 0);

pub fn validate_consistency(&self)

Validates the consistency of the tree. In particular, this function checks that:

• Every child is contained in the minimum bounding region of its parent, and
• The total number of descendants of the root node is equal to the number of nodes in the tree minus one.

pub fn get_node(&self, index: Index) -> &Node<ND>

Returns a reference to the Node with index index.

Panics

This function will panic if index does not refer to a node in this tree.

pub fn get_node_mut(&mut self, index: Index) -> &mut Node<ND>

Returns a mutable reference to the Node with index `index.

Panics

This function will panic if index does not refer to a node in this tree.

pub fn root_node(&self) -> &Node<ND>

Returns a reference to the root Node in this tree.

pub fn root_index(&self) -> Index

Returns the index of the root node in this tree.

pub fn shape_lookup(&self, shape: &Shape) -> Vec<Index>

Returns a Vec<Index> of those elements in the tree whose bounding box contains the minimum bounding box of the input shape.

pub fn point_lookup<IP: IntoPoint>(&self, point: IP) -> Vec<Index>

Returns a Vec<Index> of those regions in the tree containing the given point point.

Example

use spaceindex::rtree::RTree;

let mut tree = RTree::new(2);

// insert a couple of regions
tree.insert(((0.0, 0.0), (2.0, 2.0)), ());
tree.insert(((1.0, 0.0), (3.0, 3.0)), ());

// Both rectangles contain the point (1.0, 1.0)
assert_eq!(tree.point_lookup((1.0, 1.0)).len(), 2);

// No rectangle should contain the point (-1.0, 0.0)
assert!(tree.point_lookup((-1.0, 0.0)).is_empty());

// Only one hit for (0.5, 0.5)
assert_eq!(tree.point_lookup((0.5, 0.5)).len(), 1);

// Two hits at (2.0, 2.0)
assert_eq!(tree.point_lookup((2.0, 2.0)).len(), 2);

// Only one hit at (2.5, 2.5)
assert_eq!(tree.point_lookup((2.5, 2.5)).len(), 1);

pub fn region_intersection_lookup<'a, IC: IntoRegion<'a>>(
    &self,
    region: IC
) -> Vec<Index>

Returns a Vec<Index> of those elements in the tree whose minimum bounding box intersects the given region.

Example

use spaceindex::rtree::RTree;

let mut tree = RTree::new(2);

// insert a couple of regions
tree.insert(((0.0, 0.0), (5.0, 5.0)), ());
tree.insert(((-1.0, 1.0), (1.0, 3.0)), ());

// Nothing should intersect with the box ((-3.0, 0.0), (-2.0, 2.0))
assert!(tree.region_intersection_lookup(((-3.0, 0.0), (-2.0, 2.0))).is_empty());

// The region ((-3.0, 0.0), (-0.5, 4.0)) should intersect the second region.
assert_eq!(tree.region_intersection_lookup(((-3.0, 0.0), (-0.5, 4.0))).len(), 1);

// The skinny box ((-2.0, 1.5), (8.0, 1.5)) should intersect both regions.
assert_eq!(tree.region_intersection_lookup(((-2.0, 1.5), (8.0, 1.5))).len(), 2);

// The region ((3.0, 2.0), (4.0, 4.0)) should only intersect the first region.
assert_eq!(tree.region_intersection_lookup(((3.0, 2.0), (4.0, 4.0))).len(), 1);

pub fn region_lookup<'a, IC: IntoRegion<'a>>(&self, region: IC) -> Vec<Index>

Returns a Vec<Index> of those elements in the tree whose minimum bounding box contains the given region.

Example

use spaceindex::rtree::RTree;

let mut tree = RTree::new(2);

// insert a couple of regions
tree.insert(((0.0, 0.0), (2.0, 2.0)), ());
tree.insert(((1.0, 0.0), (3.0, 3.0)), ());

// Both regions contain the box ((1.25, 1.0), (1.75, 1.75))
assert_eq!(tree.region_lookup(((1.25, 1.0), (1.75, 1.75))).len(), 2);

// While the box ((-0.5, -0.5), (0.5, 0.5)) does intersect our first region,
// it is not contained in any region, so we should get no results.
assert!(tree.region_lookup(((-0.5, -0.5), (0.5, 0.5))).is_empty());

/// The box ((0.0, 0.5), (0.75, 1.99)) is only contained in the first region.
assert_eq!(tree.region_lookup(((0.0, 0.5), (0.75, 1.99))).len(), 1);

pub fn line_lookup(&self, line: &LineSegment) -> Vec<Index>

Returns a Vec<Index> of those elements in the tree whose minimum bounding box contains the given line.

Trait Implementations

impl<ND: Debug> Debug for RTree<ND>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<'a, ND> GraphWalk<'a> for RTree<ND>

type Node = Index

type Edge = (Index, Index)

fn nodes(&'a self) -> Cow<'a, [Self::Node]>

Returns all the nodes in this graph.

fn edges(&'a self) -> Cow<'a, [Self::Edge]>

Returns all of the edges in this graph.

fn source(&'a self, edge: &Self::Edge) -> Self::Node

The source node for edge.

fn target(&'a self, edge: &Self::Edge) -> Self::Node

The target node for edge.

impl<'a, ND> Labeller<'a> for RTree<ND>

type Node = Index

type Edge = (Index, Index)

fn graph_id(&'a self) -> Id<'a>

Must return a DOT compatible identifier naming the graph.

fn node_id(&'a self, n: &Self::Node) -> Id<'a>

Maps n to a unique identifier with respect to self. The implementor is responsible for ensuring that the returned name is a valid DOT identifier.

fn node_shape(&'a self, _node: &Self::Node) -> Option<LabelText<'a>>

Maps n to one of the [graphviz shape names][1]. If None is returned, no shape attribute is specified.

fn node_label(&'a self, n: &Self::Node) -> LabelText<'a>

Maps n to a label that will be used in the rendered output. The label need not be unique, and may be the empty string; the default is just the output from node_id.

fn edge_label(&'a self, _e: &Self::Edge) -> LabelText<'a>

Maps e to a label that will be used in the rendered output. The label need not be unique, and may be the empty string; the default is in fact the empty string.

fn node_style(&'a self, _n: &Self::Node) -> Style

Maps n to a style that will be used in the rendered output.

fn edge_style(&'a self, _e: &Self::Edge) -> Style

Maps e to a style that will be used in the rendered output.