Всем привет! В этой статье мы попробуем создать Дерево Квадрантов (Quadtree) с помощью языка программирования Rust!

Сперва узнаем, что это такое?

Дерево квадрантов (также квадродерево, 4-дерево, англ. quadtree) — дерево, в котором у каждого внутреннего узла ровно 4 потомка. Деревья квадрантов часто используются для рекурсивного разбиения двухмерного пространства по 4 квадранта (области). Области представляют собой квадраты, прямоугольники или имеют произвольную форм

- wikipedia

Опеределим архитектуру будущего проекта. Нам понадобится:

• Структура, представляющая собой фигуры (в нашем случае простая безразмерная точка
• Структура, представляющая собой отдельно взятую ноду.
• Структура обертка над нодами, представляющая собой удобное api для работы с нодами

Фигуры

Как уже было сказано, фигуры для нас это простые безразмерные точки в 2d пространстве, имеющие только два параметра: координаты в пространстве x, y: u32 Напишем небольшой код структуры:

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

И небольшую реализацию с конструктором, создающую новые точки по заданным координатам:

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

Ноды

Теперь напишем код стрктуры для ноды, но для начала выясним, что вообщем нам нужно от каждой ноды?

• Иметь высоту и ширину соотвественно: width, height
• Иметь координаты центра ноды x, y
• Иметь счетчик для подсчета объектов внутри ноды count
• Иметь счетчик вместимости capacity, после того как нода будет заполнена, она "поделится"
• Каждая нода должна уметь "делиться", а значит иметь список ссылок на суб-ноды Vec QuadNode
• Иметь список обьекто (точек), которая нода хранит внутри себя Vec Point
• Иметь счетчик, который позволит определить уровень ноды level

При этом мы могли бы не создавать отдельных переменных для центра ноды, а просто делить высоту и ширину каждой ноды или субноды на два. Также, мы могли бы не создавать счетчик вместимости, а оперделить его как константу. Напишем небольшой код структуры:

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

И реализацию, вместе с конструктором, создающим новую ноду:

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

Первой нашей функцией будет функция contain которая будет возвращать true, если нода содержит точку и false если не содержит. Работа функции заключается в нахождении левых нижних координат, правых верхних и сравнения координат точки с ними. Снова небольшой код:

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
}

Второй нашей функцией, будет функция - split. Как только нода будет заполнена, мы разделим ее на четыре субноды, каждая имеет разный центр:

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;
    // child node level
    let lvl = &self.level + 1;

    println!("subdivade node");

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

Следующей функцией будет функция вставки точки внутрь ноды - insert, она будет рекурсивной, если нода содержит субноды, то будем искать субноду содержащую точку и вставлять в нее, а также увеличивать счетчик количества точек внутри ноды. Небольшйо код:

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

Аналогичным образом напишем функцию удаления точки из нодыdelete

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

Закончим работать с нодами, написав две вспомогательные функции. Одну из них вызывает метод delete эта функция удаляет элемент из вектора точек ноды remove, вторая функция 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);
}
}// Закрывающая скобка impl