recursionrustquadtree

Rust quadtree implementation


Im trying to make a quadtree implementation in rust that takes as input an Array2<u8>. Any node that contains all the same values should become a leaf. Problem is it just keeps dividing anyway and gives an error at runtime and im at a loss how to resolve it. Any ideas? Im cannot understand why it just keeps on recursing even though I am making nodes that are empty ie. None.

This is what i came up with:

use noise::{Perlin, NoiseFn};
use ndarray::prelude::*;
use cgmath::{vec2, Vector2};

struct Node {
    grid: ndarray::Array2<u8>,
    nodes: [Option<Box<Node>>; 4],
    pos: Vector2<u8>,
}

impl Node {
    pub fn new(grid: ndarray::Array2<u8>, pos: Vector2<u8>) -> Self {
        // println!("{}", grid.dim().0);

        if grid.dim().0 > 1 {
            let half_size = (grid.dim().0 / 2) as u8;

            let bl: Node = Node::new(
                grid.slice(s![
                    pos.x as usize..(pos.x + half_size) as usize,
                    pos.y as usize..(pos.y + half_size) as usize
                ])
                .to_owned(),
                vec2(pos.x, pos.y),
            );
            let tl: Node = Node::new(
                grid.slice(s![
                    pos.x as usize..(pos.x + half_size) as usize,
                    (pos.y + half_size) as usize..(pos.y + half_size * 2) as usize
                ])
                .to_owned(),
                vec2(pos.x, pos.y + half_size),
            );
            let tr: Node = Node::new(
                grid.slice(s![
                    (pos.x + half_size) as usize..(pos.x + half_size * 2) as usize,
                    (pos.y + half_size) as usize..(pos.y + half_size * 2) as usize
                ])
                .to_owned(),
                vec2(pos.x + half_size, pos.y + half_size),
            );
            let br: Node = Node::new(
                grid.slice(s![
                    (pos.x + half_size) as usize..(pos.x + half_size * 2) as usize,
                    pos.y as usize..(pos.y + half_size) as usize
                ])
                .to_owned(),
                vec2(pos.x + half_size, pos.y),
            );
            let nodes = [Some(Box::new(bl)), Some(Box::new(tl)), Some(Box::new(tr)), Some(Box::new(br))];

            Self {
                grid: grid,
                nodes: nodes,
                pos: pos,
            }
        } else {
            print!("unsplitable ");
            Self {
                grid: Array::from_elem((1, 1), grid[[0, 0]]),
                nodes: [None, None, None, None],
                pos: pos,
            }
        }
    }
}

fn main() {
    let perlin = Perlin::new(1);
    let mut grid: Array2<u8> = Array::zeros((8, 8));

    for x in 0..8 {
        for y in 0..8 {
            grid[[x, y]] = ((perlin.get([x as f64 / 12.0, y as f64 / 12.0]) + 1.0) * 1.5) as u8;
        }
    }

    let quadtree: Node = Node::new(grid, vec2(0, 0));
}

Solution

  • The code generates an out-of-bounds access panic. I think you are misunderstanding what slicing of an ndarray returns. It returns something that behaves like a new array. If it has length 2, you can index it at 0 or at 1, not at the original index points. This is consistent with how slicing works in Rust in general.

    So when you are calculating the slice indices for the sub-arrays, you don't need to add the current quadtree position. You already have a view (a copy actually, I think, because of .to_owned()) that starts at index zero.