当前位置:   article > 正文

四叉树空间索引原理及其实现

四叉树空间索引

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

四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,如此递归下去,直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的空间数据插入和查询效率,因此四叉树是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. UL(1) | UR(0)
  5. ----------|-----------
  6. LL(2) | LR(3)
  7. 以下对该象限类型的枚举
  8. */
  9. typedef enum
  10. {
  11. UR = 0,
  12. UL = 1,
  13. LL = 2,
  14. LR = 3
  15. }QuadrantEnum;
  16. /*空间对象MBR信息*/
  17. typedef struct SHPMBRInfo
  18. {
  19. int nID; //空间对象ID号
  20. MapRect Box; //空间对象MBR范围坐标
  21. }SHPMBRInfo;
  22. /* 四叉树节点类型结构 */
  23. typedef struct QuadNode
  24. {
  25. MapRect Box; //节点所代表的矩形区域
  26. int nShpCount; //节点所包含的所有空间对象个数
  27. SHPMBRInfo* pShapeObj; //空间对象指针数组
  28. int nChildCount; //子节点个数
  29. QuadNode *children[4]; //指向节点的四个孩子
  30. }QuadNode;
  31. /* 四叉树类型结构 */
  32. typedef struct quadtree_t
  33. {
  34. QuadNode *root;
  35. int depth; // 四叉树的深度
  36. }QuadTree;
  37. //初始化四叉树节点
  38. QuadNode *InitQuadNode();
  39. //层次创建四叉树方法(满四叉树)
  40. void CreateQuadTree(int depth,GeoLayer *poLayer,QuadTree* pQuadTree);
  41. //创建各个分支
  42. void CreateQuadBranch(int depth,MapRect &rect,QuadNode** node);
  43. //构建四叉树空间索引
  44. void BuildQuadTree(GeoLayer*poLayer,QuadTree* pQuadTree);
  45. //四叉树索引查询(矩形查询)
  46. void SearchQuadTree(QuadNode* node,MapRect &queryRect,vector<int>& ItemSearched);
  47. //四叉树索引查询(矩形查询)并行查询
  48. void SearchQuadTreePara(vector<QuadNode*> resNodes,MapRect &queryRect,vector<int>& ItemSearched);
  49. //四叉树的查询(点查询)
  50. void PtSearchQTree(QuadNode* node,double cx,double cy,vector<int>& ItemSearched);
  51. //将指定的空间对象插入到四叉树中
  52. void Insert(long key,MapRect &itemRect,QuadNode* pNode);
  53. //将指定的空间对象插入到四叉树中
  54. void InsertQuad(long key,MapRect &itemRect,QuadNode* pNode);
  55. //将指定的空间对象插入到四叉树中
  56. void InsertQuad2(long key,MapRect &itemRect,QuadNode* pNode);
  57. //判断一个节点是否是叶子节点
  58. bool IsQuadLeaf(QuadNode* node);
  59. //删除多余的节点
  60. bool DelFalseNode(QuadNode* node);
  61. //四叉树遍历(所有要素)
  62. void TraversalQuadTree(QuadNode* quadTree,vector<int>& resVec);
  63. //四叉树遍历(所有节点)
  64. void TraversalQuadTree(QuadNode* quadTree,vector<QuadNode*>& arrNode);
  65. //释放树的内存空间
  66. void ReleaseQuadTree(QuadNode** quadTree);
  67. //计算四叉树所占的字节的大小
  68. long CalByteQuadTree(QuadNode* quadTree,long& nSize);
  69. #endif


源文件如下:

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


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

 

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/在线问答5/article/detail/768947
推荐阅读
相关标签
  

闽ICP备14008679号