1.四叉树定义
定义:除叶子节点外，每个节点都有四个子结点。每个节点每有一个对应的矩形区域。
如图所示。
2.四叉树节点类
由上图编写四叉树节点类
// 四叉树节点类型结构
class Quadnode
{
public:
Quadnode(Quadrect theRect, int theLevel);
bool Insert(double x, double y, int depth);
//函数功能:矩形区域查询
//查询矩形queryRect 查询结果 resultPts
void Query(Quadrect queryRect, std::vector<QPointF> & resultPts);
void Traverse(std::vector<QPointF> & resultNode);
Quadrect rect; //节点所代表的矩形区域
std::vector<QPointF> pts;
Quadnode *sub[4]; //指向节点的四个孩子
};
四叉树类
class PointQuadtree
{
public:
//指定四叉树的最大范围和四叉树的深度
PointQuadtree(Quadrect theRect, int theDepth = 4);
bool Insert(double x, double y);
//函数功能:矩形区域查询
//查询矩形queryRect 查询结果 resultNodes
bool Query(Quadrect queryRect, std::vector<QPointF> & resultPts);
Quadrect GetBoundRect();
protected:
Quadrect maxRect; // 四叉树的最大范围
Quadnode *root;
int depth; // 四叉树的深度
};
3.构造四叉树
此文采用逐个插入点，构建四叉树。这里，构造一颗四叉树，首先要指定根节点的最大矩形。只为落在这个矩形范围内的点编制索引。
首先确定插入方法。存存两种插入方法:
(1)只要某个节点对应的矩形包含的点多于一个，就要递归地对其进行分割。这种方法， 将点插入到树的不同层次的节点中。
(2)所有插入点，存放在叶子结点中。
本文采用第二种插入方法。采用这种方法，构造四叉树非常简单。只要简单的递归就行了。具体描述如下：
先判断插入点是否在节点对应的矩形中。如果不在，则返回。如果在，则这个点一定在此节点的某个子节点中，就递归调用其子节点的插入算法。
插入算法代码如下：
bool Quadnode::Insert(double x, double y, int depth)
{
//判断是否在这个节点中
if (!rect.IsInRect(x, y))
return false;
if(0 == depth)
{
pts.push_back(QPointF(x,y));
return true;
}
/* 一个矩形区域的象限划分:
UL(1) | UR(0)
----------|-----------
LL(2) | LR(3)
*/
--depth;
if (sub[0] == 0)
{
sub[0] = new Quadnode(rect.GetUL(), depth);
sub[1] = new Quadnode(rect.GetUR(), depth);
sub[2] = new Quadnode(rect.GetLL(), depth);
sub[3] = new Quadnode(rect.GetLR(), depth);
}
if(sub[0]->Insert(x, y, depth))
return true;
if(sub[1]->Insert(x, y, depth))
return true;
if(sub[2]->Insert(x, y, depth))
return true;
if(sub[3]->Insert(x, y, depth))
return true;
return false;
}
4.矩形查询算法
定义：找出落在矩形查询范围内的点，即是正交区域查询问题。
4.1算法分析
设查询矩形为RecFind，节点的矩形为RecNode。
RecFind与RecNode有四种关系
C1:RecNode包含RecFind
C2:RecFind包含RecNode
C3:RecFind与RecNode相交
C4:RecFind与RecNode相离
分别讨论这四种情况。
C1时，没有必要遍历RecNode同级的其它三个节点了。只需在此节点对应的四个子节点中查找即可。所图C1所示，查找子节点n1,n2,n3,n4。
C2时，RecNode对应的叶子节点中的点都在RecFind内，递归查找RecNode所有点。
C3时，如果RecFind是叶子节点，就检查叶子节点中储存的点是否在RecFind中。如果RecFind不是叶子节点，就在此节点中继续查找，而后在同级的其它三个节点中查找。因为RecFind也可能也其它三个节点相交或包含。
C4时，就不用查了。
只有这四种情况，可按此四种分类编写递归算法，代码如下
void Quadnode::Query(Quadrect queryRect, std::vector<QPointF> & resultPts)
{
if(sub[0] == 0)
{
//查询叶子节点中的点是否矩形中
for (int i = 0; i < pts.size(); ++i)
{
if(queryRect.IsInRect(pts[i].x(), pts[i].y()))
{
resultPts.push_back(pts[i]);
}
}
return;
}
for(int i = 0; i<4; ++i)
{
//[1]节点完全包含查询矩形
//查询这个节点子节点
if(sub[i]->rect.Contain(queryRect))
{
sub[i]->Query(queryRect, resultPts);
break; //没有必须查询其它同级节点了
}
//[2]查询矩形完全包含节点
//则遍历这个节点以下的所有节点，记录在resultNodes中
if(queryRect.Contain(sub[i]->rect))
{
sub[i]->Traverse(resultPts);
continue;
}
//[3]节点与查询矩形相交
//查询这个节点的子节点
if(queryRect.IsInterSect(sub[i]->rect))
{
sub[i]->Query(queryRect, resultPts);
}
}
}
5.四叉树的优缺点
四叉树的优点:(1)矩形查找仅与树的规模和查询矩形有关，与点的数量无关。
四叉树的缺点:(1)事先指定根节点矩形的最大范围，即索引的最大范围。
(2)当对象分布很不均匀时，索引效率低。
6.测试程序截图
