四叉树_四叉树结构 - CSDN
精华内容
参与话题
  • 今天依然在放假中,在此将以前在学校写的四叉树的东西拿出来和大家分享。 四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,如此递归下去,直至树的层次...

    转自http://blog.csdn.net/zhouxuguang236/article/details/12312099

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

    四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,如此递归下去,直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的空间数据插入和查询效率,因此四叉树是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. }  

    展开全文
  • 四叉树——图片应用实例

    千次阅读 2019-06-19 21:51:07
    四叉树前言应用实例 前言 四元树又称四叉树是一种树状数据结构,在每一个节点上会有四个子区块。四元树常应用于二维空间数据的分析与分类。 它将数据区分成为四个象限。数据范围可以是方形或矩形或其他任意形状。 ...

    前言

    四元树又称四叉树是一种树状数据结构,在每一个节点上会有四个子区块。四元树常应用于二维空间数据的分析与分类。 它将数据区分成为四个象限。数据范围可以是方形或矩形或其他任意形状。
    这种数据结构是由 拉斐尔·芬科尔(Raphael Finkel) 与 J. L. Bentley 在1974年发展出来 。

    应用实例

    四叉树索引结构可以快速的在二维空间划分数据 ,下面是一张图片的四叉树结构实例代码,根据图片中心划分,拥有非1:1图片的自适应性

    tree.h

    class Node {
    public:
        PNG *p; //the upper left pixel
        Node **children; //pointer to four other node
        int width; //当前像素区块的宽度
        int height; //当前像素区块的高度
        bool leaf; //是否是叶子节点,true 代表是叶子节点
        int x; //当前像素区块左上角顶点像素的横坐标
        int y; //当前像素区块左上角顶点像素的纵坐标
        int mean_r; //Rmean
        int mean_g; //Gmean
        int mean_b; //Bmean
    public:
    	int count;
        Node();
        Node(PNG* corner, int input_width, int input_height, int x, int y);
        Node(Node &other);
        Node(Node &&other);
        Node& operator=(Node &other);
        Node& operator=(Node &&other);
        ~Node();
        void print();
        pxl *get_pxl();
    };
    
    
    class Tree {
    public:
        Node *root; //根结点
    public:
        Tree();
        ~Tree();
        Tree(Tree &other);
        Tree& operator=(Tree &other);
        void judge(int threshold);
        pxl *get_pxl();
        void load_png(PNG *png);
    	int internal_judge(Node* n);
    	void internal_build(Node* n);
        void print();
    };
    

    tree.cpp

    Node::Node() {
        //TODO
    	mean_r = 0;
    	mean_g = 0;
    	mean_b = 0;
    
    	p = nullptr;
    	width = 0;
    	height = 0;
    	x = 0;
    	y = 0;
    
    	count = 0;
    
    	leaf = true;
    	children = nullptr;
    }
    
    Node::Node(PNG* corner, int input_width, int input_height, int x, int y) {
        //TODO
    	count = 0;
    	children = new Node*[4];
    	children[0] = nullptr;
    	children[1] = nullptr;
    	children[2] = nullptr;
    	children[3] = nullptr;
    
    	mean_r = 0;
    	mean_g = 0;
    	mean_b = 0;
    
    	if (input_width <= 0 || input_height <= 0) {
    		p = nullptr;
    		leaf = true;
    		return;
    	}
    	p = corner;
    	width = input_width;
    	height = input_height;
    	this->x = x;
    	this->y = y;
    
    	if (input_width == 1 && input_height == 1) {
    		leaf = true;
    		mean_r = corner->get_pxl(x, y)->red;
    		mean_g = corner->get_pxl(x, y)->green;
    		mean_b = corner->get_pxl(x, y)->blue;
    	}
    	else {
    		leaf = false;
    		
    	}
    }
    
    
    void Tree::internal_build(Node* n) {
    
    
    	int hw = n->width >> 1;
    	int hh = n->height >> 1;
    
    	int x = n->x;
    	int y = n->y;
    
    	if (hw > 0 && hh > 0) {
    		n->children[0] = new Node(n->p, hw, hh, x, y);
    
    		if (!n->children[0]->leaf)
    			internal_build(n->children[0]);
    	}
    	if ((n->width - hw) > 0 && hh > 0) {
    		n->children[1] = new Node(n->p, n->width - hw, hh, x + hw, y);
    
    		if (!n->children[1]->leaf)
    			internal_build(n->children[1]);
    	}
    	if (hw > 0 && (n->height) > 0) {
    		n->children[2] = new Node(n->p, hw, n->height - hh, x, hh + y);
    
    		if (!n->children[2]->leaf)
    			internal_build(n->children[2]);
    	}
    	if ((n->width - hw) > 0 && (n->height - hh) > 0) {
    		n->children[3] = new Node(n->p, n->width - hw, n->height - hh, x + hw, hh + y);
    
    		if (!n->children[3]->leaf)
    			internal_build(n->children[3]);
    	}
    
    
    
    	int c = 0;
    
    	for (int i = 0; i < 4; ++i) {
    		if (n->children[i]) {
    			++c;
    			n->mean_r += n->children[i]->mean_r;
    			n->mean_g += n->children[i]->mean_g;
    			n->mean_b += n->children[i]->mean_b;
    		}
    	}
    	n->mean_r /= c;
    	n->mean_g /= c;
    	n->mean_b /= c;
    }
    
    void Tree::load_png(PNG *png) {
        //TODO
    	
    	root = new Node(png, png->get_width(), png->get_height(), 0, 0);
    
    	if (!root->leaf) {
    		internal_build(root);
    	}
    	
    }
    

    其中
    void Tree::load_png(PNG png)为根据图片指针创建四叉树函数。
    void Tree::internal_build(Node
    n)为递归创建四叉树的函数

    展开全文
  • 四叉树Quadtrees在游戏领域应用

    千次阅读 2018-06-24 11:54:57
    孙广东 2018.6.24 维基百科介绍: 四元树又称四叉树是一种树状数据结构,在每一个节点上会有四个子区块。四元树常应用于二维空间数据的分析与分类。 它将数据区分成为四个象限。数据范围可以是方形或矩形或其他...

    孙广东   2018.6.24

        维基百科介绍:

          四元树又称四叉树是一种树状数据结构,在每一个节点上会有四个子区块。四元树常应用于二维空间数据的分析与分类。 它将数据区分成为四个象限。数据范围可以是方形或矩形或其他任意形状。

    所有的四元树法有共同之特点:

    • 可分解成为各自的区块
    • 每个区块都有节点容量。当节点达到最大容量时,节点分裂
    • 树状数据结构依造四元树法加以区分

    一些四元树的常用法


    四叉树来源于将正方形区域分成较小正方形的想法。所以他的应用倾向于 2D搜索或优化算法


    当你沿着四叉树向下移动时,每个正方形被分成四个较小的正方形。

    换一种角度在来看。 通过绘制显示每个节点的子节点的线条,  如果你专注于黑色线条,你可以看到它们形成了一个分支树状结构,每层都有四个分支。


    我们可以使树的视图更加抽象,更接近我们用来表示它的数据结构,方法是将图的树部分展平成二维树图。


    现在你可以看到四叉树作为一个数据结构并不是很特别 - 它只是一棵树,每个节点有四个子节点。


    参考 js 版本 的   

     https://github.com/CodingTrain/QuadTree  ,   移植到 Unity中   
    

    https://download.csdn.net/download/u010019717/10495980  


    参考文章

    HTML5实现3D和2D可视化QuadTree四叉树碰撞检测

    [译]2D空间中使用四叉树Quadtree进行碰撞检测优化

    Quadtree and Octree Culling Alternative          四叉树和八叉树剔除



    展开全文
  • 四叉树是干什么的?

    2020-06-19 14:34:56
    四元树又称四叉树是一种树状数据结构,在每一个节点上会有四个子区块。四元树常应用于二维空间数据的分析与分类。 它将数据区分成为四个象限。数据范围可以是方形或矩形或其他任意形状。 从定义我们可以看出重点信息...

    四元树又称四叉树是一种树状数据结构,在每一个节点上会有四个子区块。四元树常应用于二维空间数据的分析与分类。 它将数据区分成为四个象限。数据范围可以是方形或矩形或其他任意形状。
    从定义我们可以看出重点信息:

    树状结构
    四个区块
    分类
    矩形
    图示讲解
    讲解之前需要先说明一下四叉树是用来做什么的,明白了原理才好理解它的行为。
    使用四叉树就是使用分类的方法,减少碰撞节点的个数,只取出与给定碰撞体相同区域或者压在碰撞体所在区域边上的对象。

    将游戏屏幕分为四个区域。

    插入对象

    插入的对象超过了我们设置的阈值时,划分

    插入的对象再次超过了我们设置的阈值时,继续分。

    分析
    插入
    从上面的图示我们可以很好理解四叉树的原理。涉及的都是插入操作。
    那么插入操作具体都做了什么呢?

    从代码中我们可以看出:

    当插入第一个对象的时候只走了2;这个时候没有子树,所以不会走1,因为objects(管理的对象)的长度还没有超过我们设置的阈值MAX_OBJECTS,所以也不会走3。
    一直插入,当objects中的数量,超过了我们设置的阈值MAX_OBJECT,就会开始划分,产生子树,有了nodes,划分之后将自己管理的节点插入到子树中。再此之前,都不会走1,因为还没有产生子树。
    划分之后再次插入新对象,如果对象可以获得对应的象限,就会走1 不会走2和3,如果没有获得对应的象限才会走2,3(没有获得的情况可能是你创建的对象在屏幕外,游戏中很多情况是敌人从屏幕外走进屏幕的,具体可参考我做的《星际迷航》或者《星际战》游戏)。
    更新对象

    我是把四插入作为了对象管理器使用,要不然对象也需要更新,所以有了这一步操作。如果不这样你需要自己创建对象管理器,一个一个放进去,删除。通过四叉树直接管理省了不少事情。

    更新象限信息。
    这是一个递归操作,更新象限做的事情比较多了。

    检查对象是否存活,如果死亡就回收,我这里使用了对象池,所以对象实现了poolAble接口。

    判断对象的所占区域是否在四叉树的区域内
    这里需要说明的是一个四叉树本身的区域是它管理的四个象限这么大。也就是一个四叉树管理四个象限

    不在管理区域的话需要判断当前this是否为根节点,如果是说明对象已经出屏了。(这个时候可以通过对象实现的isVisible接口来控制是否回收,因为不是所有在屏幕外的都要回收,比如要进入屏幕的敌人,是不可能回收的,所以需要自己用isVisible接口来控制)。如果不是就将对象放入根节点,重新划分。

    在管理区域内,就看看在四叉树管理的哪个象限里。更新象限信息。

    如果没有变化什么都不过,如果有变化,先判断象限是否为-1,为什么会出现-1,也就是不在四个象限的任何一个象限?因为压线了。此番操作后的结果如下图。

    根据给定矩形获取对象列表

    第一个是步长,用于获取深度,当然深度越长,处理的时间越长,获取的对象也精细。这个可以根据自己游戏的同屏四叉树层级而定了。
    如果通过obj的rect获得对象所在象限如果获得了对应的象限,用获得的象限的四叉树再获取。如果压线的话就需要将碰撞的两个象限的内容都取出来。
    返回四叉树中没有分割象限的对象。
    怎么用呢?

    自然就是把要碰撞的对象传给retrieve函数获得需要碰撞的对象列表进行碰撞检测了。
    也就是文章靠头说的:
    使用四叉树就目的是为了减少碰撞节点的个数。使用的是分类的方法。
    至于用什么样的碰撞检测函数,不是四叉树关心的事情,

    至于用几个四叉树管理对象,也不是四叉树关心的事情。

    结语
    想要demo的同学可以去我的微店或者官方creator商城购买《跨引擎游戏框架》源码,跟demo是一个项目。买过的同学请加我好友,群已经建好,有更新我会群里直接发包。

    展开全文
  • 四叉树与八叉树

    万次阅读 多人点赞 2011-09-05 23:36:57
    前序 四叉树或四元树也被称为Q树(Q-Tree)。四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等,而...本文着重于对四叉树与八叉树的原理与结构的介绍,帮助您在脑海中建立四叉树与八叉树
  • 四叉树处理图像

    2020-07-30 23:31:50
    在matlab中采用四叉树算法对读取的二进制文件进行分割,去除NaN值之后对矩阵进行渲染绘图。
  • 四叉树

    千次阅读 2018-06-07 00:04:52
    1.由二维空间图像得到其压缩编码 传送门 //建树加遍历 int p[1025][1025]; int node[1025*1025]; int build(int k,int lx,int ly,int rx,int ry) { if(lx==rx&amp;amp;&amp;... ...
  • 四叉树的C++实现

    千次阅读 2020-01-18 13:04:45
    数据结构 抽象数据类型定义如下: ADT QuadTrees{ 数据对象D:D是具有相同性质的具有二维结构的数据元素的集合,本实验为坐标数据。 数据关系R:若D为空集,则...(2) D中任意元素d将其子节点划分为个象限,将
  • 四叉树算法

    万次阅读 2016-03-05 10:25:19
    title: 四叉树算法 date: 2016-1-11 15:10 categories: IOS tags: 算法 小小程序猿 我的博客:http://daycoding.com 转载:http://blog.csdn.net/zhanxinhang/article/details/6706217 高德iOS聚合实例 高德...
  • 四叉树编码实现

    万次阅读 2013-09-16 11:48:18
    关于四叉树的原理我想应该不需要多说啦,大家都懂得,实在不晓得的话,百度吧~ 由于四叉树索引效率还可以并且非常简单,因此在Gis中广泛的应用也是毋庸置疑的。   本次就自己实现一个地图四叉树索引,但是还有...
  • 这里我们学习一下使用四叉树来对碰撞检测进行优化,优化的根本是碰撞检测时跳过那些明显离得很远的物体,加快检测速度。【注:这里算法的实现使用的Java语言,但算法和语言没有关系,理解了其中的原理可以应用到各种...
  • 网格与四叉树空间索引

    千次阅读 2014-08-12 10:58:33
    在介绍空间索引之前,先谈谈什么叫“索引“。对一个数据集做”索引“,是为了提高对这个数据集检索的效率。书的”目录“就是这本书内容的”索引“,当我们拿到一本新书,想查看感兴趣内容的时候,我们会先查看目录,...
  • 这个代码是一个四叉树的C#实现,使用四叉树文成一个可视项目。四叉树是一种树结构可以用于编码和2D碰撞检测。多用在2D碰撞检测中,在大量的碰撞检测中可以提高效率,但结构略复杂。
  • matlab图像分解四叉树分解显示

    热门讨论 2020-07-28 23:33:04
    此资源为matlab代码,对图像进行四叉树分解,并把分解后的结果显示于原图。
  • 四叉树分割的示意图(matlab)

    热门讨论 2020-07-28 23:30:12
    matlab程序,用于显示四叉树分割后的示意图。这是个主程序,不是函数,运行前需要修改程序所读入的图像位置。
  • 四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,...四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的空间数据插入和查询效率,因
  • 用java实现的四叉树编码源码

    热门讨论 2020-07-24 23:33:34
    从文件读取四叉树结点,按照morton码对四叉树进行编码
  • geotools介绍 ... Geotools是一个java类库,它提供了很多的标准类和方法来处理空间数据,同时这个类库是构建在OGC标准之上的,是OGC思想的一种实现。而OGC是国际标准,所以geotools将来必定会成为开源空间数据处理的...
  • 四叉树优化碰撞检测

    万次阅读 热门讨论 2015-05-26 00:32:18
    游戏中碰撞检测分为两个阶段:broad phase 和 narrow phase。接下来要介绍的就是broad phase。在broad phase这个阶段,我们的主要任务是将屏幕上的物体进行筛选,筛选出最可能发生碰撞的物体集合。...
  • 四叉树LOD地形入门学习

    热门讨论 2020-07-30 23:33:08
    基于 LOD 的大规模真实感室外场景实时渲染技术 四叉树LOD地形入门
1 2 3 4 5 ... 20
收藏数 41,296
精华内容 16,518
关键字:

四叉树