共计 6009 个字符,预计需要花费 16 分钟才能阅读完成。
四叉树是一种空间索引(划分)技术,通过递归地将一整块区域平均划分为 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,可见查找效率还是十分高的,数据量只有几千时能十分快地找到邻点。
正文完