四叉树是一种空间索引（划分）技术，通过递归地将一整块区域平均划分为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，可见查找效率还是十分高的，数据量只有几千时能十分快地找到邻点。