四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间划分为四个相等的子空间，如此递归下去，直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单，并且当空间数据分布比较均匀时，具有比较高的空间数据插入和查询效率。这里介绍的四叉树结构中，所有的点位置信息都存储在叶子节点上，中间节点以及根结点不存储点信息。
为了快速检索点，设计了如下的数据结构来支持四叉树的操作。
//矩形区域
struct Region
{
double up; //上边界
double bottom; //下边界
double left; //左边界
double right; //右边界
};
//点结构体
struct ElePoint
{
double lng; //x坐标
double lat; //y坐标
};
3.四叉树结点数据结构：四叉树结点是四叉树结构的主要组成部分，主要用于存储点的最小外包矩形，深度，子节点指针等，也是四叉树算法操作的主要部分。
//四叉树结点
struct QuadTreeNode
{
int depth; //结点的深度
int is_leaf; //是否是叶子节点
struct Region region; //区域范围
struct QuadTreeNode *LU; //左上子节点指针
struct QuadTreeNode *LB; //左下子节点指针
struct QuadTreeNode *RU; //右上子节点指针
struct QuadTreeNode *RB; //右下子节点指针
int ele_num; //矩形区域中位置点数
struct ElePoint *ele_list[MAX_ELE_NUM]; //矩形区域中位置点列表
};
四叉树的主要操作：
（1）判断结点是否已经分裂，已分裂的选择合适的子节点，进行插入；
（2）未分裂的查看是否过载，过载的分裂结点，重新插入；
（3）未过载的直接插入。
示例代码如下：
void insertEle(QuadTreeNode *node, ElePoint ele)
{
//是叶子结点
if (1 == node->is_leaf)
{
if (node->ele_num + 1 > MAX_ELE_NUM)
{
splitNode(node);
//分裂后的 node 不是叶子节点，所以新插入的元素会插入到 node 的子节点上
insertEle(node, ele); //将新插入的元素插入到node的子节点上
}
else
{
ElePoint *ele_ptr = ( ElePoint *) malloc(sizeof(ElePoint));
ele_ptr->lat = ele.lat;
ele_ptr->lng = ele.lng;
//将新插入的点加入到父节点的位置点列表中
node->ele_list[node->ele_num] = ele_ptr;
node->ele_num++;
}
return;
}
//不是叶子结点
double mid_vertical = (node->region.up + node->region.bottom) / 2;
double mid_horizontal = (node->region.left + node->region.right) / 2;
if (ele.lat > mid_vertical)
{
if (ele.lng > mid_horizontal)
{
insertEle(node->RU, ele);
}
else
{
insertEle(node->LU, ele);
}
}
else
{
if (ele.lng > mid_horizontal)
{
insertEle(node->RB, ele);
}
else
{
insertEle(node->LB, ele);
}
}
}
2.分裂结点：对父节点进行分裂，分成四个子区域，其步骤如下：
（1）通过父节点获取子节点的深度和范围；
（2）父节点分裂出四个子节点；
（3）将父节点的元素插入到子节点上，然后释放父节点元素空间
（4）父节点的位置点数-1
示例代码如下：
void splitNode(struct QuadTreeNode *node)
{
double mid_vertical = (node->region.up + node->region.bottom) / 2; //垂直放向的中间线
double mid_horizontal = (node->region.left + node->region.right) / 2; //水平方向的中间线
node->is_leaf = 0;
//生成四个孩子结点
node->RU = createChildNode(node, mid_vertical, node->region.up, mid_horizontal, node->region.right);
node->LU = createChildNode(node, mid_vertical, node->region.up, node->region.left, mid_horizontal);
node->RB = createChildNode(node, node->region.bottom, mid_vertical, mid_horizontal, node->region.right);
node->LB = createChildNode(node, node->region.bottom, mid_vertical, node->region.left, mid_horizontal);
for (int i = 0; i < node->ele_num; i++)
{
//此时插入的时候，node不是叶子节点，此时执行 insert 函数，会将元素插入到孩子节点上
insertEle(node, *node->ele_list[i]); // 将父节点元素 插入到子节点
free(node->ele_list[i]); //释放父节点元素
node->ele_num--; //每插入一个元素，父节点的元素数-1
}
}
3.查询：输入一个检索点，然后输出与这个点在同一个四叉树结点中的所有点，步骤如下：
（1）先判断该点是否是叶子节点；
（2）是叶子结点直接输出该点所在区域的周边点；
（3）不是叶子结点，递归搜索其子节点；
示例代码如下：
void queryEle(struct QuadTreeNode node, struct ElePoint ele)
{
//是叶子结点
if (node.is_leaf == 1)
{
cout << "附近点有" << node.ele_num << "个,分别是：" << endl;
for (int j = 0; j < node.ele_num; j++)
{
cout << "(" << node.ele_list[j]->lng << "," << node.ele_list[j]->lat << ")";
}
return;
}
//不是叶子节点
double mid_vertical = (node.region.up + node.region.bottom) / 2;
double mid_horizontal = (node.region.left + node.region.right) / 2;
if (ele.lat > mid_vertical)
{
if (ele.lng > mid_horizontal)
{
queryEle(*node.RU, ele);
}
else
{
queryEle(*node.LU, ele);
}
}
else
{
if (ele.lng > mid_horizontal)
{
queryEle(*node.RB, ele);
}
else
{
queryEle(*node.LB, ele);
}
}
}
任意区域查询：
//任意区域查询
void queryArea(QuadTreeNode *node, Region *region)
{ //是叶子节点
if (node->is_leaf == 1)
{
//遍历叶子节点中的所有点
for (int i = 0; i < node->ele_num; i++)
{
//如果叶子节点中有点在该矩形区域中，就输出该点坐标
if (node->ele_list[i]->lng >= region->left &&
node->ele_list[i]->lng <= region->right &&
node->ele_list[i]->lat >= region->bottom &&
node->ele_list[i]->lat <= region->up)
{
cout << "(" << node->ele_list[i]->lng << "," << node->ele_list[i]->lat << ") ";
}
}
cout << endl;
return;
}
//不是叶子结点 ， 递归查找与矩形区域有交集的叶子结点
double mid_vertical = (node->region.up + node->region.bottom) / 2;
double mid_horizontal = (node->region.left + node->region.right) / 2;
//讨论矩形区域的9种分布情况
if (region->bottom > mid_vertical){
if (region->left > mid_horizontal){
//如果矩形区域的下边界大，左边界大，就在右上区域查询
queryArea(node->RU, region);
}
else if (region->right < mid_horizontal){
queryArea(node->LU, region);
}
else{
//将该矩形区域分成两块，逐块递归判断其所属的子区域
Region *region1 = (Region *)malloc(sizeof(Region));
*region1 = { region->bottom,region->up,region->left,mid_horizontal };
queryArea(node->LU, region1);
Region *region2 = (Region *)malloc(sizeof(Region));
*region2 = { region->bottom,region->up,mid_horizontal,region->right };
queryArea(node->RU, region2);
}
}
else if (region->up < mid_vertical){
if (region->right < mid_horizontal){
queryArea(node->LB, region);
}
else if (region->left > mid_horizontal){
queryArea(node->RB, region);
}
else{
Region *region1 = (Region *)malloc(sizeof(Region));
*region1 = { region->bottom, region->up,region->left,mid_horizontal };
queryArea(node->LB, region1);
Region *region2 = (Region *)malloc(sizeof(Region));
*region2 = { region->bottom,region->up,mid_horizontal,region->right };
queryArea(node->RB, region2);
}
}
else{
if (region->right < mid_horizontal){
Region *region1 = (Region *)malloc(sizeof(Region));
*region1 = { mid_vertical,region->up,region->left,region->right };
queryArea(node->LU, region1);
Region *region2 = (Region *)malloc(sizeof(Region));
*region2 = { region->bottom,mid_vertical,region->left,region->right };
queryArea(node->LB, region2);
}
else if (region->left > mid_horizontal) {
Region *region1 = (Region *)malloc(sizeof(Region));
*region1 = { mid_vertical,region->up,region->left,region->right };
queryArea(node->RU, region1);
Region *region2 = (Region *)malloc(sizeof(Region));
*region2 = { region->bottom,mid_vertical,region->left,region->right };
queryArea(node->RB, region2);
}
else {
Region *region1 = (Region *)malloc(sizeof(Region));
*region1 = { mid_vertical,region->up,region->left,mid_horizontal };
queryArea(node->LU, region1);
Region *region2 = (Region *)malloc(sizeof(Region));
*region2 = { mid_vertical,region->up,mid_horizontal,region->right };
queryArea(node->RU, region2);
Region *region3 = (Region *)malloc(sizeof(Region));
*region3 = { region->bottom,mid_vertical,region->left,mid_horizontal };
queryArea(node->LB, region3);
Region *region4 = (Region *)malloc(sizeof(Region));
*region4 = { region->bottom, mid_vertical,mid_horizontal,region->right };
queryArea(node->RB, region4);
}
}
}
#include