精华内容
下载资源
问答
  • 四叉树

    千次阅读 2016-08-04 16:00:24
    四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,...常规四叉树的结构如图所示,地理空间对象都存储在叶子节点上,中间节点以及根节点不存储地理空间对象。

    四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,如此递归下去,直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的空间数据插入和查询效率,因此四叉树是GIS中常用的空间索引之一。常规四叉树的结构如图所示,地理空间对象都存储在叶子节点上,中间节点以及根节点不存储地理空间对象。

     

    四叉树示意图

     

    四叉树对于区域查询,效率比较高。但如果空间对象分布不均匀,随着地理空间对象的不断插入,四叉树的层次会不断地加深,将形成一棵严重不平衡的四叉树,那么每次查询的深度将大大的增多,从而导致查询效率的急剧下降。

     

    本节将介绍一种改进的四叉树索引结构。四叉树结构是自顶向下逐步划分的一种树状的层次结构。传统的四叉树索引存在着以下几个缺点:

    (1)空间实体只能存储在叶子节点中,中间节点以及根节点不能存储空间实体信息,随着空间对象的不断插入,最终会导致四叉树树的层次比较深,在进行空间数据窗口查询的时候效率会比较低下。

    (2)同一个地理实体在四叉树的分裂过程中极有可能存储在多个节点中,这样就导致了索引存储空间的浪费。

    (3)由于地理空间对象可能分布不均衡,这样会导致常规四叉树生成一棵极为不平衡的树,这样也会造成树结构的不平衡以及存储空间的浪费。

    相应的改进方法,将地理实体信息存储在完全包含它的最小矩形节点中,不存储在它的父节点中,每个地理实体只在树中存储一次,避免存储空间的浪费。首先生成满四叉树,避免在地理实体插入时需要重新分配内存,加快插入的速度,最后将空的节点所占内存空间释放掉。改进后的四叉树结构如下图所示。四叉树的深度一般取经验值4-7之间为最佳。

     

    图改进的四叉树结构

     

    为了维护空间索引与对存储在文件或数据库中的空间数据的一致性,作者设计了如下的数据结构支持四叉树的操作。

    (1)四分区域标识

    分别定义了一个平面区域的四个子区域索引号,右上为第一象限0,左上为第二象限1,左下为第三象限2,右下为第四象限3。

    typedef enum

    {

          UR = 0,// UR第一象限

          UL = 1, // UL为第二象限

          LL = 2, // LL为第三象限

          LR = 3  // LR为第四象限

    }QuadrantEnum;

    (2)空间对象数据结构

    空间对象数据结构是对地理空间对象的近似,在空间索引中,相当一部分都是采用MBR作为近似。

    /*空间对象MBR信息*/

    typedef struct SHPMBRInfo

    {

          int nID;       //空间对象ID号

          MapRect Box;    //空间对象MBR范围坐标

    }SHPMBRInfo;

    nID是空间对象的标识号,Box是空间对象的最小外包矩形(MBR)。

    (3)四叉树节点数据结构

    四叉树节点是四叉树结构的主要组成部分,主要用于存储空间对象的标识号和MBR,也是四叉树算法操作的主要部分。

    /*四叉树节点类型结构*/

    typedef struct QuadNode

    {

          MapRect            Box;                   //节点所代表的矩形区域

          int                nShpCount;        //节点所包含的所有空间对象个数

          SHPMBRInfo* pShapeObj;          //空间对象指针数组

          int         nChildCount;            //子节点个数

          QuadNode *children[4];             //指向节点的四个孩子

    }QuadNode;

    Box是代表四叉树对应区域的最小外包矩形,上一层的节点的最小外包矩形包含下一层最小外包矩形区域;nShpCount代表本节点包含的空间对象的个数;pShapeObj代表指向空间对象存储地址的首地址,同一个节点的空间对象在内存中连续存储;nChildCount代表节点拥有的子节点的数目;children是指向孩子节点指针的数组。

    上述理论部分都都讲的差不多了,下面就贴上我的C语言实现版本代码。

    头文件如下:

    #ifndef __QUADTREE_H_59CAE94A_E937_42AD_AA27_794E467715BB__
    #define __QUADTREE_H_59CAE94A_E937_42AD_AA27_794E467715BB__
    
    
    
    
    /* 一个矩形区域的象限划分::
    
    UL(1)   |    UR(0)
    ----------|-----------
    LL(2)   |    LR(3)
    以下对该象限类型的枚举
    */
    typedef enum
    {
    	UR = 0,
    	UL = 1,
    	LL = 2,
    	LR = 3
    }QuadrantEnum;
    
    /*空间对象MBR信息*/
    typedef struct SHPMBRInfo
    {
    	int nID;		//空间对象ID号
    	MapRect Box;	//空间对象MBR范围坐标
    }SHPMBRInfo;
    
    /* 四叉树节点类型结构 */
    typedef struct QuadNode
    {
    	MapRect		Box;			//节点所代表的矩形区域
    	int			nShpCount;		//节点所包含的所有空间对象个数
    	SHPMBRInfo* pShapeObj;		//空间对象指针数组
    	int		nChildCount;		//子节点个数
    	QuadNode  *children[4];		//指向节点的四个孩子 
    }QuadNode;
    
    /* 四叉树类型结构 */
    typedef struct quadtree_t
    {
    	QuadNode  *root;
    	int         depth;           // 四叉树的深度                    
    }QuadTree;
    
    
    	//初始化四叉树节点
    	QuadNode *InitQuadNode();
    
    	//层次创建四叉树方法(满四叉树)
    	void CreateQuadTree(int depth,GeoLayer *poLayer,QuadTree* pQuadTree);
    
    	//创建各个分支
    	void CreateQuadBranch(int depth,MapRect &rect,QuadNode** node);
    
    	//构建四叉树空间索引
    	void BuildQuadTree(GeoLayer*poLayer,QuadTree* pQuadTree);
    
    	//四叉树索引查询(矩形查询)
    	void SearchQuadTree(QuadNode* node,MapRect &queryRect,vector<int>& ItemSearched);
    
    	//四叉树索引查询(矩形查询)并行查询
    	void SearchQuadTreePara(vector<QuadNode*> resNodes,MapRect &queryRect,vector<int>& ItemSearched);
    
    	//四叉树的查询(点查询)
    	void PtSearchQTree(QuadNode* node,double cx,double cy,vector<int>& ItemSearched);
    
    	//将指定的空间对象插入到四叉树中
    	void Insert(long key,MapRect &itemRect,QuadNode* pNode);
    
    	//将指定的空间对象插入到四叉树中
    	void InsertQuad(long key,MapRect &itemRect,QuadNode* pNode);
    
    	//将指定的空间对象插入到四叉树中
    	void InsertQuad2(long key,MapRect &itemRect,QuadNode* pNode);
    
    	//判断一个节点是否是叶子节点
    	bool IsQuadLeaf(QuadNode* node);
    
    	//删除多余的节点
    	bool DelFalseNode(QuadNode* node);
    
    	//四叉树遍历(所有要素)
    	void TraversalQuadTree(QuadNode* quadTree,vector<int>& resVec);
    
    	//四叉树遍历(所有节点)
    	void TraversalQuadTree(QuadNode* quadTree,vector<QuadNode*>& arrNode);
    
    	//释放树的内存空间
    	void ReleaseQuadTree(QuadNode** quadTree);
    
    	//计算四叉树所占的字节的大小
    	long CalByteQuadTree(QuadNode* quadTree,long& nSize);
    
    
    #endif

    #include "QuadTree.h"
    
    
    QuadNode *InitQuadNode()
    {
    	QuadNode *node = new QuadNode;
    	node->Box.maxX = 0;
    	node->Box.maxY = 0;
    	node->Box.minX = 0;
    	node->Box.minY = 0;
    
    	for (int i = 0; i < 4; i ++)
    	{
    		node->children[i] = NULL;
    	}
    	node->nChildCount = 0;
    	node->nShpCount = 0;
    	node->pShapeObj = NULL;
    
    	return node;
    }
    
    void CreateQuadTree(int depth,GeoLayer *poLayer,QuadTree* pQuadTree)
    {
    	pQuadTree->depth = depth;
    
    	GeoEnvelope env;	//整个图层的MBR
    	poLayer->GetExtent(&env);
    	
    	MapRect rect;
    	rect.minX = env.MinX;
    	rect.minY = env.MinY;
    	rect.maxX = env.MaxX;
    	rect.maxY = env.MaxY;
    	
    	//创建各个分支
    	CreateQuadBranch(depth,rect,&(pQuadTree->root));
    
    	int nCount = poLayer->GetFeatureCount();
    	GeoFeature **pFeatureClass = new GeoFeature*[nCount];
    	for (int i = 0; i < poLayer->GetFeatureCount(); i ++)
    	{
    		pFeatureClass[i] = poLayer->GetFeature(i); 
    	}
    
    	//插入各个要素
    	GeoEnvelope envObj;	//空间对象的MBR
    	//#pragma omp parallel for
    	for (int i = 0; i < nCount; i ++)
    	{
    		pFeatureClass[i]->GetGeometry()->getEnvelope(&envObj);
    		rect.minX = envObj.MinX;
    		rect.minY = envObj.MinY;
    		rect.maxX = envObj.MaxX;
    		rect.maxY = envObj.MaxY;
    		InsertQuad(i,rect,pQuadTree->root);
    	}
    
    	//DelFalseNode(pQuadTree->root);
    }
    
    void CreateQuadBranch(int depth,MapRect &rect,QuadNode** node)
    {
    	if (depth != 0)
    	{
    		*node = InitQuadNode();	//创建树根
    		QuadNode *pNode = *node;
    		pNode->Box = rect;
    		pNode->nChildCount = 4;
    
    		MapRect boxs[4];
    		pNode->Box.Split(boxs,boxs+1,boxs+2,boxs+3);
    		for (int i = 0; i < 4; i ++)
    		{
    			//创建四个节点并插入相应的MBR
    			pNode->children[i] = InitQuadNode();
    			pNode->children[i]->Box = boxs[i];
    
    			CreateQuadBranch(depth-1,boxs[i],&(pNode->children[i]));
    		}
    	}
    }
    
    void BuildQuadTree(GeoLayer *poLayer,QuadTree* pQuadTree)
    {
    	assert(poLayer);
    	GeoEnvelope env;	//整个图层的MBR
    	poLayer->GetExtent(&env);
    	pQuadTree->root = InitQuadNode();
    
    	QuadNode* rootNode = pQuadTree->root;
    
    	rootNode->Box.minX = env.MinX;
    	rootNode->Box.minY = env.MinY;
    	rootNode->Box.maxX = env.MaxX;
    	rootNode->Box.maxY = env.MaxY;
    
    	//设置树的深度(	根据等比数列的求和公式)
    	//pQuadTree->depth = log(poLayer->GetFeatureCount()*3/8.0+1)/log(4.0);
    	int nCount = poLayer->GetFeatureCount();
    
    	MapRect rect;
    	GeoEnvelope envObj;	//空间对象的MBR
    	for (int i = 0; i < nCount; i ++)
    	{
    		poLayer->GetFeature(i)->GetGeometry()->getEnvelope(&envObj);
    		rect.minX = envObj.MinX;
    		rect.minY = envObj.MinY;
    		rect.maxX = envObj.MaxX;
    		rect.maxY = envObj.MaxY;
    		InsertQuad2(i,rect,rootNode);
    	}
    
    	DelFalseNode(pQuadTree->root);
    }
    
    void SearchQuadTree(QuadNode* node,MapRect &queryRect,vector<int>& ItemSearched)
    {
    	assert(node);
    
    	//int coreNum = omp_get_num_procs();
    	//vector<int> * pResArr = new vector<int>[coreNum];
    
    	if (NULL != node)
    	{
    		for (int i = 0; i < node->nShpCount; i ++)
    		{
    			if (queryRect.Contains(node->pShapeObj[i].Box)
    				|| queryRect.Intersects(node->pShapeObj[i].Box))
    			{
    				ItemSearched.push_back(node->pShapeObj[i].nID);
    			}
    		}
    
    		//并行搜索四个孩子节点
    		/*#pragma omp parallel sections
    		{
    			#pragma omp section
    			if ((node->children[0] != NULL) && 
    				(node->children[0]->Box.Contains(queryRect)
    				|| node->children[0]->Box.Intersects(queryRect)))
    			{
    				int tid = omp_get_thread_num();
    				SearchQuadTree(node->children[0],queryRect,pResArr[tid]);
    			}
    
    			#pragma omp section
    			if ((node->children[1] != NULL) && 
    				(node->children[1]->Box.Contains(queryRect)
    				|| node->children[1]->Box.Intersects(queryRect)))
    			{
    				int tid = omp_get_thread_num();
    				SearchQuadTree(node->children[1],queryRect,pResArr[tid]);
    			}
    
    			#pragma omp section
    			if ((node->children[2] != NULL) && 
    				(node->children[2]->Box.Contains(queryRect)
    				|| node->children[2]->Box.Intersects(queryRect)))
    			{
    				int tid = omp_get_thread_num();
    				SearchQuadTree(node->children[2],queryRect,pResArr[tid]);
    			}
    
    			#pragma omp section
    			if ((node->children[3] != NULL) && 
    				(node->children[3]->Box.Contains(queryRect)
    				|| node->children[3]->Box.Intersects(queryRect)))
    			{
    				int tid = omp_get_thread_num();
    				SearchQuadTree(node->children[3],queryRect,pResArr[tid]);
    			}
    		}*/
    		for (int i = 0; i < 4; i ++)
    		{
    			if ((node->children[i] != NULL) && 
    				(node->children[i]->Box.Contains(queryRect)
    				|| node->children[i]->Box.Intersects(queryRect)))
    			{
    				SearchQuadTree(node->children[i],queryRect,ItemSearched);
    				//node = node->children[i];	//非递归
    			}
    		}
    	}
    
    	/*for (int i = 0 ; i < coreNum; i ++)
    	{
    		ItemSearched.insert(ItemSearched.end(),pResArr[i].begin(),pResArr[i].end());
    	}*/
    
    }
    
    void SearchQuadTreePara(vector<QuadNode*> resNodes,MapRect &queryRect,vector<int>& ItemSearched)
    {
    	int coreNum = omp_get_num_procs();
    	omp_set_num_threads(coreNum);
    	vector<int>* searchArrs = new vector<int>[coreNum];
    	for (int i = 0; i < coreNum; i ++)
    	{
    		searchArrs[i].clear();
    	}
    
    	#pragma omp parallel for
    	for (int i = 0; i < resNodes.size(); i ++)
    	{
    		int tid = omp_get_thread_num();
    		for (int j = 0; j < resNodes[i]->nShpCount; j ++)
    		{
    			if (queryRect.Contains(resNodes[i]->pShapeObj[j].Box)
    				|| queryRect.Intersects(resNodes[i]->pShapeObj[j].Box))
    			{
    				searchArrs[tid].push_back(resNodes[i]->pShapeObj[j].nID);
    			}
    		}
    	}
    
    	for (int i = 0; i < coreNum; i ++)
    	{
    		ItemSearched.insert(ItemSearched.end(),
    			searchArrs[i].begin(),searchArrs[i].end());
    	}
    
    	delete [] searchArrs;
    	searchArrs = NULL;
    }
    
    void PtSearchQTree(QuadNode* node,double cx,double cy,vector<int>& ItemSearched)
    {
    	assert(node);
    	if (node->nShpCount >0)		//节点		  
    	{
    		for (int i = 0; i < node->nShpCount; i ++)
    		{
    			if (node->pShapeObj[i].Box.IsPointInRect(cx,cy))
    			{
    				ItemSearched.push_back(node->pShapeObj[i].nID);
    			}
    		}
    	}
    
    	else if (node->nChildCount >0)				//节点
    	{
    		for (int i = 0; i < 4; i ++)
    		{
    			if (node->children[i]->Box.IsPointInRect(cx,cy))
    			{
    				PtSearchQTree(node->children[i],cx,cy,ItemSearched);
    			}
    		}
    	}
    
    	//找出重复元素的位置
    	sort(ItemSearched.begin(),ItemSearched.end());	//先排序,默认升序
    	vector<int>::iterator unique_iter = 
    		unique(ItemSearched.begin(),ItemSearched.end());
    	ItemSearched.erase(unique_iter,ItemSearched.end());
    }
    
    void Insert(long key, MapRect &itemRect,QuadNode* pNode)
    {
    	QuadNode *node = pNode;		//保留根节点副本
    	SHPMBRInfo pShpInfo;
    	
    	//节点有孩子
    	if (0 < node->nChildCount)
    	{
    		for (int i = 0; i < 4; i ++)
    		{  
    			//如果包含或相交,则将节点插入到此节点
    			if (node->children[i]->Box.Contains(itemRect)
    				|| node->children[i]->Box.Intersects(itemRect))
    			{
    				//node = node->children[i];
    				Insert(key,itemRect,node->children[i]);
    			}
    		}
    	}
    
    	//如果当前节点存在一个子节点时
    	else if (1 == node->nShpCount)
    	{
    		MapRect boxs[4];
    		node->Box.Split(boxs,boxs+1,boxs+2,boxs+3);
    
    		//创建四个节点并插入相应的MBR
    		node->children[UR] = InitQuadNode();
    		node->children[UL] = InitQuadNode();
    		node->children[LL] = InitQuadNode();
    		node->children[LR] = InitQuadNode();
    
    		node->children[UR]->Box = boxs[0];
    		node->children[UL]->Box = boxs[1];
    		node->children[LL]->Box = boxs[2];
    		node->children[LR]->Box = boxs[3];
    		node->nChildCount = 4;
    
    		for (int i = 0; i < 4; i ++)
    		{  
    			//将当前节点中的要素移动到相应的子节点中
    			for (int j = 0; j < node->nShpCount; j ++)
    			{
    				if (node->children[i]->Box.Contains(node->pShapeObj[j].Box)
    					|| node->children[i]->Box.Intersects(node->pShapeObj[j].Box))
    				{
    					node->children[i]->nShpCount += 1;
    					node->children[i]->pShapeObj = 
    						(SHPMBRInfo*)malloc(node->children[i]->nShpCount*sizeof(SHPMBRInfo));
    					
    					memcpy(node->children[i]->pShapeObj,&(node->pShapeObj[j]),sizeof(SHPMBRInfo));
    
    					free(node->pShapeObj);
    					node->pShapeObj = NULL;
    					node->nShpCount = 0;
    				}
    			}
    		}
    
    		for (int i = 0; i < 4; i ++)
    		{  
    			//如果包含或相交,则将节点插入到此节点
    			if (node->children[i]->Box.Contains(itemRect)
    				|| node->children[i]->Box.Intersects(itemRect))
    			{
    				if (node->children[i]->nShpCount == 0)	 //如果之前没有节点
    				{
    					node->children[i]->nShpCount += 1;
    					node->pShapeObj = 
    						(SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->children[i]->nShpCount);
    				}
    				else if	(node->children[i]->nShpCount > 0)
    				{
    					node->children[i]->nShpCount += 1;
    					node->children[i]->pShapeObj = 
    						(SHPMBRInfo *)realloc(node->children[i]->pShapeObj,
    						sizeof(SHPMBRInfo)*node->children[i]->nShpCount);
    				}
    
    				pShpInfo.Box = itemRect;
    				pShpInfo.nID = key;
    				memcpy(node->children[i]->pShapeObj,
    					&pShpInfo,sizeof(SHPMBRInfo));
    			}
    		}
    	}
    
    	//当前节点没有空间对象
    	else if (0 == node->nShpCount)
    	{
    		node->nShpCount += 1;
    		node->pShapeObj = 
    			(SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);
    
    		pShpInfo.Box = itemRect;
    		pShpInfo.nID = key;
    		memcpy(node->pShapeObj,&pShpInfo,sizeof(SHPMBRInfo));
    	}
    }
    
    void InsertQuad(long key,MapRect &itemRect,QuadNode* pNode)
    {
    	assert(pNode != NULL);
    
    	if (!IsQuadLeaf(pNode))	   //非叶子节点
    	{
    		int nCorver = 0;		//跨越的子节点个数
    		int iIndex = -1;		//被哪个子节点完全包含的索引号
    		for (int i = 0; i < 4; i ++)
    		{
    			if (pNode->children[i]->Box.Contains(itemRect)
    				&& pNode->Box.Contains(itemRect))
    			{
    				nCorver += 1;
    				iIndex = i;
    			}
    		}
    
    		//如果被某一个子节点包含,则进入该子节点
    		if (/*pNode->Box.Contains(itemRect) || 
    			pNode->Box.Intersects(itemRect)*/1 <= nCorver)
    		{ 
    			InsertQuad(key,itemRect,pNode->children[iIndex]);
    		}
    
    		//如果跨越了多个子节点,直接放在这个节点中
    		else if (nCorver == 0)
    		{
    			if (pNode->nShpCount == 0)	 //如果之前没有节点
    			{
    				pNode->nShpCount += 1;
    				pNode->pShapeObj = 
    					(SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*pNode->nShpCount);
    			}
    			else
    			{
    				pNode->nShpCount += 1;
    				pNode->pShapeObj = 
    					(SHPMBRInfo *)realloc(pNode->pShapeObj,sizeof(SHPMBRInfo)*pNode->nShpCount);
    			}
    
    			SHPMBRInfo pShpInfo;
    			pShpInfo.Box = itemRect;
    			pShpInfo.nID = key;
    			memcpy(pNode->pShapeObj+pNode->nShpCount-1,&pShpInfo,sizeof(SHPMBRInfo));
    		}
    	}
    
    	//如果是叶子节点,直接放进去
    	else if (IsQuadLeaf(pNode))
    	{
    		if (pNode->nShpCount == 0)	 //如果之前没有节点
    		{
    			pNode->nShpCount += 1;
    			pNode->pShapeObj = 
    				(SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*pNode->nShpCount);
    		}
    		else
    		{
    			pNode->nShpCount += 1;
    			pNode->pShapeObj = 
    				(SHPMBRInfo *)realloc(pNode->pShapeObj,sizeof(SHPMBRInfo)*pNode->nShpCount);
    		}
    
    		SHPMBRInfo pShpInfo;
    		pShpInfo.Box = itemRect;
    		pShpInfo.nID = key;
    		memcpy(pNode->pShapeObj+pNode->nShpCount-1,&pShpInfo,sizeof(SHPMBRInfo));
    	}
    }
    
    void InsertQuad2(long key,MapRect &itemRect,QuadNode* pNode)
    {
    	QuadNode *node = pNode;		//保留根节点副本
    	SHPMBRInfo pShpInfo;
    
    	//节点有孩子
    	if (0 < node->nChildCount)
    	{
    		for (int i = 0; i < 4; i ++)
    		{  
    			//如果包含或相交,则将节点插入到此节点
    			if (node->children[i]->Box.Contains(itemRect)
    				|| node->children[i]->Box.Intersects(itemRect))
    			{
    				//node = node->children[i];
    				Insert(key,itemRect,node->children[i]);
    			}
    		}
    	}
    
    	//如果当前节点存在一个子节点时
    	else if (0 == node->nChildCount)
    	{
    		MapRect boxs[4];
    		node->Box.Split(boxs,boxs+1,boxs+2,boxs+3);
    
    		int cnt = -1;
    		for (int i = 0; i < 4; i ++)
    		{  
    			//如果包含或相交,则将节点插入到此节点
    			if (boxs[i].Contains(itemRect))
    			{
    				cnt = i;
    			}
    		}
    
    		//如果有一个矩形包含此对象,则创建四个孩子节点
    		if (cnt > -1)
    		{
    			for (int i = 0; i < 4; i ++)
    			{
    				//创建四个节点并插入相应的MBR
    				node->children[i] = InitQuadNode();
    				node->children[i]->Box = boxs[i];
    			}
    			node->nChildCount = 4;
    			InsertQuad2(key,itemRect,node->children[cnt]);	//递归
    		}
    
    		//如果都不包含,则直接将对象插入此节点
    		if (cnt == -1)
    		{
    			if (node->nShpCount == 0)	 //如果之前没有节点
    			{
    				node->nShpCount += 1;
    				node->pShapeObj = 
    					(SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);
    			}
    			else if	(node->nShpCount > 0)
    			{
    				node->nShpCount += 1;
    				node->pShapeObj = 
    					(SHPMBRInfo *)realloc(node->pShapeObj,
    					sizeof(SHPMBRInfo)*node->nShpCount);
    			}
    
    			pShpInfo.Box = itemRect;
    			pShpInfo.nID = key;
    			memcpy(node->pShapeObj,
    				&pShpInfo,sizeof(SHPMBRInfo));
    		}
    	}
    
    	//当前节点没有空间对象
    	/*else if (0 == node->nShpCount)
    	{
    		node->nShpCount += 1;
    		node->pShapeObj = 
    			(SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);
    
    		pShpInfo.Box = itemRect;
    		pShpInfo.nID = key;
    		memcpy(node->pShapeObj,&pShpInfo,sizeof(SHPMBRInfo));
    	}*/
    }
    
    bool IsQuadLeaf(QuadNode* node)
    {
    	if (NULL == node)
    	{
    		return 1;
    	}
    	for (int i = 0; i < 4; i ++)
    	{
    		if (node->children[i] != NULL)
    		{
    			return 0;
    		}
    	}
    
    	return 1;
    }
    
    bool DelFalseNode(QuadNode* node)
    {
    	//如果没有子节点且没有要素
    	if (node->nChildCount ==0 && node->nShpCount == 0)
    	{
    		ReleaseQuadTree(&node);
    	}
    
    	//如果有子节点
    	else if (node->nChildCount > 0)
    	{
    		for (int i = 0; i < 4; i ++)
    		{
    			DelFalseNode(node->children[i]);
    		}
    	}
    
    	return 1;
    }
    
    void TraversalQuadTree(QuadNode* quadTree,vector<int>& resVec)
    {
    	QuadNode *node = quadTree;
    	int i = 0; 
    	if (NULL != node)
    	{
    		//将本节点中的空间对象存储数组中
    		for (i = 0; i < node->nShpCount; i ++)
    		{
    			resVec.push_back((node->pShapeObj+i)->nID);
    		}
    
    		//遍历孩子节点
    		for (i = 0; i < node->nChildCount; i ++)
    		{
    			if (node->children[i] != NULL)
    			{
    				TraversalQuadTree(node->children[i],resVec);
    			}
    		}
    	}
    
    }
    
    void TraversalQuadTree(QuadNode* quadTree,vector<QuadNode*>& arrNode)
    {
    	deque<QuadNode*> nodeQueue;
    	if (quadTree != NULL)
    	{
    		nodeQueue.push_back(quadTree);
    		while (!nodeQueue.empty())
    		{
    			QuadNode* queueHead = nodeQueue.at(0);	//取队列头结点
    			arrNode.push_back(queueHead);
    			nodeQueue.pop_front();
    			for (int i = 0; i < 4; i ++)
    			{
    				if (queueHead->children[i] != NULL)
    				{
    					nodeQueue.push_back(queueHead->children[i]);
    				}
    			}
    		}
    	}
    }
    
    void ReleaseQuadTree(QuadNode** quadTree)
    {
    	int i = 0;
    	QuadNode* node = *quadTree;
    	if (NULL == node)
    	{
    		return;
    	}
    
    	else
    	{
    		for (i = 0; i < 4; i ++)
    		{ 
    			ReleaseQuadTree(&node->children[i]);
    		}
    		free(node);
    		node = NULL;
    	}
    
    	node = NULL;
    }
    
    long CalByteQuadTree(QuadNode* quadTree,long& nSize)
    {
    	if (quadTree != NULL)
    	{
    		nSize += sizeof(QuadNode)+quadTree->nChildCount*sizeof(SHPMBRInfo);
    		for (int i = 0; i < 4; i ++)
    		{
    			if (quadTree->children[i] != NULL)
    			{
    				nSize += CalByteQuadTree(quadTree->children[i],nSize);
    			}
    		}
    	}
    
    	return 1;
    }




    展开全文
  • 今天依然在放假中,在此将以前在学校写的四叉树的东西拿出来和大家分享。...常规四叉树的结构如图所示,地理空间对象都存储在叶子节点上,中间节点以及根节点不存储地理空间对象。 四叉树示意图 四叉树对于..

    今天依然在放假中,在此将以前在学校写的四叉树的东西拿出来和大家分享。

    四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,如此递归下去,直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的空间数据插入和查询效率,因此四叉树是GIS中常用的空间索引之一。常规四叉树的结构如图所示,地理空间对象都存储在叶子节点上,中间节点以及根节点不存储地理空间对象。

     


    四叉树示意图

     

    四叉树对于区域查询,效率比较高。但如果空间对象分布不均匀,随着地理空间对象的不断插入,四叉树的层次会不断地加深,将形成一棵严重不平衡的四叉树,那么每次查询的深度将大大的增多,从而导致查询效率的急剧下降。

     

    本节将介绍一种改进的四叉树索引结构。四叉树结构是自顶向下逐步划分的一种树状的层次结构。传统的四叉树索引存在着以下几个缺点:

    (1)空间实体只能存储在叶子节点中,中间节点以及根节点不能存储空间实体信息,随着空间对象的不断插入,最终会导致四叉树树的层次比较深,在进行空间数据窗口查询的时候效率会比较低下。

    (2)同一个地理实体在四叉树的分裂过程中极有可能存储在多个节点中,这样就导致了索引存储空间的浪费。

    (3)由于地理空间对象可能分布不均衡,这样会导致常规四叉树生成一棵极为不平衡的树,这样也会造成树结构的不平衡以及存储空间的浪费。

    相应的改进方法,将地理实体信息存储在完全包含它的最小矩形节点中,不存储在它的父节点中,每个地理实体只在树中存储一次,避免存储空间的浪费。首先生成满四叉树,避免在地理实体插入时需要重新分配内存,加快插入的速度,最后将空的节点所占内存空间释放掉。改进后的四叉树结构如下图所示。四叉树的深度一般取经验值4-7之间为最佳。

     

    图改进的四叉树结构

     

    为了维护空间索引与对存储在文件或数据库中的空间数据的一致性,作者设计了如下的数据结构支持四叉树的操作。

    (1)四分区域标识

    分别定义了一个平面区域的四个子区域索引号,右上为第一象限0,左上为第二象限1,左下为第三象限2,右下为第四象限3。

    typedef enum

    {

          UR = 0,// UR第一象限

          UL = 1, // UL为第二象限

          LL = 2, // LL为第三象限

          LR = 3  // LR为第四象限

    }QuadrantEnum;

    (2)空间对象数据结构

    空间对象数据结构是对地理空间对象的近似,在空间索引中,相当一部分都是采用MBR作为近似。

    /*空间对象MBR信息*/

    typedef struct SHPMBRInfo

    {

          int nID;       //空间对象ID号

          MapRect Box;    //空间对象MBR范围坐标

    }SHPMBRInfo;

    nID是空间对象的标识号,Box是空间对象的最小外包矩形(MBR)。

    (3)四叉树节点数据结构

    四叉树节点是四叉树结构的主要组成部分,主要用于存储空间对象的标识号和MBR,也是四叉树算法操作的主要部分。

    /*四叉树节点类型结构*/

    typedef struct QuadNode

    {

          MapRect            Box;                   //节点所代表的矩形区域

          int                nShpCount;        //节点所包含的所有空间对象个数

          SHPMBRInfo* pShapeObj;          //空间对象指针数组

          int         nChildCount;            //子节点个数

          QuadNode *children[4];             //指向节点的四个孩子

    }QuadNode;

    Box是代表四叉树对应区域的最小外包矩形,上一层的节点的最小外包矩形包含下一层最小外包矩形区域;nShpCount代表本节点包含的空间对象的个数;pShapeObj代表指向空间对象存储地址的首地址,同一个节点的空间对象在内存中连续存储;nChildCount代表节点拥有的子节点的数目;children是指向孩子节点指针的数组。

    上述理论部分都都讲的差不多了,下面就贴上我的C语言实现版本代码。

    头文件如下:

    #ifndef __QUADTREE_H_59CAE94A_E937_42AD_AA27_794E467715BB__
    #define __QUADTREE_H_59CAE94A_E937_42AD_AA27_794E467715BB__
     
     
     
     
    /* 一个矩形区域的象限划分::
    UL(1)   |    UR(0)
    ----------|-----------
    LL(2)   |    LR(3)
    以下对该象限类型的枚举
    */
    typedef enum
    {
        UR = 0,
        UL = 1,
        LL = 2,
        LR = 3
    }QuadrantEnum;
     
    /*空间对象MBR信息*/
    typedef struct SHPMBRInfo
    {
        int nID;        //空间对象ID号
        MapRect Box;    //空间对象MBR范围坐标
    }SHPMBRInfo;
     
    /* 四叉树节点类型结构 */
    typedef struct QuadNode
    {
        MapRect        Box;            //节点所代表的矩形区域
        int            nShpCount;        //节点所包含的所有空间对象个数
        SHPMBRInfo* pShapeObj;        //空间对象指针数组
        int        nChildCount;        //子节点个数
        QuadNode  *children[4];        //指向节点的四个孩子 
    }QuadNode;
     
    /* 四叉树类型结构 */
    typedef struct quadtree_t
    {
        QuadNode  *root;
        int         depth;           // 四叉树的深度                    
    }QuadTree;
     
     
        //初始化四叉树节点
        QuadNode *InitQuadNode();
     
        //层次创建四叉树方法(满四叉树)
        void CreateQuadTree(int depth,GeoLayer *poLayer,QuadTree* pQuadTree);
     
        //创建各个分支
        void CreateQuadBranch(int depth,MapRect &rect,QuadNode** node);
     
        //构建四叉树空间索引
        void BuildQuadTree(GeoLayer*poLayer,QuadTree* pQuadTree);
     
        //四叉树索引查询(矩形查询)
        void SearchQuadTree(QuadNode* node,MapRect &queryRect,vector<int>& ItemSearched);
     
        //四叉树索引查询(矩形查询)并行查询
        void SearchQuadTreePara(vector<QuadNode*> resNodes,MapRect &queryRect,vector<int>& ItemSearched);
     
        //四叉树的查询(点查询)
        void PtSearchQTree(QuadNode* node,double cx,double cy,vector<int>& ItemSearched);
     
        //将指定的空间对象插入到四叉树中
        void Insert(long key,MapRect &itemRect,QuadNode* pNode);
     
        //将指定的空间对象插入到四叉树中
        void InsertQuad(long key,MapRect &itemRect,QuadNode* pNode);
     
        //将指定的空间对象插入到四叉树中
        void InsertQuad2(long key,MapRect &itemRect,QuadNode* pNode);
     
        //判断一个节点是否是叶子节点
        bool IsQuadLeaf(QuadNode* node);
     
        //删除多余的节点
        bool DelFalseNode(QuadNode* node);
     
        //四叉树遍历(所有要素)
        void TraversalQuadTree(QuadNode* quadTree,vector<int>& resVec);
     
        //四叉树遍历(所有节点)
        void TraversalQuadTree(QuadNode* quadTree,vector<QuadNode*>& arrNode);
     
        //释放树的内存空间
        void ReleaseQuadTree(QuadNode** quadTree);
     
        //计算四叉树所占的字节的大小
        long CalByteQuadTree(QuadNode* quadTree,long& nSize);
     
     
    #endif

    源文件如下:

    #include "QuadTree.h"
     
     
    QuadNode *InitQuadNode()
    {
        QuadNode *node = new QuadNode;
        node->Box.maxX = 0;
        node->Box.maxY = 0;
        node->Box.minX = 0;
        node->Box.minY = 0;
     
        for (int i = 0; i < 4; i ++)
        {
            node->children[i] = NULL;
        }
        node->nChildCount = 0;
        node->nShpCount = 0;
        node->pShapeObj = NULL;
     
        return node;
    }
     
    void CreateQuadTree(int depth,GeoLayer *poLayer,QuadTree* pQuadTree)
    {
        pQuadTree->depth = depth;
     
        GeoEnvelope env;    //整个图层的MBR
        poLayer->GetExtent(&env);
        
        MapRect rect;
        rect.minX = env.MinX;
        rect.minY = env.MinY;
        rect.maxX = env.MaxX;
        rect.maxY = env.MaxY;
        
        //创建各个分支
        CreateQuadBranch(depth,rect,&(pQuadTree->root));
     
        int nCount = poLayer->GetFeatureCount();
        GeoFeature **pFeatureClass = new GeoFeature*[nCount];
        for (int i = 0; i < poLayer->GetFeatureCount(); i ++)
        {
            pFeatureClass[i] = poLayer->GetFeature(i); 
        }
     
        //插入各个要素
        GeoEnvelope envObj;    //空间对象的MBR
        //#pragma omp parallel for
        for (int i = 0; i < nCount; i ++)
        {
            pFeatureClass[i]->GetGeometry()->getEnvelope(&envObj);
            rect.minX = envObj.MinX;
            rect.minY = envObj.MinY;
            rect.maxX = envObj.MaxX;
            rect.maxY = envObj.MaxY;
            InsertQuad(i,rect,pQuadTree->root);
        }
     
        //DelFalseNode(pQuadTree->root);
    }
     
    void CreateQuadBranch(int depth,MapRect &rect,QuadNode** node)
    {
        if (depth != 0)
        {
            *node = InitQuadNode();    //创建树根
            QuadNode *pNode = *node;
            pNode->Box = rect;
            pNode->nChildCount = 4;
     
            MapRect boxs[4];
            pNode->Box.Split(boxs,boxs+1,boxs+2,boxs+3);
            for (int i = 0; i < 4; i ++)
            {
                //创建四个节点并插入相应的MBR
                pNode->children[i] = InitQuadNode();
                pNode->children[i]->Box = boxs[i];
     
                CreateQuadBranch(depth-1,boxs[i],&(pNode->children[i]));
            }
        }
    }
     
    void BuildQuadTree(GeoLayer *poLayer,QuadTree* pQuadTree)
    {
        assert(poLayer);
        GeoEnvelope env;    //整个图层的MBR
        poLayer->GetExtent(&env);
        pQuadTree->root = InitQuadNode();
     
        QuadNode* rootNode = pQuadTree->root;
     
        rootNode->Box.minX = env.MinX;
        rootNode->Box.minY = env.MinY;
        rootNode->Box.maxX = env.MaxX;
        rootNode->Box.maxY = env.MaxY;
     
        //设置树的深度(    根据等比数列的求和公式)
        //pQuadTree->depth = log(poLayer->GetFeatureCount()*3/8.0+1)/log(4.0);
        int nCount = poLayer->GetFeatureCount();
     
        MapRect rect;
        GeoEnvelope envObj;    //空间对象的MBR
        for (int i = 0; i < nCount; i ++)
        {
            poLayer->GetFeature(i)->GetGeometry()->getEnvelope(&envObj);
            rect.minX = envObj.MinX;
            rect.minY = envObj.MinY;
            rect.maxX = envObj.MaxX;
            rect.maxY = envObj.MaxY;
            InsertQuad2(i,rect,rootNode);
        }
     
        DelFalseNode(pQuadTree->root);
    }
     
    void SearchQuadTree(QuadNode* node,MapRect &queryRect,vector<int>& ItemSearched)
    {
        assert(node);
     
        //int coreNum = omp_get_num_procs();
        //vector<int> * pResArr = new vector<int>[coreNum];
     
        if (NULL != node)
        {
            for (int i = 0; i < node->nShpCount; i ++)
            {
                if (queryRect.Contains(node->pShapeObj[i].Box)
                    || queryRect.Intersects(node->pShapeObj[i].Box))
                {
                    ItemSearched.push_back(node->pShapeObj[i].nID);
                }
            }
     
            //并行搜索四个孩子节点
            /*#pragma omp parallel sections
            {
                #pragma omp section
                if ((node->children[0] != NULL) && 
                    (node->children[0]->Box.Contains(queryRect)
                    || node->children[0]->Box.Intersects(queryRect)))
                {
                    int tid = omp_get_thread_num();
                    SearchQuadTree(node->children[0],queryRect,pResArr[tid]);
                }
                #pragma omp section
                if ((node->children[1] != NULL) && 
                    (node->children[1]->Box.Contains(queryRect)
                    || node->children[1]->Box.Intersects(queryRect)))
                {
                    int tid = omp_get_thread_num();
                    SearchQuadTree(node->children[1],queryRect,pResArr[tid]);
                }
                #pragma omp section
                if ((node->children[2] != NULL) && 
                    (node->children[2]->Box.Contains(queryRect)
                    || node->children[2]->Box.Intersects(queryRect)))
                {
                    int tid = omp_get_thread_num();
                    SearchQuadTree(node->children[2],queryRect,pResArr[tid]);
                }
                #pragma omp section
                if ((node->children[3] != NULL) && 
                    (node->children[3]->Box.Contains(queryRect)
                    || node->children[3]->Box.Intersects(queryRect)))
                {
                    int tid = omp_get_thread_num();
                    SearchQuadTree(node->children[3],queryRect,pResArr[tid]);
                }
            }*/
            for (int i = 0; i < 4; i ++)
            {
                if ((node->children[i] != NULL) && 
                    (node->children[i]->Box.Contains(queryRect)
                    || node->children[i]->Box.Intersects(queryRect)))
                {
                    SearchQuadTree(node->children[i],queryRect,ItemSearched);
                    //node = node->children[i];    //非递归
                }
            }
        }
     
        /*for (int i = 0 ; i < coreNum; i ++)
        {
            ItemSearched.insert(ItemSearched.end(),pResArr[i].begin(),pResArr[i].end());
        }*/
     
    }
     
    void SearchQuadTreePara(vector<QuadNode*> resNodes,MapRect &queryRect,vector<int>& ItemSearched)
    {
        int coreNum = omp_get_num_procs();
        omp_set_num_threads(coreNum);
        vector<int>* searchArrs = new vector<int>[coreNum];
        for (int i = 0; i < coreNum; i ++)
        {
            searchArrs[i].clear();
        }
     
        #pragma omp parallel for
        for (int i = 0; i < resNodes.size(); i ++)
        {
            int tid = omp_get_thread_num();
            for (int j = 0; j < resNodes[i]->nShpCount; j ++)
            {
                if (queryRect.Contains(resNodes[i]->pShapeObj[j].Box)
                    || queryRect.Intersects(resNodes[i]->pShapeObj[j].Box))
                {
                    searchArrs[tid].push_back(resNodes[i]->pShapeObj[j].nID);
                }
            }
        }
     
        for (int i = 0; i < coreNum; i ++)
        {
            ItemSearched.insert(ItemSearched.end(),
                searchArrs[i].begin(),searchArrs[i].end());
        }
     
        delete [] searchArrs;
        searchArrs = NULL;
    }
     
    void PtSearchQTree(QuadNode* node,double cx,double cy,vector<int>& ItemSearched)
    {
        assert(node);
        if (node->nShpCount >0)        //节点          
        {
            for (int i = 0; i < node->nShpCount; i ++)
            {
                if (node->pShapeObj[i].Box.IsPointInRect(cx,cy))
                {
                    ItemSearched.push_back(node->pShapeObj[i].nID);
                }
            }
        }
     
        else if (node->nChildCount >0)                //节点
        {
            for (int i = 0; i < 4; i ++)
            {
                if (node->children[i]->Box.IsPointInRect(cx,cy))
                {
                    PtSearchQTree(node->children[i],cx,cy,ItemSearched);
                }
            }
        }
     
        //找出重复元素的位置
        sort(ItemSearched.begin(),ItemSearched.end());    //先排序,默认升序
        vector<int>::iterator unique_iter = 
            unique(ItemSearched.begin(),ItemSearched.end());
        ItemSearched.erase(unique_iter,ItemSearched.end());
    }
     
    void Insert(long key, MapRect &itemRect,QuadNode* pNode)
    {
        QuadNode *node = pNode;        //保留根节点副本
        SHPMBRInfo pShpInfo;
        
        //节点有孩子
        if (0 < node->nChildCount)
        {
            for (int i = 0; i < 4; i ++)
            {  
                //如果包含或相交,则将节点插入到此节点
                if (node->children[i]->Box.Contains(itemRect)
                    || node->children[i]->Box.Intersects(itemRect))
                {
                    //node = node->children[i];
                    Insert(key,itemRect,node->children[i]);
                }
            }
        }
     
        //如果当前节点存在一个子节点时
        else if (1 == node->nShpCount)
        {
            MapRect boxs[4];
            node->Box.Split(boxs,boxs+1,boxs+2,boxs+3);
     
            //创建四个节点并插入相应的MBR
            node->children[UR] = InitQuadNode();
            node->children[UL] = InitQuadNode();
            node->children[LL] = InitQuadNode();
            node->children[LR] = InitQuadNode();
     
            node->children[UR]->Box = boxs[0];
            node->children[UL]->Box = boxs[1];
            node->children[LL]->Box = boxs[2];
            node->children[LR]->Box = boxs[3];
            node->nChildCount = 4;
     
            for (int i = 0; i < 4; i ++)
            {  
                //将当前节点中的要素移动到相应的子节点中
                for (int j = 0; j < node->nShpCount; j ++)
                {
                    if (node->children[i]->Box.Contains(node->pShapeObj[j].Box)
                        || node->children[i]->Box.Intersects(node->pShapeObj[j].Box))
                    {
                        node->children[i]->nShpCount += 1;
                        node->children[i]->pShapeObj = 
                            (SHPMBRInfo*)malloc(node->children[i]->nShpCount*sizeof(SHPMBRInfo));
                        
                        memcpy(node->children[i]->pShapeObj,&(node->pShapeObj[j]),sizeof(SHPMBRInfo));
     
                        free(node->pShapeObj);
                        node->pShapeObj = NULL;
                        node->nShpCount = 0;
                    }
                }
            }
     
            for (int i = 0; i < 4; i ++)
            {  
                //如果包含或相交,则将节点插入到此节点
                if (node->children[i]->Box.Contains(itemRect)
                    || node->children[i]->Box.Intersects(itemRect))
                {
                    if (node->children[i]->nShpCount == 0)     //如果之前没有节点
                    {
                        node->children[i]->nShpCount += 1;
                        node->pShapeObj = 
                            (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->children[i]->nShpCount);
                    }
                    else if    (node->children[i]->nShpCount > 0)
                    {
                        node->children[i]->nShpCount += 1;
                        node->children[i]->pShapeObj = 
                            (SHPMBRInfo *)realloc(node->children[i]->pShapeObj,
                            sizeof(SHPMBRInfo)*node->children[i]->nShpCount);
                    }
     
                    pShpInfo.Box = itemRect;
                    pShpInfo.nID = key;
                    memcpy(node->children[i]->pShapeObj,
                        &pShpInfo,sizeof(SHPMBRInfo));
                }
            }
        }
     
        //当前节点没有空间对象
        else if (0 == node->nShpCount)
        {
            node->nShpCount += 1;
            node->pShapeObj = 
                (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);
     
            pShpInfo.Box = itemRect;
            pShpInfo.nID = key;
            memcpy(node->pShapeObj,&pShpInfo,sizeof(SHPMBRInfo));
        }
    }
     
    void InsertQuad(long key,MapRect &itemRect,QuadNode* pNode)
    {
        assert(pNode != NULL);
     
        if (!IsQuadLeaf(pNode))       //非叶子节点
        {
            int nCorver = 0;        //跨越的子节点个数
            int iIndex = -1;        //被哪个子节点完全包含的索引号
            for (int i = 0; i < 4; i ++)
            {
                if (pNode->children[i]->Box.Contains(itemRect)
                    && pNode->Box.Contains(itemRect))
                {
                    nCorver += 1;
                    iIndex = i;
                }
            }
     
            //如果被某一个子节点包含,则进入该子节点
            if (/*pNode->Box.Contains(itemRect) || 
                pNode->Box.Intersects(itemRect)*/1 <= nCorver)
            { 
                InsertQuad(key,itemRect,pNode->children[iIndex]);
            }
     
            //如果跨越了多个子节点,直接放在这个节点中
            else if (nCorver == 0)
            {
                if (pNode->nShpCount == 0)     //如果之前没有节点
                {
                    pNode->nShpCount += 1;
                    pNode->pShapeObj = 
                        (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*pNode->nShpCount);
                }
                else
                {
                    pNode->nShpCount += 1;
                    pNode->pShapeObj = 
                        (SHPMBRInfo *)realloc(pNode->pShapeObj,sizeof(SHPMBRInfo)*pNode->nShpCount);
                }
     
                SHPMBRInfo pShpInfo;
                pShpInfo.Box = itemRect;
                pShpInfo.nID = key;
                memcpy(pNode->pShapeObj+pNode->nShpCount-1,&pShpInfo,sizeof(SHPMBRInfo));
            }
        }
     
        //如果是叶子节点,直接放进去
        else if (IsQuadLeaf(pNode))
        {
            if (pNode->nShpCount == 0)     //如果之前没有节点
            {
                pNode->nShpCount += 1;
                pNode->pShapeObj = 
                    (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*pNode->nShpCount);
            }
            else
            {
                pNode->nShpCount += 1;
                pNode->pShapeObj = 
                    (SHPMBRInfo *)realloc(pNode->pShapeObj,sizeof(SHPMBRInfo)*pNode->nShpCount);
            }
     
            SHPMBRInfo pShpInfo;
            pShpInfo.Box = itemRect;
            pShpInfo.nID = key;
            memcpy(pNode->pShapeObj+pNode->nShpCount-1,&pShpInfo,sizeof(SHPMBRInfo));
        }
    }
     
    void InsertQuad2(long key,MapRect &itemRect,QuadNode* pNode)
    {
        QuadNode *node = pNode;        //保留根节点副本
        SHPMBRInfo pShpInfo;
     
        //节点有孩子
        if (0 < node->nChildCount)
        {
            for (int i = 0; i < 4; i ++)
            {  
                //如果包含或相交,则将节点插入到此节点
                if (node->children[i]->Box.Contains(itemRect)
                    || node->children[i]->Box.Intersects(itemRect))
                {
                    //node = node->children[i];
                    Insert(key,itemRect,node->children[i]);
                }
            }
        }
     
        //如果当前节点存在一个子节点时
        else if (0 == node->nChildCount)
        {
            MapRect boxs[4];
            node->Box.Split(boxs,boxs+1,boxs+2,boxs+3);
     
            int cnt = -1;
            for (int i = 0; i < 4; i ++)
            {  
                //如果包含或相交,则将节点插入到此节点
                if (boxs[i].Contains(itemRect))
                {
                    cnt = i;
                }
            }
     
            //如果有一个矩形包含此对象,则创建四个孩子节点
            if (cnt > -1)
            {
                for (int i = 0; i < 4; i ++)
                {
                    //创建四个节点并插入相应的MBR
                    node->children[i] = InitQuadNode();
                    node->children[i]->Box = boxs[i];
                }
                node->nChildCount = 4;
                InsertQuad2(key,itemRect,node->children[cnt]);    //递归
            }
     
            //如果都不包含,则直接将对象插入此节点
            if (cnt == -1)
            {
                if (node->nShpCount == 0)     //如果之前没有节点
                {
                    node->nShpCount += 1;
                    node->pShapeObj = 
                        (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);
                }
                else if    (node->nShpCount > 0)
                {
                    node->nShpCount += 1;
                    node->pShapeObj = 
                        (SHPMBRInfo *)realloc(node->pShapeObj,
                        sizeof(SHPMBRInfo)*node->nShpCount);
                }
     
                pShpInfo.Box = itemRect;
                pShpInfo.nID = key;
                memcpy(node->pShapeObj,
                    &pShpInfo,sizeof(SHPMBRInfo));
            }
        }
     
        //当前节点没有空间对象
        /*else if (0 == node->nShpCount)
        {
            node->nShpCount += 1;
            node->pShapeObj = 
                (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);
            pShpInfo.Box = itemRect;
            pShpInfo.nID = key;
            memcpy(node->pShapeObj,&pShpInfo,sizeof(SHPMBRInfo));
        }*/
    }
     
    bool IsQuadLeaf(QuadNode* node)
    {
        if (NULL == node)
        {
            return 1;
        }
        for (int i = 0; i < 4; i ++)
        {
            if (node->children[i] != NULL)
            {
                return 0;
            }
        }
     
        return 1;
    }
     
    bool DelFalseNode(QuadNode* node)
    {
        //如果没有子节点且没有要素
        if (node->nChildCount ==0 && node->nShpCount == 0)
        {
            ReleaseQuadTree(&node);
        }
     
        //如果有子节点
        else if (node->nChildCount > 0)
        {
            for (int i = 0; i < 4; i ++)
            {
                DelFalseNode(node->children[i]);
            }
        }
     
        return 1;
    }
     
    void TraversalQuadTree(QuadNode* quadTree,vector<int>& resVec)
    {
        QuadNode *node = quadTree;
        int i = 0; 
        if (NULL != node)
        {
            //将本节点中的空间对象存储数组中
            for (i = 0; i < node->nShpCount; i ++)
            {
                resVec.push_back((node->pShapeObj+i)->nID);
            }
     
            //遍历孩子节点
            for (i = 0; i < node->nChildCount; i ++)
            {
                if (node->children[i] != NULL)
                {
                    TraversalQuadTree(node->children[i],resVec);
                }
            }
        }
     
    }
     
    void TraversalQuadTree(QuadNode* quadTree,vector<QuadNode*>& arrNode)
    {
        deque<QuadNode*> nodeQueue;
        if (quadTree != NULL)
        {
            nodeQueue.push_back(quadTree);
            while (!nodeQueue.empty())
            {
                QuadNode* queueHead = nodeQueue.at(0);    //取队列头结点
                arrNode.push_back(queueHead);
                nodeQueue.pop_front();
                for (int i = 0; i < 4; i ++)
                {
                    if (queueHead->children[i] != NULL)
                    {
                        nodeQueue.push_back(queueHead->children[i]);
                    }
                }
            }
        }
    }
     
    void ReleaseQuadTree(QuadNode** quadTree)
    {
        int i = 0;
        QuadNode* node = *quadTree;
        if (NULL == node)
        {
            return;
        }
     
        else
        {
            for (i = 0; i < 4; i ++)
            { 
                ReleaseQuadTree(&node->children[i]);
            }
            free(node);
            node = NULL;
        }
     
        node = NULL;
    }
     
    long CalByteQuadTree(QuadNode* quadTree,long& nSize)
    {
        if (quadTree != NULL)
        {
            nSize += sizeof(QuadNode)+quadTree->nChildCount*sizeof(SHPMBRInfo);
            for (int i = 0; i < 4; i ++)
            {
                if (quadTree->children[i] != NULL)
                {
                    nSize += CalByteQuadTree(quadTree->children[i],nSize);
                }
            }
        }
     
        return 1;
    }

    代码有点长,有需要的朋友可以借鉴并自己优化。

    展开全文
  • 四叉树空间索引

    千次阅读 2014-02-24 16:39:14
    四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,...常规四叉树的结构如图所示,地理空间对象都存储在叶子节点上,中间节点以及根节点不存储地理空间对象。

    四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,如此递归下去,直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的空间数据插入和查询效率,因此四叉树是GIS中常用的空间索引之一。常规四叉树的结构如图所示,地理空间对象都存储在叶子节点上,中间节点以及根节点不存储地理空间对象。

     

    四叉树示意图

     

    四叉树对于区域查询,效率比较高。但如果空间对象分布不均匀,随着地理空间对象的不断插入,四叉树的层次会不断地加深,将形成一棵严重不平衡的四叉树,那么每次查询的深度将大大的增多,从而导致查询效率的急剧下降。

     

    本节将介绍一种改进的四叉树索引结构。四叉树结构是自顶向下逐步划分的一种树状的层次结构。传统的四叉树索引存在着以下几个缺点:

    (1)空间实体只能存储在叶子节点中,中间节点以及根节点不能存储空间实体信息,随着空间对象的不断插入,最终会导致四叉树树的层次比较深,在进行空间数据窗口查询的时候效率会比较低下。

    (2)同一个地理实体在四叉树的分裂过程中极有可能存储在多个节点中,这样就导致了索引存储空间的浪费。

    (3)由于地理空间对象可能分布不均衡,这样会导致常规四叉树生成一棵极为不平衡的树,这样也会造成树结构的不平衡以及存储空间的浪费。

    相应的改进方法,将地理实体信息存储在完全包含它的最小矩形节点中,不存储在它的父节点中,每个地理实体只在树中存储一次,避免存储空间的浪费。首先生成满四叉树,避免在地理实体插入时需要重新分配内存,加快插入的速度,最后将空的节点所占内存空间释放掉。改进后的四叉树结构如下图所示。四叉树的深度一般取经验值4-7之间为最佳。

     

    图改进的四叉树结构

     

    为了维护空间索引与对存储在文件或数据库中的空间数据的一致性,作者设计了如下的数据结构支持四叉树的操作。

    (1)四分区域标识

    分别定义了一个平面区域的四个子区域索引号,右上为第一象限0,左上为第二象限1,左下为第三象限2,右下为第四象限3。

    typedef enum

    {

          UR = 0,// UR第一象限

          UL = 1, // UL为第二象限

          LL = 2, // LL为第三象限

          LR = 3  // LR为第四象限

    }QuadrantEnum;

    (2)空间对象数据结构

    空间对象数据结构是对地理空间对象的近似,在空间索引中,相当一部分都是采用MBR作为近似。

    /*空间对象MBR信息*/

    typedef struct SHPMBRInfo

    {

          int nID;       //空间对象ID号

          MapRect Box;    //空间对象MBR范围坐标

    }SHPMBRInfo;

    nID是空间对象的标识号,Box是空间对象的最小外包矩形(MBR)。

    (3)四叉树节点数据结构

    四叉树节点是四叉树结构的主要组成部分,主要用于存储空间对象的标识号和MBR,也是四叉树算法操作的主要部分。

    /*四叉树节点类型结构*/

    typedef struct QuadNode

    {

          MapRect            Box;                   //节点所代表的矩形区域

          int                nShpCount;        //节点所包含的所有空间对象个数

          SHPMBRInfo* pShapeObj;          //空间对象指针数组

          int         nChildCount;            //子节点个数

          QuadNode *children[4];             //指向节点的四个孩子

    }QuadNode;

    Box是代表四叉树对应区域的最小外包矩形,上一层的节点的最小外包矩形包含下一层最小外包矩形区域;nShpCount代表本节点包含的空间对象的个数;pShapeObj代表指向空间对象存储地址的首地址,同一个节点的空间对象在内存中连续存储;nChildCount代表节点拥有的子节点的数目;children是指向孩子节点指针的数组。

    上述理论部分都都讲的差不多了,下面就贴上我的C语言实现版本代码。

    头文件如下:

    1. #ifndef __QUADTREE_H_59CAE94A_E937_42AD_AA27_794E467715BB__  
    2. #define __QUADTREE_H_59CAE94A_E937_42AD_AA27_794E467715BB__  
    3.   
    4.   
    5.   
    6.   
    7. /* 一个矩形区域的象限划分:: 
    8.  
    9. UL(1)   |    UR(0) 
    10. ----------|----------- 
    11. LL(2)   |    LR(3) 
    12. 以下对该象限类型的枚举 
    13. */  
    14. typedef enum  
    15. {  
    16.     UR = 0,  
    17.     UL = 1,  
    18.     LL = 2,  
    19.     LR = 3  
    20. }QuadrantEnum;  
    21.   
    22. /*空间对象MBR信息*/  
    23. typedef struct SHPMBRInfo  
    24. {  
    25.     int nID;        //空间对象ID号  
    26.     MapRect Box;    //空间对象MBR范围坐标  
    27. }SHPMBRInfo;  
    28.   
    29. /* 四叉树节点类型结构 */  
    30. typedef struct QuadNode  
    31. {  
    32.     MapRect     Box;            //节点所代表的矩形区域  
    33.     int         nShpCount;      //节点所包含的所有空间对象个数  
    34.     SHPMBRInfo* pShapeObj;      //空间对象指针数组  
    35.     int     nChildCount;        //子节点个数  
    36.     QuadNode  *children[4];     //指向节点的四个孩子   
    37. }QuadNode;  
    38.   
    39. /* 四叉树类型结构 */  
    40. typedef struct quadtree_t  
    41. {  
    42.     QuadNode  *root;  
    43.     int         depth;           // 四叉树的深度                      
    44. }QuadTree;  
    45.   
    46.   
    47.     //初始化四叉树节点  
    48.     QuadNode *InitQuadNode();  
    49.   
    50.     //层次创建四叉树方法(满四叉树)  
    51.     void CreateQuadTree(int depth,GeoLayer *poLayer,QuadTree* pQuadTree);  
    52.   
    53.     //创建各个分支  
    54.     void CreateQuadBranch(int depth,MapRect &rect,QuadNode** node);  
    55.   
    56.     //构建四叉树空间索引  
    57.     void BuildQuadTree(GeoLayer*poLayer,QuadTree* pQuadTree);  
    58.   
    59.     //四叉树索引查询(矩形查询)  
    60.     void SearchQuadTree(QuadNode* node,MapRect &queryRect,vector<int>& ItemSearched);  
    61.   
    62.     //四叉树索引查询(矩形查询)并行查询  
    63.     void SearchQuadTreePara(vector<QuadNode*> resNodes,MapRect &queryRect,vector<int>& ItemSearched);  
    64.   
    65.     //四叉树的查询(点查询)  
    66.     void PtSearchQTree(QuadNode* node,double cx,double cy,vector<int>& ItemSearched);  
    67.   
    68.     //将指定的空间对象插入到四叉树中  
    69.     void Insert(long key,MapRect &itemRect,QuadNode* pNode);  
    70.   
    71.     //将指定的空间对象插入到四叉树中  
    72.     void InsertQuad(long key,MapRect &itemRect,QuadNode* pNode);  
    73.   
    74.     //将指定的空间对象插入到四叉树中  
    75.     void InsertQuad2(long key,MapRect &itemRect,QuadNode* pNode);  
    76.   
    77.     //判断一个节点是否是叶子节点  
    78.     bool IsQuadLeaf(QuadNode* node);  
    79.   
    80.     //删除多余的节点  
    81.     bool DelFalseNode(QuadNode* node);  
    82.   
    83.     //四叉树遍历(所有要素)  
    84.     void TraversalQuadTree(QuadNode* quadTree,vector<int>& resVec);  
    85.   
    86.     //四叉树遍历(所有节点)  
    87.     void TraversalQuadTree(QuadNode* quadTree,vector<QuadNode*>& arrNode);  
    88.   
    89.     //释放树的内存空间  
    90.     void ReleaseQuadTree(QuadNode** quadTree);  
    91.   
    92.     //计算四叉树所占的字节的大小  
    93.     long CalByteQuadTree(QuadNode* quadTree,long& nSize);  
    94.   
    95.   
    96. #endif  


    源文件如下:

    1. #include "QuadTree.h"  
    2.   
    3.   
    4. QuadNode *InitQuadNode()  
    5. {  
    6.     QuadNode *node = new QuadNode;  
    7.     node->Box.maxX = 0;  
    8.     node->Box.maxY = 0;  
    9.     node->Box.minX = 0;  
    10.     node->Box.minY = 0;  
    11.   
    12.     for (int i = 0; i < 4; i ++)  
    13.     {  
    14.         node->children[i] = NULL;  
    15.     }  
    16.     node->nChildCount = 0;  
    17.     node->nShpCount = 0;  
    18.     node->pShapeObj = NULL;  
    19.   
    20.     return node;  
    21. }  
    22.   
    23. void CreateQuadTree(int depth,GeoLayer *poLayer,QuadTree* pQuadTree)  
    24. {  
    25.     pQuadTree->depth = depth;  
    26.   
    27.     GeoEnvelope env;    //整个图层的MBR  
    28.     poLayer->GetExtent(&env);  
    29.       
    30.     MapRect rect;  
    31.     rect.minX = env.MinX;  
    32.     rect.minY = env.MinY;  
    33.     rect.maxX = env.MaxX;  
    34.     rect.maxY = env.MaxY;  
    35.       
    36.     //创建各个分支  
    37.     CreateQuadBranch(depth,rect,&(pQuadTree->root));  
    38.   
    39.     int nCount = poLayer->GetFeatureCount();  
    40.     GeoFeature **pFeatureClass = new GeoFeature*[nCount];  
    41.     for (int i = 0; i < poLayer->GetFeatureCount(); i ++)  
    42.     {  
    43.         pFeatureClass[i] = poLayer->GetFeature(i);   
    44.     }  
    45.   
    46.     //插入各个要素  
    47.     GeoEnvelope envObj; //空间对象的MBR  
    48.     //#pragma omp parallel for  
    49.     for (int i = 0; i < nCount; i ++)  
    50.     {  
    51.         pFeatureClass[i]->GetGeometry()->getEnvelope(&envObj);  
    52.         rect.minX = envObj.MinX;  
    53.         rect.minY = envObj.MinY;  
    54.         rect.maxX = envObj.MaxX;  
    55.         rect.maxY = envObj.MaxY;  
    56.         InsertQuad(i,rect,pQuadTree->root);  
    57.     }  
    58.   
    59.     //DelFalseNode(pQuadTree->root);  
    60. }  
    61.   
    62. void CreateQuadBranch(int depth,MapRect &rect,QuadNode** node)  
    63. {  
    64.     if (depth != 0)  
    65.     {  
    66.         *node = InitQuadNode(); //创建树根  
    67.         QuadNode *pNode = *node;  
    68.         pNode->Box = rect;  
    69.         pNode->nChildCount = 4;  
    70.   
    71.         MapRect boxs[4];  
    72.         pNode->Box.Split(boxs,boxs+1,boxs+2,boxs+3);  
    73.         for (int i = 0; i < 4; i ++)  
    74.         {  
    75.             //创建四个节点并插入相应的MBR  
    76.             pNode->children[i] = InitQuadNode();  
    77.             pNode->children[i]->Box = boxs[i];  
    78.   
    79.             CreateQuadBranch(depth-1,boxs[i],&(pNode->children[i]));  
    80.         }  
    81.     }  
    82. }  
    83.   
    84. void BuildQuadTree(GeoLayer *poLayer,QuadTree* pQuadTree)  
    85. {  
    86.     assert(poLayer);  
    87.     GeoEnvelope env;    //整个图层的MBR  
    88.     poLayer->GetExtent(&env);  
    89.     pQuadTree->root = InitQuadNode();  
    90.   
    91.     QuadNode* rootNode = pQuadTree->root;  
    92.   
    93.     rootNode->Box.minX = env.MinX;  
    94.     rootNode->Box.minY = env.MinY;  
    95.     rootNode->Box.maxX = env.MaxX;  
    96.     rootNode->Box.maxY = env.MaxY;  
    97.   
    98.     //设置树的深度(   根据等比数列的求和公式)  
    99.     //pQuadTree->depth = log(poLayer->GetFeatureCount()*3/8.0+1)/log(4.0);  
    100.     int nCount = poLayer->GetFeatureCount();  
    101.   
    102.     MapRect rect;  
    103.     GeoEnvelope envObj; //空间对象的MBR  
    104.     for (int i = 0; i < nCount; i ++)  
    105.     {  
    106.         poLayer->GetFeature(i)->GetGeometry()->getEnvelope(&envObj);  
    107.         rect.minX = envObj.MinX;  
    108.         rect.minY = envObj.MinY;  
    109.         rect.maxX = envObj.MaxX;  
    110.         rect.maxY = envObj.MaxY;  
    111.         InsertQuad2(i,rect,rootNode);  
    112.     }  
    113.   
    114.     DelFalseNode(pQuadTree->root);  
    115. }  
    116.   
    117. void SearchQuadTree(QuadNode* node,MapRect &queryRect,vector<int>& ItemSearched)  
    118. {  
    119.     assert(node);  
    120.   
    121.     //int coreNum = omp_get_num_procs();  
    122.     //vector<int> * pResArr = new vector<int>[coreNum];  
    123.   
    124.     if (NULL != node)  
    125.     {  
    126.         for (int i = 0; i < node->nShpCount; i ++)  
    127.         {  
    128.             if (queryRect.Contains(node->pShapeObj[i].Box)  
    129.                 || queryRect.Intersects(node->pShapeObj[i].Box))  
    130.             {  
    131.                 ItemSearched.push_back(node->pShapeObj[i].nID);  
    132.             }  
    133.         }  
    134.   
    135.         //并行搜索四个孩子节点  
    136.         /*#pragma omp parallel sections 
    137.         { 
    138.             #pragma omp section 
    139.             if ((node->children[0] != NULL) &&  
    140.                 (node->children[0]->Box.Contains(queryRect) 
    141.                 || node->children[0]->Box.Intersects(queryRect))) 
    142.             { 
    143.                 int tid = omp_get_thread_num(); 
    144.                 SearchQuadTree(node->children[0],queryRect,pResArr[tid]); 
    145.             } 
    146.  
    147.             #pragma omp section 
    148.             if ((node->children[1] != NULL) &&  
    149.                 (node->children[1]->Box.Contains(queryRect) 
    150.                 || node->children[1]->Box.Intersects(queryRect))) 
    151.             { 
    152.                 int tid = omp_get_thread_num(); 
    153.                 SearchQuadTree(node->children[1],queryRect,pResArr[tid]); 
    154.             } 
    155.  
    156.             #pragma omp section 
    157.             if ((node->children[2] != NULL) &&  
    158.                 (node->children[2]->Box.Contains(queryRect) 
    159.                 || node->children[2]->Box.Intersects(queryRect))) 
    160.             { 
    161.                 int tid = omp_get_thread_num(); 
    162.                 SearchQuadTree(node->children[2],queryRect,pResArr[tid]); 
    163.             } 
    164.  
    165.             #pragma omp section 
    166.             if ((node->children[3] != NULL) &&  
    167.                 (node->children[3]->Box.Contains(queryRect) 
    168.                 || node->children[3]->Box.Intersects(queryRect))) 
    169.             { 
    170.                 int tid = omp_get_thread_num(); 
    171.                 SearchQuadTree(node->children[3],queryRect,pResArr[tid]); 
    172.             } 
    173.         }*/  
    174.         for (int i = 0; i < 4; i ++)  
    175.         {  
    176.             if ((node->children[i] != NULL) &&   
    177.                 (node->children[i]->Box.Contains(queryRect)  
    178.                 || node->children[i]->Box.Intersects(queryRect)))  
    179.             {  
    180.                 SearchQuadTree(node->children[i],queryRect,ItemSearched);  
    181.                 //node = node->children[i];  //非递归  
    182.             }  
    183.         }  
    184.     }  
    185.   
    186.     /*for (int i = 0 ; i < coreNum; i ++) 
    187.     { 
    188.         ItemSearched.insert(ItemSearched.end(),pResArr[i].begin(),pResArr[i].end()); 
    189.     }*/  
    190.   
    191. }  
    192.   
    193. void SearchQuadTreePara(vector<QuadNode*> resNodes,MapRect &queryRect,vector<int>& ItemSearched)  
    194. {  
    195.     int coreNum = omp_get_num_procs();  
    196.     omp_set_num_threads(coreNum);  
    197.     vector<int>* searchArrs = new vector<int>[coreNum];  
    198.     for (int i = 0; i < coreNum; i ++)  
    199.     {  
    200.         searchArrs[i].clear();  
    201.     }  
    202.   
    203.     #pragma omp parallel for  
    204.     for (int i = 0; i < resNodes.size(); i ++)  
    205.     {  
    206.         int tid = omp_get_thread_num();  
    207.         for (int j = 0; j < resNodes[i]->nShpCount; j ++)  
    208.         {  
    209.             if (queryRect.Contains(resNodes[i]->pShapeObj[j].Box)  
    210.                 || queryRect.Intersects(resNodes[i]->pShapeObj[j].Box))  
    211.             {  
    212.                 searchArrs[tid].push_back(resNodes[i]->pShapeObj[j].nID);  
    213.             }  
    214.         }  
    215.     }  
    216.   
    217.     for (int i = 0; i < coreNum; i ++)  
    218.     {  
    219.         ItemSearched.insert(ItemSearched.end(),  
    220.             searchArrs[i].begin(),searchArrs[i].end());  
    221.     }  
    222.   
    223.     delete [] searchArrs;  
    224.     searchArrs = NULL;  
    225. }  
    226.   
    227. void PtSearchQTree(QuadNode* node,double cx,double cy,vector<int>& ItemSearched)  
    228. {  
    229.     assert(node);  
    230.     if (node->nShpCount >0)       //节点            
    231.     {  
    232.         for (int i = 0; i < node->nShpCount; i ++)  
    233.         {  
    234.             if (node->pShapeObj[i].Box.IsPointInRect(cx,cy))  
    235.             {  
    236.                 ItemSearched.push_back(node->pShapeObj[i].nID);  
    237.             }  
    238.         }  
    239.     }  
    240.   
    241.     else if (node->nChildCount >0)                //节点  
    242.     {  
    243.         for (int i = 0; i < 4; i ++)  
    244.         {  
    245.             if (node->children[i]->Box.IsPointInRect(cx,cy))  
    246.             {  
    247.                 PtSearchQTree(node->children[i],cx,cy,ItemSearched);  
    248.             }  
    249.         }  
    250.     }  
    251.   
    252.     //找出重复元素的位置  
    253.     sort(ItemSearched.begin(),ItemSearched.end());  //先排序,默认升序  
    254.     vector<int>::iterator unique_iter =   
    255.         unique(ItemSearched.begin(),ItemSearched.end());  
    256.     ItemSearched.erase(unique_iter,ItemSearched.end());  
    257. }  
    258.   
    259. void Insert(long key, MapRect &itemRect,QuadNode* pNode)  
    260. {  
    261.     QuadNode *node = pNode;     //保留根节点副本  
    262.     SHPMBRInfo pShpInfo;  
    263.       
    264.     //节点有孩子  
    265.     if (0 < node->nChildCount)  
    266.     {  
    267.         for (int i = 0; i < 4; i ++)  
    268.         {    
    269.             //如果包含或相交,则将节点插入到此节点  
    270.             if (node->children[i]->Box.Contains(itemRect)  
    271.                 || node->children[i]->Box.Intersects(itemRect))  
    272.             {  
    273.                 //node = node->children[i];  
    274.                 Insert(key,itemRect,node->children[i]);  
    275.             }  
    276.         }  
    277.     }  
    278.   
    279.     //如果当前节点存在一个子节点时  
    280.     else if (1 == node->nShpCount)  
    281.     {  
    282.         MapRect boxs[4];  
    283.         node->Box.Split(boxs,boxs+1,boxs+2,boxs+3);  
    284.   
    285.         //创建四个节点并插入相应的MBR  
    286.         node->children[UR] = InitQuadNode();  
    287.         node->children[UL] = InitQuadNode();  
    288.         node->children[LL] = InitQuadNode();  
    289.         node->children[LR] = InitQuadNode();  
    290.   
    291.         node->children[UR]->Box = boxs[0];  
    292.         node->children[UL]->Box = boxs[1];  
    293.         node->children[LL]->Box = boxs[2];  
    294.         node->children[LR]->Box = boxs[3];  
    295.         node->nChildCount = 4;  
    296.   
    297.         for (int i = 0; i < 4; i ++)  
    298.         {    
    299.             //将当前节点中的要素移动到相应的子节点中  
    300.             for (int j = 0; j < node->nShpCount; j ++)  
    301.             {  
    302.                 if (node->children[i]->Box.Contains(node->pShapeObj[j].Box)  
    303.                     || node->children[i]->Box.Intersects(node->pShapeObj[j].Box))  
    304.                 {  
    305.                     node->children[i]->nShpCount += 1;  
    306.                     node->children[i]->pShapeObj =   
    307.                         (SHPMBRInfo*)malloc(node->children[i]->nShpCount*sizeof(SHPMBRInfo));  
    308.                       
    309.                     memcpy(node->children[i]->pShapeObj,&(node->pShapeObj[j]),sizeof(SHPMBRInfo));  
    310.   
    311.                     free(node->pShapeObj);  
    312.                     node->pShapeObj = NULL;  
    313.                     node->nShpCount = 0;  
    314.                 }  
    315.             }  
    316.         }  
    317.   
    318.         for (int i = 0; i < 4; i ++)  
    319.         {    
    320.             //如果包含或相交,则将节点插入到此节点  
    321.             if (node->children[i]->Box.Contains(itemRect)  
    322.                 || node->children[i]->Box.Intersects(itemRect))  
    323.             {  
    324.                 if (node->children[i]->nShpCount == 0)     //如果之前没有节点  
    325.                 {  
    326.                     node->children[i]->nShpCount += 1;  
    327.                     node->pShapeObj =   
    328.                         (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->children[i]->nShpCount);  
    329.                 }  
    330.                 else if (node->children[i]->nShpCount > 0)  
    331.                 {  
    332.                     node->children[i]->nShpCount += 1;  
    333.                     node->children[i]->pShapeObj =   
    334.                         (SHPMBRInfo *)realloc(node->children[i]->pShapeObj,  
    335.                         sizeof(SHPMBRInfo)*node->children[i]->nShpCount);  
    336.                 }  
    337.   
    338.                 pShpInfo.Box = itemRect;  
    339.                 pShpInfo.nID = key;  
    340.                 memcpy(node->children[i]->pShapeObj,  
    341.                     &pShpInfo,sizeof(SHPMBRInfo));  
    342.             }  
    343.         }  
    344.     }  
    345.   
    346.     //当前节点没有空间对象  
    347.     else if (0 == node->nShpCount)  
    348.     {  
    349.         node->nShpCount += 1;  
    350.         node->pShapeObj =   
    351.             (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);  
    352.   
    353.         pShpInfo.Box = itemRect;  
    354.         pShpInfo.nID = key;  
    355.         memcpy(node->pShapeObj,&pShpInfo,sizeof(SHPMBRInfo));  
    356.     }  
    357. }  
    358.   
    359. void InsertQuad(long key,MapRect &itemRect,QuadNode* pNode)  
    360. {  
    361.     assert(pNode != NULL);  
    362.   
    363.     if (!IsQuadLeaf(pNode))    //非叶子节点  
    364.     {  
    365.         int nCorver = 0;        //跨越的子节点个数  
    366.         int iIndex = -1;        //被哪个子节点完全包含的索引号  
    367.         for (int i = 0; i < 4; i ++)  
    368.         {  
    369.             if (pNode->children[i]->Box.Contains(itemRect)  
    370.                 && pNode->Box.Contains(itemRect))  
    371.             {  
    372.                 nCorver += 1;  
    373.                 iIndex = i;  
    374.             }  
    375.         }  
    376.   
    377.         //如果被某一个子节点包含,则进入该子节点  
    378.         if (/*pNode->Box.Contains(itemRect) ||  
    379.             pNode->Box.Intersects(itemRect)*/1 <= nCorver)  
    380.         {   
    381.             InsertQuad(key,itemRect,pNode->children[iIndex]);  
    382.         }  
    383.   
    384.         //如果跨越了多个子节点,直接放在这个节点中  
    385.         else if (nCorver == 0)  
    386.         {  
    387.             if (pNode->nShpCount == 0)    //如果之前没有节点  
    388.             {  
    389.                 pNode->nShpCount += 1;  
    390.                 pNode->pShapeObj =   
    391.                     (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*pNode->nShpCount);  
    392.             }  
    393.             else  
    394.             {  
    395.                 pNode->nShpCount += 1;  
    396.                 pNode->pShapeObj =   
    397.                     (SHPMBRInfo *)realloc(pNode->pShapeObj,sizeof(SHPMBRInfo)*pNode->nShpCount);  
    398.             }  
    399.   
    400.             SHPMBRInfo pShpInfo;  
    401.             pShpInfo.Box = itemRect;  
    402.             pShpInfo.nID = key;  
    403.             memcpy(pNode->pShapeObj+pNode->nShpCount-1,&pShpInfo,sizeof(SHPMBRInfo));  
    404.         }  
    405.     }  
    406.   
    407.     //如果是叶子节点,直接放进去  
    408.     else if (IsQuadLeaf(pNode))  
    409.     {  
    410.         if (pNode->nShpCount == 0)    //如果之前没有节点  
    411.         {  
    412.             pNode->nShpCount += 1;  
    413.             pNode->pShapeObj =   
    414.                 (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*pNode->nShpCount);  
    415.         }  
    416.         else  
    417.         {  
    418.             pNode->nShpCount += 1;  
    419.             pNode->pShapeObj =   
    420.                 (SHPMBRInfo *)realloc(pNode->pShapeObj,sizeof(SHPMBRInfo)*pNode->nShpCount);  
    421.         }  
    422.   
    423.         SHPMBRInfo pShpInfo;  
    424.         pShpInfo.Box = itemRect;  
    425.         pShpInfo.nID = key;  
    426.         memcpy(pNode->pShapeObj+pNode->nShpCount-1,&pShpInfo,sizeof(SHPMBRInfo));  
    427.     }  
    428. }  
    429.   
    430. void InsertQuad2(long key,MapRect &itemRect,QuadNode* pNode)  
    431. {  
    432.     QuadNode *node = pNode;     //保留根节点副本  
    433.     SHPMBRInfo pShpInfo;  
    434.   
    435.     //节点有孩子  
    436.     if (0 < node->nChildCount)  
    437.     {  
    438.         for (int i = 0; i < 4; i ++)  
    439.         {    
    440.             //如果包含或相交,则将节点插入到此节点  
    441.             if (node->children[i]->Box.Contains(itemRect)  
    442.                 || node->children[i]->Box.Intersects(itemRect))  
    443.             {  
    444.                 //node = node->children[i];  
    445.                 Insert(key,itemRect,node->children[i]);  
    446.             }  
    447.         }  
    448.     }  
    449.   
    450.     //如果当前节点存在一个子节点时  
    451.     else if (0 == node->nChildCount)  
    452.     {  
    453.         MapRect boxs[4];  
    454.         node->Box.Split(boxs,boxs+1,boxs+2,boxs+3);  
    455.   
    456.         int cnt = -1;  
    457.         for (int i = 0; i < 4; i ++)  
    458.         {    
    459.             //如果包含或相交,则将节点插入到此节点  
    460.             if (boxs[i].Contains(itemRect))  
    461.             {  
    462.                 cnt = i;  
    463.             }  
    464.         }  
    465.   
    466.         //如果有一个矩形包含此对象,则创建四个孩子节点  
    467.         if (cnt > -1)  
    468.         {  
    469.             for (int i = 0; i < 4; i ++)  
    470.             {  
    471.                 //创建四个节点并插入相应的MBR  
    472.                 node->children[i] = InitQuadNode();  
    473.                 node->children[i]->Box = boxs[i];  
    474.             }  
    475.             node->nChildCount = 4;  
    476.             InsertQuad2(key,itemRect,node->children[cnt]);   //递归  
    477.         }  
    478.   
    479.         //如果都不包含,则直接将对象插入此节点  
    480.         if (cnt == -1)  
    481.         {  
    482.             if (node->nShpCount == 0)     //如果之前没有节点  
    483.             {  
    484.                 node->nShpCount += 1;  
    485.                 node->pShapeObj =   
    486.                     (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);  
    487.             }  
    488.             else if (node->nShpCount > 0)  
    489.             {  
    490.                 node->nShpCount += 1;  
    491.                 node->pShapeObj =   
    492.                     (SHPMBRInfo *)realloc(node->pShapeObj,  
    493.                     sizeof(SHPMBRInfo)*node->nShpCount);  
    494.             }  
    495.   
    496.             pShpInfo.Box = itemRect;  
    497.             pShpInfo.nID = key;  
    498.             memcpy(node->pShapeObj,  
    499.                 &pShpInfo,sizeof(SHPMBRInfo));  
    500.         }  
    501.     }  
    502.   
    503.     //当前节点没有空间对象  
    504.     /*else if (0 == node->nShpCount) 
    505.     { 
    506.         node->nShpCount += 1; 
    507.         node->pShapeObj =  
    508.             (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount); 
    509.  
    510.         pShpInfo.Box = itemRect; 
    511.         pShpInfo.nID = key; 
    512.         memcpy(node->pShapeObj,&pShpInfo,sizeof(SHPMBRInfo)); 
    513.     }*/  
    514. }  
    515.   
    516. bool IsQuadLeaf(QuadNode* node)  
    517. {  
    518.     if (NULL == node)  
    519.     {  
    520.         return 1;  
    521.     }  
    522.     for (int i = 0; i < 4; i ++)  
    523.     {  
    524.         if (node->children[i] != NULL)  
    525.         {  
    526.             return 0;  
    527.         }  
    528.     }  
    529.   
    530.     return 1;  
    531. }  
    532.   
    533. bool DelFalseNode(QuadNode* node)  
    534. {  
    535.     //如果没有子节点且没有要素  
    536.     if (node->nChildCount ==0 && node->nShpCount == 0)  
    537.     {  
    538.         ReleaseQuadTree(&node);  
    539.     }  
    540.   
    541.     //如果有子节点  
    542.     else if (node->nChildCount > 0)  
    543.     {  
    544.         for (int i = 0; i < 4; i ++)  
    545.         {  
    546.             DelFalseNode(node->children[i]);  
    547.         }  
    548.     }  
    549.   
    550.     return 1;  
    551. }  
    552.   
    553. void TraversalQuadTree(QuadNode* quadTree,vector<int>& resVec)  
    554. {  
    555.     QuadNode *node = quadTree;  
    556.     int i = 0;   
    557.     if (NULL != node)  
    558.     {  
    559.         //将本节点中的空间对象存储数组中  
    560.         for (i = 0; i < node->nShpCount; i ++)  
    561.         {  
    562.             resVec.push_back((node->pShapeObj+i)->nID);  
    563.         }  
    564.   
    565.         //遍历孩子节点  
    566.         for (i = 0; i < node->nChildCount; i ++)  
    567.         {  
    568.             if (node->children[i] != NULL)  
    569.             {  
    570.                 TraversalQuadTree(node->children[i],resVec);  
    571.             }  
    572.         }  
    573.     }  
    574.   
    575. }  
    576.   
    577. void TraversalQuadTree(QuadNode* quadTree,vector<QuadNode*>& arrNode)  
    578. {  
    579.     deque<QuadNode*> nodeQueue;  
    580.     if (quadTree != NULL)  
    581.     {  
    582.         nodeQueue.push_back(quadTree);  
    583.         while (!nodeQueue.empty())  
    584.         {  
    585.             QuadNode* queueHead = nodeQueue.at(0);  //取队列头结点  
    586.             arrNode.push_back(queueHead);  
    587.             nodeQueue.pop_front();  
    588.             for (int i = 0; i < 4; i ++)  
    589.             {  
    590.                 if (queueHead->children[i] != NULL)  
    591.                 {  
    592.                     nodeQueue.push_back(queueHead->children[i]);  
    593.                 }  
    594.             }  
    595.         }  
    596.     }  
    597. }  
    598.   
    599. void ReleaseQuadTree(QuadNode** quadTree)  
    600. {  
    601.     int i = 0;  
    602.     QuadNode* node = *quadTree;  
    603.     if (NULL == node)  
    604.     {  
    605.         return;  
    606.     }  
    607.   
    608.     else  
    609.     {  
    610.         for (i = 0; i < 4; i ++)  
    611.         {   
    612.             ReleaseQuadTree(&node->children[i]);  
    613.         }  
    614.         free(node);  
    615.         node = NULL;  
    616.     }  
    617.   
    618.     node = NULL;  
    619. }  
    620.   
    621. long CalByteQuadTree(QuadNode* quadTree,long& nSize)  
    622. {  
    623.     if (quadTree != NULL)  
    624.     {  
    625.         nSize += sizeof(QuadNode)+quadTree->nChildCount*sizeof(SHPMBRInfo);  
    626.         for (int i = 0; i < 4; i ++)  
    627.         {  
    628.             if (quadTree->children[i] != NULL)  
    629.             {  
    630.                 nSize += CalByteQuadTree(quadTree->children[i],nSize);  
    631.             }  
    632.         }  
    633.     }  
    634.   
    635.     return 1;  
    636. }  
    展开全文
  • 四叉树数据结构 四叉树数据结构 常规四叉树 线性四叉树 1 四叉树分割的基本思想 k k 把一副图像或一副栅格地图2 x2 ,k>1等分成四部分逐 块检查其格网值 如果某个子区的所有格网都含有相 2 3 1 同的值则子区不再分割 ...
  • 第2章GIS数据结构.ppt

    2020-03-11 15:44:04
    属性+游程长度 属性+终止列号 4四叉树将图象按四个...自下而上bottomup逐层集化 要点按下图所示顺序检测各个网格如4个网格值相同则合并反之作为四个叶结点记录依次逐层向上直到根结点 四叉树存储方法 常规四叉树 存储6
  • 游戏算法

    2014-04-13 20:27:00
    四叉树算法 四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,如此...常规四叉树的结构如图所示,地理空间对象都存储在叶子节点上,中间节点以及根节点...

    四叉树算法

         四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,如此递归下去,直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的空间数据插入和查询效率,因此四叉树是GIS中常用的空间索引之一。常规四叉树的结构如图所示,地理空间对象都存储在叶子节点上,中间节点以及根节点不存储地理空间对象。

     

    游戏状态机

        有限状态机是一种用来进行对象行为建模的工具,其作用主要是描述对象在它的生命周期内所经历的状态序列,以及如何响应来自外界的各种事件

        有限状态机元素:
         1. 状态,用来定义行为以及可能产生动作
         2. 状态转换,从一种状态到另一种状态的转移
         3. 规则或条件,必须以此来允许状态转换
         4. 输入事件,由外部或内部产生的,可能触发规则并导致状态变换

        结合模糊逻辑和有限状态机,就产生了模糊状态机。模糊状态机中,单位不是绝对的处于某种状态,而是同时处于几种状态,只是每种状态的比重不同

     

    Dijkstra算法

        假设有两个集合或者说两个表,表A和表B
        表A表示生成路径,表B表示最后确定的路径
        1.从原点出发,遍历检查所有与之相连的节点,将原点和这些节点存放到表A中,并记录下两节点之间的代价。
        2.将代价最小的代价值和这两节点移动到表B中(其中一个是原点)。
        3.把这个节点所连接的子节点找出,放入到表A中,算出子节点到原点的代价
        4.重复第二步和第三步直到表A为空。然后根据表B中的数据算出最优树。

     

    a*算法

         A*算法最为核心的部分,就在于它的一个估值函数的设计上:f(n)=g(n)+h(n)

          其中f(n)是每个可能试探点的估值,它有两部分组成:
              一部分,为g(n),它表示从起始搜索点到当前点的代价(通常用某结点在搜索树中的深度来表示)。
               另一部分,即h(n),它表示启发式搜索中最为重要的一部分,即当前结点到目标结点的估值,
         h(n)设计的好坏,直接影响着具有此种启发式函数的启发式算法的是否能称为A*算法。

              A*算法与和Dijkstra 算法的联系就在于:当g(n)=0时,该算法类似于DFS,当h(n)=0时,该算法类似于BFS, 如果h(n)为0,只需求出g(n),即求出起点到任意顶点n的最短路径,则转化Dijkstra算法

    转载于:https://www.cnblogs.com/kangbry/p/3662698.html

    展开全文
  • [GIS原理] 4.2 栅格数据结构

    千次阅读 2018-11-22 21:43:50
    文章目录栅格数据结构完全栅格数据结构多通道/多波段影像完全数据结构压缩栅格数据结构四叉树数据结构常规四叉树线性四叉树(MD码)链码结构影像金字塔数据结构 栅格数据结构 点:为一个像元 线:在一定方向上...
  • FatTree胖拓扑结构

    万次阅读 2018-04-19 10:13:18
    FatTree拓扑结构是由MIT的Fares等人在改进传统形结构性能的基础上提出的,属于switch-only型拓扑。 整个拓扑网络分为三个层次:自上而下分别为边缘层(edge)、汇聚层(aggregate...图3 四叉 图3 六叉胖...
  • 地理信息系统算法基础

    千次下载 热门讨论 2009-06-20 10:57:53
    7.3.1常规四叉树 7.3.2线性四叉树 7.3.3线性四叉树的编码 7.3.4Z曲线和Hibert曲线算法 思考题 第8章空间数据内插算法 8.1概述 8.1.1几何方法 8.1.2统计方法 8.1.3空间统计方法 8.1.4函数方法 ...
  • FatTree拓扑结构是由MIT的Fares等人在改进传统形结构性能的基础上提出的,属于switch-only型拓扑。 整个拓扑网络分为三个层次:自上而下分别为边缘层(edge)、汇聚层...图3 四叉 图3 六叉胖 ...
  • arpg页游出售 完成度60% 现由于特殊原因低价出售arpg前端页游源码,整个游戏架构,现已经完成场景,战斗...四叉树优化!  内存SO管理!对象池管理! 保证内存在300M 以内 同屏 600人 30帧频! 无压力! 1000人
  • Postgresql SP-Gist索引

    2020-03-03 09:50:05
    SP-Gist SP-Gist和Gist类似, ...此类包括四叉树,k维树(k-D树)和基数树。 结构介绍 SP-GiST的思想是将值域拆分为非重叠的子域,每个子域又可以拆分。像这样的分区会生成不平衡的树(不像B树和常规的GiST)。...
  • FatTree拓扑结构

    2018-08-07 11:34:00
    FatTree拓扑结构是由MIT的Fares等人在改进传统形结构性能的基础上提出的,属于switch-only型拓扑。 整个拓扑网络分为三个层次:自上而下分别为边缘层(edge)、汇聚层...图3 四叉 图3 六叉胖 ...

空空如也

空空如也

1 2
收藏数 33
精华内容 13
关键字:

常规四叉树