乐趣区

关于c++:C实现四叉树

jiezi

四叉树是一种空间索引（划分）技术，通过递归地将一整块区域平均划分为 4 个子区域，每个区域托管肯定数量的二维点，于是任意一个二维点都能够依据它的坐标疾速找到所述的子区域，失去它的邻点。

具体介绍略过，只有会实现二叉树的二分查找，就不难领会四叉树划分的思维。因为查找邻点的速度十分快，所以罕用于游戏中的碰撞检测，GIS 的地理位置索引等。

上面是我实现的一种传统四叉树。

节点定义：

#include <vector>
#include <cstdlib>
#include <ctime>
#include <iostream>

// 二维数据点定义
typedef struct Point_2D {
    int x;
    int y;
}Point;

// 节点定义
typedef struct Quad_Tree_Node {
    Point start_xy;               // 左上角起始点
    int width;                    // 宽度
    int height;                   // 高度
    int capacity;                 // 节点容量
    bool is_leaf;                 // 叶节点标记
    std::vector<Point> points;    // 存储的二维点
    Quad_Tree_Node* lu_child;     // 子节点，左上
    Quad_Tree_Node* ru_child;     // 子节点，右上
    Quad_Tree_Node* lb_child;     // 子节点，左下
    Quad_Tree_Node* rb_child;     // 子节点，右下
    int depth;                    // 以后节点深度
}Quad_Node;

二维数据点构造只有横纵坐标，也能够携带别的信息。四叉树节点中须要保留所属子区域的信息，我应用左上角起始点 + 宽度 + 高度来定义一块区域。设置了节点容量来限度一块区域能保留的数据量，如果超过容量，节点就要持续决裂。

创立节点办法：

Quad_Node* Quad_Tree::create_node_(const Point& start, const int& w, const int& h) {
    Quad_Node* new_node = new Quad_Node;
    new_node->start_xy = start;
    new_node->width = w;
    new_node->height = h;
    new_node->capacity = _set_capacity;
    new_node->is_leaf = true;
    new_node->lu_child = nullptr;
    new_node->lb_child = nullptr;
    new_node->ru_child = nullptr;
    new_node->rb_child = nullptr;
    return new_node;
}

创立节点办法须要左上起始点、宽度和高度三个入口参数。

决裂节点办法：

int Quad_Tree::split_node_(Quad_Node* node) {
    node->is_leaf = false;

    int sub_w = node->width / 2;
    int sub_h = node->height / 2;

    // 确定每个子节点的起始地位
    Point lu_start = node->start_xy;
    Point lb_start;
    lb_start.x = node->start_xy.x;
    lb_start.y = node->start_xy.y + sub_h;
    Point ru_start;
    ru_start.x = node->start_xy.x + sub_w;
    ru_start.y = node->start_xy.y;
    Point rb_start;
    rb_start.x = node->start_xy.x + sub_w;
    rb_start.y = node->start_xy.y + sub_h;

    // 创立子节点
    node->lu_child = create_node_(lu_start, sub_w, sub_h);
    node->lb_child = create_node_(lb_start, sub_w, sub_h);
    node->ru_child = create_node_(ru_start, sub_w, sub_h);
    node->rb_child = create_node_(rb_start, sub_w, sub_h);

    // 将以后节点保留的数据点插入到下一层
    for (int i = 0, count = node->points.size(); i < count; ++i) {insert_node_(node, node->points[i]);
    }
    node->points.clear();

    return 0;
}

决裂节点留神须要把以后节点保留的所有数据点插入到下一层，即从新划分到子节点的区域中。因而，不难看出只有叶节点上会保留数据点。

插入节点办法：

int Quad_Tree::insert_node_(Quad_Node* node, const Point& point)
{if (node->is_leaf) {    // 数据点都插入到叶节点
        int count = node->points.size();
        if (count + 1 > node->capacity) {    // 超过容量就要决裂节点，再插入
            split_node_(node);
            insert_node_(node, point);
        }
        else {node->points.push_back(point);    // 没超过就失常插入
        }

        return 0;
    }

    // 以后节点不是叶节点，找到它所属的子区域
    Region in_region = find_region(node, point);

    if (in_region == Region::LEFT_UP) {insert_node_(node->lu_child, point);    // 插入到左上子节点
    }
    else if (in_region == Region::LEFT_BOTTOM) {insert_node_(node->lb_child, point);    // 插入到左下子节点
    }
    else if (in_region == Region::RIGHT_UP) {insert_node_(node->ru_child, point);    // 插入到右上子节点
    }
    else if (in_region == Region::RIGHT_BOTTOM) {insert_node_(node->rb_child, point);    // 插入到右下子节点
    }
    else {return -1;    // 不属于任何子区域}

    return 0;
}

插入节点时判断以后节点是不是叶节点，不是叶节点的话须要找到确定所属子区域，插入到对应的子节点中。确定子区域的过程我独自实现为一个函数：

Region Quad_Tree::find_region(Quad_Node* node, const Point& point)
{
    Region found = Region::OUT_OF_RANGE;
    int x = point.x;
    int y = point.y;
    int sub_w = node->width / 2;
    int sub_h = node->height / 2;
    if (x > node->start_xy.x && x < node->start_xy.x + sub_w) {if (y > node->start_xy.y && y < node->start_xy.y + sub_h) {found = Region::LEFT_UP;}
        else if (y > node->start_xy.y + sub_h && y < node->start_xy.y + node->height) {found = Region::LEFT_BOTTOM;}
        else {}}
    else if (x > node->start_xy.x + sub_w && x < node->start_xy.x + node->width) {if (y > node->start_xy.y && y < node->start_xy.y + sub_h) {found = Region::RIGHT_UP;}
        else if (y > node->start_xy.y + sub_h && y < node->start_xy.y + node->height) {found = Region::RIGHT_BOTTOM;}
        else {}}
    else {found = Region::OUT_OF_RANGE;}

    return found;
}

依据下面的实现，我对正好位于边界线的数据点是没有解决的。能够把它们保留到父节点上。

区域的定义用了枚举类：

enum class Region {
    LEFT_UP = 0,
    LEFT_BOTTOM,
    RIGHT_UP,
    RIGHT_BOTTOM,
    OUT_OF_RANGE
};

实现一个遍历删除办法：

void Quad_Tree::traverse(Quad_Node* node) {if (node->is_leaf) {
        // 拜访操作
        node->points.clear();
        delete node;
        return;
    }

    traverse(node->lu_child);
    traverse(node->lb_child);
    traverse(node->ru_child);
    traverse(node->rb_child);

    node->points.clear();
    delete node;
}

// 遍历输入
void Quad_Tree::show() {traverse(root_);
}

决裂到指定深度的办法：

int max_depth = 8;

void Quad_Tree::init_split()
{split_to_depth(root_, 0);
}

int Quad_Tree::split_to_depth(Quad_Node* node, const int& depth)
{if (depth == max_depth) {
        node->is_leaf = true;
        return 1;
    }
    else {
        node->is_leaf = false;
        node->depth = depth;
        int sub_w = node->width / 2;
        int sub_h = node->height / 2;

        Point lu_start = node->start_xy;
        Point lb_start;
        lb_start.x = node->start_xy.x;
        lb_start.y = node->start_xy.y + sub_h;
        Point ru_start;
        ru_start.x = node->start_xy.x + sub_w;
        ru_start.y = node->start_xy.y;
        Point rb_start;
        rb_start.x = node->start_xy.x + sub_w;
        rb_start.y = node->start_xy.y + sub_h;

        node->lu_child = create_node_(lu_start, sub_w, sub_h);
        node->lb_child = create_node_(lb_start, sub_w, sub_h);
        node->ru_child = create_node_(ru_start, sub_w, sub_h);
        node->rb_child = create_node_(rb_start, sub_w, sub_h);
    }

    split_to_depth(node->lu_child, depth + 1);
    split_to_depth(node->lb_child, depth + 1);
    split_to_depth(node->ru_child, depth + 1);
    split_to_depth(node->rb_child, depth + 1);
}

Quad_Tree 类定义：

class Quad_Tree {
private:
    Quad_Node* root_;    // 根节点

    Quad_Node* create_node_(const Point& start, const int& w, const int& h);    
    int split_node_(Quad_Node* node);
    int insert_node_(Quad_Node* node, const Point& point);
    Region find_region(Quad_Node* node, const Point& point);
    void traverse(Quad_Node* node);
    int split_to_depth(Quad_Node* node, const int& depth);
    
public:
    Quad_Tree(const int& start_x, const int& start_y, const int& witdh, const int& height);
    ~Quad_Tree();
    void insert_point_(const Point& point);
    void show();
    void init_split();};

main 函数，测试一下划分 10000 个数据点的工夫。

#include "quadTree.h"

void test_time() {

    // 设置工夫种子
    srand(time(0));
    clock_t startTime, endTime;
    double in_sec = 0, tra_sec = 0;

    Quad_Tree quad_tree(0, 0, 1920, 1536);    // 左上起始地位（0,0），宽 1920，高 1536

    const int rand_size = 10000;
    Point* rand_points = new Point[rand_size];

    // 数据点插入
    startTime = clock();
    for (int i = 0; i < rand_size; ++i) {    // 划分随机数据点
        rand_points[i].x = rand() % 1920;
        rand_points[i].y = rand() % 1536;
        quad_tree.insert_point_(rand_points[i]);
    }
    endTime = clock();
    in_sec = (double)(endTime - startTime);

    // 数据点遍历
    startTime = clock();
    quad_tree.show();
    endTime = clock();
    tra_sec = (double)(endTime - startTime);

    std::cout << "\n";
    std::cout << "insert" << rand_size << "points takes" << in_sec << "ms.\n";
    std::cout << "traverse" << rand_size << "points takes" << tra_sec << "ms.\n";
}

int main() {//Quad_Tree quad_tree(0, 0, 1920, 1536);
    //quad_tree.init_split();

    test_time();}

最初失去 1 万个数据点建树约 9~12ms，遍历约 2~3ms。5000 个数据点建树约 5~6ms，遍历 1~2ms，可见查找效率还是十分高的，数据量只有几千时能十分快地找到邻点。

退出移动版