Rust 四叉树实现

Question

我正在尝试在 Rust 中实现一个四叉树实现，它以 Array2 作为输入。任何包含所有相同值的节点都应该成为叶子。问题是它只是不断划分并在运行时给出错误，我不知道如何解决它。有任何想法吗？我无法理解为什么它只是继续递归，即使我正在创建空节点，即。没有。

这就是我想到的：

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));
}

Answer 1

该代码会产生越界访问恐慌。我认为您误解了 ndarray 的 slicing 返回的内容。它返回一些行为类似于新数组的东西。如果它的长度为 2，您可以在 0 或 1 处对其进行索引，而不是在原始索引点处。

因此，当您计算子数组的切片索引时，不需要添加当前四叉树位置。您已经有了一个从索引零开始的视图（我认为实际上是一个副本，因为

.to_owned()

）。