Struct octree::Octree

source ·

pub struct Octree<'point, L> { /* private fields */ }

Expand description

The Octree data structure.

Implementations§

source §

impl<'point, L> Octree<'point, L>where L: Locatable + Eq + Hash,

source

pub fn new(points: Vec<&'point L>) -> Self

Construct an Octree that covers all given points.

Example

use octree::point::Point3D;
use octree::Octree;

let point1 = Point3D::new(0.0, 0.0, 0.0);
let point2 = Point3D::new(10.0, 10.0, 10.0);

// Note points takes ownership of the above two points.
let points = vec![point1, point2];

let octree = Octree::new(points.iter().collect());

source

pub fn insert(&mut self, point: &'point L) -> bool

Insert a new point. If Octree does not cover the new point then nothing will change.

Example

use octree::point::Point3D;
use octree::Octree;

let point1 = Point3D::new(0.0, 0.0, 0.0);
let point2 = Point3D::new(10.0, 10.0, 10.0);
let point3 = Point3D::new(5.0, 5.0, 5.0);
let point4 = Point3D::new(20.0, 20.0, 20.0);

// Note points takes ownership of the above two points.
let points = vec![point1, point2];
let mut octree = Octree::new(points.iter().collect());

assert!(octree.insert(&point3));
assert!(!octree.insert(&point4));

source

pub fn delete(&mut self, point: &'point L) -> bool

Delete a point from current Octree, if the point is not in the tree, then nothing will change.

Example

use octree::point::Point3D;
use octree::Octree;

let point1 = Point3D::new(0.0, 0.0, 0.0);
let point2 = Point3D::new(10.0, 10.0, 10.0);
let point3 = Point3D::new(20.0, 20.0, 20.0);

let points = vec![point1.clone(), point2];
let mut octree = Octree::new(points.iter().collect());

assert!(octree.delete(&point1));
assert!(!octree.delete(&point3));

source

pub fn query(&self, bounding_box: &BoundingBox) -> HashSet<&L>

Find all points covered by a specified BoundingBox.

Example

use std::collections::HashSet;

use octree::point::Point3D;
use octree::{BoundingBox, Octree};

// Build an example octree.
let point1 = Point3D::new(0.0, 0.0, 0.0);
let point2 = Point3D::new(10.0, 10.0, 10.0);
let point3 = Point3D::new(4.0, 4.0, 4.0);
let points = vec![point1.clone(), point2];
let mut octree = Octree::new(points.iter().collect());
let point4 = Point3D::new(5.0, 10.0, 5.0);
octree.insert(&point3);
octree.insert(&point4);

let points_for_query = vec![point1.clone(), point4.clone()];
let bounding_box = BoundingBox::new(points_for_query.iter().collect());

assert_eq!(
    // The actual query.
    octree.query(&bounding_box),
    HashSet::from([&point1, &point3])
);

source

pub fn contains(&self, point: &L) -> bool

Check if a point is already recorded.

Example

use octree::point::Point3D;
use octree::Octree;

let point1 = Point3D::new(0.0, 0.0, 0.0);
let point2 = Point3D::new(10.0, 10.0, 10.0);
let point3 = Point3D::new(20.0, 20.0, 20.0);

let points = vec![point1.clone(), point2];

let octree = Octree::new(points.iter().collect());

assert!(octree.contains(&point1));
assert!(!octree.contains(&point3));

source

pub fn covers(&self, point: &L) -> bool

Check if a point can be covered by the current Octree.

Example

use octree::point::Point3D;
use octree::Octree;

let point1 = Point3D::new(0.0, 0.0, 0.0);
let point2 = Point3D::new(10.0, 10.0, 10.0);
let point3 = Point3D::new(5.0, 5.0, 5.0);
let point4 = Point3D::new(20.0, 20.0, 20.0);

// Note points takes ownership of the above two points.
let points = vec![point1, point2];

let octree = Octree::new(points.iter().collect());

assert!(octree.covers(&point3));
assert!(!octree.covers(&point4));

source

pub fn overlaps(&self, bounding_box: &BoundingBox) -> bool

Check if the space occupied by current Octree overlap with a given BoundingBox.

Example

use octree::point::Point3D;
use octree::{BoundingBox, Octree};

let point1 = Point3D::new(0.0, 0.0, 0.0);
let point2 = Point3D::new(10.0, 10.0, 10.0);
let points = vec![point1, point2];
let octree = Octree::new(points.iter().collect());

let point3 = Point3D::new(1.0, 1.0, 1.0);
let point4 = Point3D::new(11.0, 11.0, 11.0);
let bounding_box1 = BoundingBox::new(vec![point3, point4].iter().collect());

let point5 = Point3D::new(1.0, 1.0, 1.0);
let point6 = Point3D::new(9.0, 9.0, 9.0);
let bounding_box2 = BoundingBox::new(vec![point5, point6].iter().collect());

let point7 = Point3D::new(11.0, 0.0, 0.0);
let point8 = Point3D::new(20.0, 20.0, 20.0);
let bounding_box3 = BoundingBox::new(vec![point7, point8].iter().collect());

assert!(octree.overlaps(&bounding_box1));
assert!(octree.overlaps(&bounding_box2));
assert!(!octree.overlaps(&bounding_box3));