1
\$\begingroup\$

To teach myself Rust, I implemented a simple Quadtree over 2D points with insert, delete, contain function.

My code does not seems "idiomatic rust code" to me. Also I think it's not so fast.

I'm added 2 tests:

  1. simple test for check code work
  2. test to add 10_000 points to the quadtree

Code:

use std::ops::DerefMut;

#[derive(PartialEq, Copy, Clone)]
pub struct Point {
    x: u32,
    y: u32,
}

impl Point {
    pub fn new(x: u32, y: u32) -> Self {
        Point {
            x,
            y,
        }
    }
}


pub struct QuadNode {
    x: u32,
    y: u32,
    width: u32,
    height: u32,
    count: u8,
    capacity: u8,
    child: Vec<Option<Box<QuadNode>>>,
    elements: Vec<Point>, // Option?
}

impl QuadNode {
    fn new(x: u32, y: u32, width: u32, height: u32, capacity: u8) -> Self {
        QuadNode {
            x,
            y,
            width,
            height,
            count: 0,
            capacity,
            child: Vec::with_capacity(capacity as usize),
            elements: Vec::with_capacity(capacity as usize),
        }
    }

    fn contain(&mut self, p: &Point) -> bool {
        // bottom left
        let botlx = self.x - (self.width / 2);
        let botly = self.y - (self.height / 2);
        //top right
        let toprx = self.x + (self.width / 2);
        let topry = self.y + (self.height / 2);

        p.x > botlx && p.x < toprx && p.y > botly && p.y < topry
    }

    fn split(&mut self) {
        // center
        let x = self.x;
        let y = self.y;
        // child node width && height
        let w = self.width / 2;
        let h = self.height / 2;

        println!("subdivade node");

        self.child.push(Some(Box::new(QuadNode::new(x - w / 2, y + h / 2, w, h, self.capacity))));
        self.child.push(Some(Box::new(QuadNode::new(x + w / 2, y + h / 2, w, h, self.capacity))));
        self.child.push(Some(Box::new(QuadNode::new(x + w / 2, y - h / 2, w, h, self.capacity))));
        self.child.push(Some(Box::new(QuadNode::new(x - w / 2, y - h / 2, w, h, self.capacity))));
    }

    /*
    fn find(&mut self, p: &Point) -> &mut QuadNode { // -> &mut QuadNode?
        match self.child.len() {
            0 => {
                // no child
                if self.contain(p) {
                    return self;
                } else {
                    return None;
                }
            },
            _ => {
                // have child
                let mut flag: bool = false;

                for child in self.child.iter().filter_map(Option::as_ref) {

                }
            }
        }
    }
    */

    fn insert(&mut self, p: Point) {
        match self.child.len() {
            0 => {
                if self.contain(&p) {
                    // no child
                    if self.count >= self.capacity {
                        // need to split
                        self.split();
                        self.insert(p);
                    } else {
                        // just push
                        println!("insert new element");
                        self.count += 1;
                        self.elements.push(p);

                    }
                }
            }
            _ => {
                // have child
                for child in self.child.iter_mut().filter_map(Option::as_mut).map(Box::deref_mut) {
                    child.insert(p);
                }
            }
        }
    }

    fn delete(&mut self, p: Point) {
        match self.child.len() {
            0 => {
                if self.contain(&p) {
                    self.remove(&p);
                    self.count -= 1;
                }
            }
            _ => {
                let mut flag: bool = false;
                for child in self.child.iter_mut().filter_map(Option::as_mut).map(Box::deref_mut) {
                    flag = child.contain(&p);
                }
                if flag {
                    // parent node count -1
                    self.count -= 1;

                    for child in self.child.iter_mut().filter_map(Option::as_mut).map(Box::deref_mut) {
                        child.delete(p);
                    }

                    // need to un_split?
                    if self.count < self.capacity {
                        self.clear();
                    }
                }
            }
        }
    }

    fn clear(&mut self) {

        // add child's elements to parent node
        for child in self.child.iter_mut().filter_map(Option::as_mut).map(Box::deref_mut) {
            self.elements.extend(child.elements.iter().cloned()); // append?
        }

        // clear child node
        self.child.clear();
    }

    fn remove(&mut self, p: &Point) {
        // magic remove
        let pos = self.elements.iter().position(|x| *x == *p).unwrap();
        self.elements.remove(pos);
    }
}

fn main() {}

pub struct QuadTree {
    root: Option<Box<QuadNode>>,
}

impl QuadTree {
    pub fn new() -> Self {
        QuadTree {
            root: None,
        }
    }

    pub fn insert(&mut self, p: Point) {
        match self.root {
            Some(ref mut root) => {
                root.insert(p);
            }
            None => {
                self.root = Some(Box::new(QuadNode::new(100_000 / 2, 100_000 / 2, 100_000, 100_000, 10)));
            }
        }
    }

    pub fn init(&mut self) {
        match self.root {
            None => {
                self.root = Some(Box::new(QuadNode::new(100_000 / 2, 100_000 / 2, 100_000, 100_000, 10)));
                println!("create new node");
            }
            _ => {
                return;
            }
        }
    }

    pub fn delete(&mut self, p: Point) {
        match self.root {
            Some(ref mut root) => {
                root.delete(p);
            }
            _ => {
                return;
            }
        }
    }

    pub fn contain(&mut self, p: &Point) -> bool {
        match self.root {
            Some(ref mut root) => {
                if root.contain(p) {
                    return true;
                } else {
                    return false;
                }
            },
            _ => {
                return false;
            }
        }
    }
}

Simple test:

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn simple_insert_five_points() {
        let mut qtree = QuadTree::new();
        qtree.init();
        let p1 = Point::new(10, 10);
        let p2 = Point::new(30, 30);
        let p3 = Point::new(40, 40);
        let p4 = Point::new(190, 190);
        let p5 = Point::new(170, 170);
        qtree.insert(p1);
        qtree.insert(p2);
        qtree.insert(p3);
        qtree.insert(p4);
        qtree.insert(p5);
    }

    // soo sloooow
    #[test]
    fn add_ten_thousend_point() {
        let mut qtree = QuadTree::new();
        qtree.init();

        for i in 1..10000 {
            qtree.insert(Point { x: i, y: i });
        }
    }
}

Edit: I wrote it to use this in my game, so an example of use is something like this (in pseudocode):

fn game_loop () {
   input_player();
    render();
    for node.contain(player) { // no idea how to write this
        player.update();
        //collision detected here
    }

}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.