Idiomatic quadtree implementation in Rust

Question

I am learning Rust, coming from a Java background, and I was hoping to get some critique on my simple QuadTree implementation in Rust. This is as a learning exercise for me.

Are there tips on how to make it more idiomatic? Are there features of Rust I am overlooking?

// common.rs
#[derive(Copy, Clone, Debug)]
pub struct Point2D {
 pub x: f32,
 pub y: f32
}
impl Point2D {
 #[wasm_bindgen(constructor)]
 pub fn new(x: f32, y: f32) -> Self {
 Point2D { x, y }
 }
 pub fn zero() -> Self {
 Point2D::new(0.0, 0.0 )
 }
 pub fn offset(&self, dx: f32, dy: f32) -> Self {
 Point2D::new(self.x + dx, self.y + dy)
 }
}
#[derive(Debug)]
pub struct Rectangle {
 pub p0: Point2D,
 pub width: f32,
 pub height: f32
}
impl Rectangle {
 #[wasm_bindgen(constructor)]
 pub fn new(x: f32, y: f32, width: f32, height: f32) -> Self {
 Rectangle {
 p0: Point2D::new(x, y),
 width,
 height
 }
 }
 pub fn contains(&self, point: &Point2D) -> bool {
 if point.x < self.p0.x || point.x > self.p0.x + self.width {
 return false
 }
 if point.y < self.p0.y || point.y > self.p0.y + self.height {
 return false
 }
 true
 }
 pub fn intersects(&self, other: &Rectangle) -> bool {
 let l1 = self.p0;
 let r1 = self.p0.offset(self.width, self.height);
 let l2 = other.p0;
 let r2 = other.p0.offset(other.width, other.height);
 if l1.x > r2.x || l2.x > r1.x {
 return false
 }
 if l1.y > r2.y || l2.y > r1.y {
 return false
 }
 return true
 }
}

// quad_tree.rs
use std::mem;
use crate::common::*;
#[derive(Debug, Eq, PartialEq)]
pub enum QuadTreeResult {
 Ok,
 Err
}
pub struct QuadTree {
 boundary: Rectangle,
 points: Vec<Point2D>,
 north_east: Option<Box<QuadTree>>,
 south_east: Option<Box<QuadTree>>,
 south_west: Option<Box<QuadTree>>,
 north_west: Option<Box<QuadTree>>
}
impl QuadTree {
 const MAX_CAPACITY: usize = 4;
 pub fn new(p0: Point2D, width: f32, height: f32) -> Self {
 QuadTree {
 boundary: Rectangle {
 p0,
 width,
 height
 },
 points: Vec::new(),
 north_east: None,
 south_east: None,
 south_west: None,
 north_west: None
 }
 }
 pub fn insert(&mut self, point: Point2D) -> QuadTreeResult {
 if !self.boundary.contains(&point) {
 return QuadTreeResult::Err
 }
 if self.points.len() < QuadTree::MAX_CAPACITY && self.is_leaf() {
 self.points.push(point);
 return QuadTreeResult::Ok
 }
 if self.points.len() >= QuadTree::MAX_CAPACITY || !self.is_leaf() {
 self.subdivide();
 if self.north_east.as_mut().unwrap().boundary.contains(&point) {
 return self.north_east.as_mut().unwrap().insert(point)
 } else if self.south_east.as_mut().unwrap().boundary.contains(&point) {
 return self.south_east.as_mut().unwrap().insert(point)
 } else if self.south_west.as_mut().unwrap().boundary.contains(&point) {
 return self.south_west.as_mut().unwrap().insert(point)
 } else {
 return self.north_west.as_mut().unwrap().insert(point)
 }
 }
 QuadTreeResult::Err
 }
 fn subdivide(&mut self) -> QuadTreeResult {
 if self.is_leaf() {
 let p0 = &self.boundary.p0;
 let new_width = self.boundary.width / 2.0;
 let new_height = self.boundary.height / 2.0;
 self.north_east = Some(Box::new(QuadTree::new(p0.offset(new_width, 0.0), new_width, new_height)));
 self.south_east = Some(Box::new(QuadTree::new(p0.offset(new_width, new_height), new_width, new_height)));
 self.south_west = Some(Box::new(QuadTree::new(p0.offset(0.0, new_height), new_width, new_height)));
 self.north_west = Some(Box::new(QuadTree::new(p0.offset(0.0, 0.0), new_width, new_height)));
 let old_points = mem::replace(&mut self.points, Vec::new());
 for p in old_points {
 if let QuadTreeResult::Err = self.insert(p) {
 return QuadTreeResult::Err
 }
 }
 }
 QuadTreeResult::Ok
 }
 pub fn query(&self, range: &Rectangle) -> Vec<Point2D> {
 let mut result = Vec::new();
 if !self.boundary.intersects(range) {
 return result;
 }
 if self.is_leaf() {
 for p in &self.points {
 if range.contains(p) {
 result.push(*p)
 }
 }
 } else {
 result.extend(self.north_east.as_ref().unwrap().query(range));
 result.extend(self.south_east.as_ref().unwrap().query(range));
 result.extend(self.south_west.as_ref().unwrap().query(range));
 result.extend(self.north_west.as_ref().unwrap().query(range));
 }
 return result
 }
 fn is_leaf(&self) -> bool {
 return self.north_east.is_none() && self.south_east.is_none() && self.south_west.is_none() && self.north_west.is_none()
 }
}

Answer 1

Just a very general observation: the position of a rectangle is not fundamental to the rectangle itself, but rather a to the instantiation of a rectangle in a scene. In your implementation making it a property of Rectangle might make sense, but pulling it out makes the implementation more flexible and I suspect might make it easier to read when it grows. For one thing, a rectangle might be placed in a 3D scene, a non-Euclidean space, or might be used without reference to any particular reference frame (such as when comparing the area of two rectangles). Pulling out the position also makes it possible to reuse an instance in a bunch of places. In the following image, for example, all the equally sized squares could refer to the same struct, saving memory in case of large trees.

quadtree example

Also, I don't think QuadTreeResult is helpful - it doesn't add anything to Result, and I don't think being able to distinguish them in your code is useful. It's a bit like trivially subclassing java.lang.Boolean (as opposed to trivially subclassing java.lang.RuntimeException, which is idiomatic).

• avanwieringen: Thanks! Nice observations and they make a lot of sense. I will change my implementation.
• exocortex: I am also learning Rust and was wondering about quadtrees. I don't completely understand what you mean with "pulling it out" i.e. the position of a rectangle of its implementation. Do you mean that each quadtree also saves the positions of each child-rectangle, but not the child-rectangle itself? But then the rectangles would still have to save their sizes, right?