// 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()
}
}
```
// 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()
}
}
```
// 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()
}
}
Idiomatic quadtree implementation in Rust
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()
}
}
```
lang-rust