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

    2012-07-10 08:11:57
    基于十进制实现四叉树的编码,以moton码存储属性数据的行列号
  • 这个代码是一个四叉树的C#实现,使用四叉树文成一个可视项目。四叉树是一种树结构可以用于编码和2D碰撞检测。多用在2D碰撞检测中,在大量的碰撞检测中可以提高效率,但结构略复杂。
  • C# GIS算法演示:道格拉斯压缩、线性四叉树、投影变换等
  • 四叉树编码的原理

    热门讨论 2012-01-10 08:39:42
    文档主要描述四叉树的思想的原理,能清除的给读者知道四叉树的来龙去脉,因此,不懂此原理的朋友可下载。
  • Yogurt是一名学GIS的学生,今天要跟大家分享的是四叉树这种空间索引方式的Morton编码方法,接下来我将在小课堂中简单介绍一下空间索引以及其几种编码方式~~ -----------------------------------------------------...

        Yogurt是一名学GIS的学生,今天要跟大家分享的是四叉树这种空间索引方式的Morton编码方法,接下来我将在小课堂中简单介绍一下空间索引以及其几种编码方式~~

    ---------------------------------------------------------yogurt小课堂开课啦--------------------------------------------------------

        GIS所涉及到的都是有关空间的数据信息,即也属于所谓的大数据了,那么怎么将客观的物体对象存储到计算机中,以及怎么从计算机中读取所需要的数据呢?

        首先我们要知道计算机的存储器有内存和外存,内存空间小但是读写快,外存空间大却读写慢,访问外存所花费的时间是访问内存的十万倍以上!在GIS的实际应用中大量的数据都是存储在外存上的,想象一下如果这些数据全都杂乱无章的堆放在那里,那么每需要查询一个数据就需要扫描整个数据文件,这样访问磁盘的代价是非常大的,严重影响了系统效率!所以,我们必须记录好每个数据存放的位置,以便于组织和管理,在这个过程中就需要用到索引技术啦!

        【(这里引自我老师的课件哈,低调低调!!!)

        从传统的索引技术观点来看,可以把空间索引技术大致分为四大类:基于R树,基于Hashing,基于二叉树,基于空间填充。

        在建立索引时,按照划分区域是否与空间对象的分布特征有关的标准,空间索引又可以分为两大类:无关的(网格索引、四叉树),有关的(BSP树、KD树、KDB树、R树及其变种树)。

        我们来看看几种索引方法的实际应用:

        (1)ESRI的ArcSDE采用的是固定格网索引;

        (2)目前国内外主要的空间数据库如ESRI的ArcView,Mapinfo公司的Maoinfo和Informix的GeoSpatial DataBlade采用的是R树系列作为空间索引的方式;

        (3)Oracle公司的Spatial同时采用固定格网索引以及R树索引;

        (4)中国地质大学的MapGIS和中科院的SuperMap采用的是四叉树。

         以上来自我的一个大牛老师的PPT~~】

        好啦,既然今天要讲矩阵四叉树的Morton编码,那么接下来就介绍一下四叉树以及Morton码的编码规则吧:

       【四叉树】:

        区域型物体的四叉树表示方法最早出现在加拿大地理信息系统CGIS中,20世纪80年代以来,四叉树在图象分割、数据压缩、 地理信息系统等方面进行了大量的研究,对四叉树数据结构提出了许多编码方案。四叉树分为常规四叉树与线性四叉树,下图简单的说明了两者的区别:(不要嫌弃我字丑!!!)

        编码规定:

           

       【线性四叉树的编码方式】: 例如有这样一个矩阵线性四叉树,以红色圈中的9的编码为例,有自上而下的方法和自下而上的方法:

           

       (1)基于深度和层次码线性四叉树编码:(自上而下的方法)

       层次码:第一层(在位置2,用两位二进制表示为:10),第二层(在位置1,用两位二进制表示为:01),第三层(在位置2,用两位二进制表示为:10);

       深度码:有3层深,(用四位二进制表示为:0011);

       “9”的位置编码为:10 01 10 0011,该位置码的十进制为2^0+2^1+2^5+2^6+2^9=611.

       (2)基于四进制的线性四叉树编码:

       (自上而下的方法):第一层2,第二层1,第三层2,位置码:212

       (自下而上的方法,说明四进制编码的过程):二进制的行列号Iyb、Ixb(从第0行0列开始),四进制编码M=2*Iyb+ Ixb;那么这里就是:第5行(101)第2列(010):M=2*101+10=212

       (3)基于十进制的线性四叉树编码:

       (自下而上的方法,说明四进制编码的过程):二进制的行列号Iyb、Ixb(从第0行0列开始),十进制编码M=奇数位用列号填充,偶数位用行号填充;那么这里就是:第5行(101)第2列(010):M=10 01 10

       (4)在相邻四个码中若属性值相同,进行合并,除去最低位得到合并后的新编码。

    -----------------------------------------------------------下课啦!!!--------------------------------------------------------------

     

     

    编写该程序的思路:

    第一步:读入矩阵四叉树,并将其输出;

    第二步:利用four_decimal函数得到每一个位置的四进制M码,利用Change函数得到规定格式的三位四进制M码;最后利用checkcombine_four函数,将属性值一样的位置的M码合并,并输出;

    第三步:同第二步类似,利用ten_decimal函数得到每一个位置的十进制M码,利用checkcombine_ten函数,将属性值一样的位置的M码合并,并输出。

     

    具体实现过程:

    (1)将十进制行列号转换为二进制:利用函数Tobinary :

    (2)得到四进制M码:利用函数four_decimal:

    (3)得到十进制M码:利用函数ten_decimal:(注意按位交错)

    (4)对属性值一样的M码进行合并的处理操作checkcombine_ten:(以十进制为例)

    在第二层里:(方法与第一层类似,只是合并条件变成了w==2)

    最后输出数组即可,对于四进制的M码,由于合并时还要除去最低位的,所以需要特殊处理(便于输出):如在合并第一层时,给第二三位赋予标志值99999999:

     

    合并第二层时,给第三位赋予标志值99999999:

     

    输出时:

     

    好啦,接下来是整体代码:

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    
    typedef int newc[3];
    typedef int ceng[2];
    
    void read(int a[][8]);                             //读入矩形四叉树
    int Tobinary(int k);                               //将十进制的行列号k转换为二进制.
    int eq(int m, int n);                              //判断m和n是否相等,相等则返回1,否则返回0.
    void judge_four(int a[][8], newc b[][8], ceng c[4]);//判断数组c表示的矩形范围内的值是否一样,若一样就更新数组b.
    void judge_ten(int a[][8], int b[][8], ceng c[4]); 
    void checkcombine_four(int a[][8], newc b[][8]);   //将属性值一样的单元进行合并.
    void checkcombine_ten(int a[][8], int b[][8]);     
    void Change(int m[][8], newc n[][8]);              //将四进制的M码按照规定格式输出.
    void four_decimal(int b[][8]);                     //四进制编码.
    void ten_decimal(int c[][8]);                      //十进制编码.
    void output_i(int a[][8]);                         //输出int型数组.
    void output_c(newc a[][8]);                        //输出newc型数组.
    
    void main()
    {
        int a[8][8], b[8][8], c[8][8];
        newc bb[8][8];
        read(a);
        printf("矩阵四叉树为:\n");
        output_i(a);
    
        four_decimal(b);
        Change(b, bb);
        checkcombine_four(a,bb);
        printf("\n四叉树对应的四进制编码为:\n");
        output_c(bb);
    
        ten_decimal(c);
        checkcombine_ten(a,c);
        printf("\n四叉树对应的十进制编码为:\n");
        output_i(c);
    }
    
    void read(int a[][8])
    {
        FILE *fp = fopen("四叉树.txt","r");
        if (!fp)
            exit;
        else
        for (int i = 0; i < 8;i++)
        for (int j = 0; j < 8; j++)
            fscanf(fp, "%d", &a[i][j]);
        fclose(fp);
    }
    
    int Tobinary(int k)
    {
        int s[10],rem,i=0,t=0;
        do
        {
            rem = k % 2;
            k = k / 2;
            s[i++] = rem;
        } while (k != 0);   //当十进制数是0时也要进行一遍此循环,所以必须用do……while循环,而不是while循环
        for (int j = --i; j >= 0; j--)
        {
            t += s[j] * pow(10.0, j);
        }
        return t;
    }
    
    int eq(int m, int n)
    {
        if (m == n)
            return 1;
        else
            return 0;
    }
    
    void judge_four(int a[][8], newc b[][8], ceng c[4])
    {
        for (int i = 0; i < 4; i++)
        {
            int w = 0;
            for (int m = c[i][0]; m <c[i][0] + 2; m++)
            for (int n = c[i][1]; n <c[i][1] + 1; n++)
                w += eq(a[m][n], a[m][n + 1]);
            if (w == 2)//4个值属性一样
            {
                for (int m = c[i][0]; m <c[i][0] + 2; m++)
                for (int n = c[i][1]; n < c[i][1] + 2; n++)
                {
                    *b[m][n] = *b[(c[i][0])][(c[i][1])];
                    *(b[m][n] + 1) = *(b[(c[i][0])][(c[i][1])] + 1);
                    *(b[m][n] + 2) = 99999999;
                }
            }
        }
    }
    
    void judge_ten(int a[][8], int b[][8], ceng c[4])
    {
        for (int i = 0; i < 4; i++)
        {
            int w = 0;
            for (int m = c[i][0]; m <c[i][0]+2; m++)
            for (int n = c[i][1]; n <c[i][1]+1; n++)
                w += eq(a[m][n], a[m][n + 1]);
            if (w == 2)//4个值属性一样
            {
                for (int m = c[i][0]; m <c[i][0] + 2; m++)
                for (int n = c[i][1]; n < c[i][1] + 2; n++)
                {
                    b[m][n] = b[(c[i][0])][(c[i][1])];
                }
            }
        }
    }
    
    void checkcombine_ten(int a[][8], int b[][8])
    {
        //第一层
        ceng c[4] = { { 0, 0 }, { 0, 4 }, { 4, 0 }, { 4, 4 } };
        for (int i = 0; i < 4; i++)
        {
            int w = 0;
            for (int m = c[i][0]; m < 4; m++)
            for (int n = c[i][1]; n < 3; n++)
                w += eq(a[m][n], a[m][n + 1]);
            if (w == 12)//16个值属性一样
            {
                for (int m = c[i][0]; m < c[i][0] + 4; m++)
                for (int n = c[i][1]; n < c[i][1] + 4; n++)
                {
                    b[m][n] = b[(c[i][0])][(c[i][1])];
                }
            }
        }
        //第二层
        ceng d[4] = { { 0, 0 }, { 0, 2 }, { 2, 0 }, { 2, 2 } },
            e[4] = { { 0, 4 }, { 0, 6 }, { 2, 4 }, { 2, 6 } },
            f[4] = { { 4, 0 }, { 4, 2 }, { 6, 0 }, { 6, 2 } },
            g[4] = { { 4, 4 }, { 4, 6 }, { 6, 4 }, { 6, 6 } };
        judge_ten(a, b, d);
        judge_ten(a, b, e);
        judge_ten(a, b, f);
        judge_ten(a, b, g);
    }
    
    void checkcombine_four(int a[][8], newc b[][8])
    {
        //第一层
        ceng c[4] = { { 0, 0 }, { 0, 4 }, { 4, 0 }, { 4, 4 } };
        for (int i = 0; i < 4; i++)
        {
            int w = 0;
            for (int m = c[i][0]; m < 4; m++)
            for (int n = c[i][1]; n < 3; n++)
                w += eq(a[m][n], a[m][n + 1]);
            if (w == 12)//16个值属性一样
            {
                for (int m = c[i][0]; m < c[i][0] + 4; m++)
                for (int n = c[i][1]; n < c[i][1] + 4; n++)
                {
                    *b[m][n] =*b[(c[i][0])][(c[i][1])];
                    *(b[m][n] + 1) =99999999;
                    *(b[m][n] + 2) =99999999;
                }
            }
        }
        //第二层
        ceng d[4] = { { 0, 0 }, { 0, 2 }, { 2, 0 }, { 2, 2 } },
            e[4] = { { 0, 4 }, { 0, 6 }, { 2, 4 }, { 2, 6 } },
            f[4] = { { 4, 0 }, { 4, 2 }, { 6, 0 }, { 6, 2 } },
            g[4] = { { 4, 4 }, { 4, 6 }, { 6, 4 }, { 6, 6 } };
        judge_four(a, b, d);
        judge_four(a, b, e);
        judge_four(a, b, f);
        judge_four(a, b, g);
    }
    
    void Change(int m[][8], newc n[][8])
    {
        int t[3];
        int q;
        for (int i = 0; i < 8;i++)
        for (int j = 0; j < 8; j++)
        {
            q = m[i][j];
            t[0] = q / 100;
            q = q % 100;    
            t[1] = q / 10;
            q = q % 10;
            t[2] = q;
            *n[i][j] = *t;             //数组赋值,数组名称不能直接做左值
            *(n[i][j] + 1) = *(t + 1);
            *(n[i][j] + 2) = *(t + 2);
        }
    }
    
    void four_decimal(int b[][8])
    {
        for (int i = 0; i < 8;i++)
        for (int j = 0; j < 8;j++)
        {
            int m=Tobinary(i);
            int n=Tobinary(j);
            b[i][j] = 2 * m + n;
        }
    }
    
    void ten_decimal(int c[][8])
    {
        for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
        {
            int m = Tobinary(i);
            int n = Tobinary(j);
            int t[8];
            t[0] = m / 1000;
            m = m % 1000;
            t[2] = m / 100;
            m = m % 100;
            t[4] = m / 10;
            m = m % 10;
            t[6] = m;
    
            t[1] = n / 1000;
            n = n % 1000;
            t[3] = n / 100;
            n = n % 100;
            t[5] = n / 10;
            n = n % 10;
            t[7] = n;
    
            int y = 0;
            for (int w = 0; w < 8; w++)
            {
                y+= t[w] * pow(2.0,7-w);
            }    
            c[i][j] = y;
        }
    }
    
    void output_i(int a[][8])
    {
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                printf("%6d", a[i][j]);
            }
            printf("\n");
        }
    }
    
    void output_c(newc a[][8])
    {
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
            if (*(a[i][j] + 1)==99999999&&*(a[i][j] + 2)==99999999)
                printf("%6d", *a[i][j]);
            else if (*(a[i][j] + 2) == 99999999)
                printf("%5d%d", *a[i][j], *(a[i][j] + 1));
            else
                printf("%4d%d%d", *a[i][j], *(a[i][j] + 1), *(a[i][j] + 2));
            printf("\n");
        }
    }
    View Code

     

    最后结果:

     

    转载于:https://www.cnblogs.com/to-sunshine/p/6430485.html

    展开全文
  • vc++实现图像数据结构图遍历算法四叉树
  • 四叉树

    千次阅读 2019-05-30 11:53:00
    本文着重于对四叉树与八叉树的原理与结构的介绍,帮助您在脑海中建立四叉树与八叉树的基本思想。本文并不对这两种数据结构同时进行详解,而只对四叉树进行详解,因为八叉树的建立可由四叉树的建立推得。...

    前序

    四叉树或四元树也被称为Q树(Q-Tree)。四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等,而八叉树(Octree)主要应用于3D图形处理。对游戏编程,这会很有用。本文着重于对四叉树与八叉树的原理与结构的介绍,帮助您在脑海中建立四叉树与八叉树的基本思想。本文并不对这两种数据结构同时进行详解,而只对四叉树进行详解,因为八叉树的建立可由四叉树的建立推得。若有不足之处,望能不吝指出,以改进之。^_^  欢迎Email:zhanxinhang@gmail.com

    四叉树与八叉树的结构与原理

    四叉树(Q-Tree)是一种树形数据结构。四叉树的定义是:它的每个节点下至多可以有四个子节点,通常把一部分二维空间细分为四个象限或区域并把该区域里的相关信息存入到四叉树节点中。这个区域可以是正方形、矩形或是任意形状。以下为四叉树的二维空间结构(左)和存储结构(右)示意图(注意节点颜色与网格边框颜色):

     

     

    四叉树的每一个节点代表一个矩形区域(如上图黑色的根节点代表最外围黑色边框的矩形区域),每一个矩形区域又可划分为四个小矩形区域,这四个小矩形区域作为四个子节点所代表的矩形区域。

    较之四叉树,八叉树将场景从二维空间延伸到了三维空间。八叉树(Octree)的定义是:若不为空树的话,树中任一节点的子节点恰好只会有八个,或零个,也就是子节点不会有0与8以外的数目。那么,这要用来做什么?想象一个立方体,我们最少可以切成多少个相同等分的小立方体?答案就是8个。如下八叉树的结构示意图所示:

     

     

     

    四叉树存储结构的c语言描述:

    /* 一个矩形区域的象限划分::

    UL(1) | UR(0)
    ----------|-----------
    LL(2) | LR(3)
    以下对该象限类型的枚举
    */
    typedef enum
    {
    UR = 0,
    UL = 1,
    LL = 2,
    LR = 3
    }QuadrantEnum;

    /* 矩形结构 */
    typedef struct quadrect_t
    {
    double left,
    top,
    right,
    bottom;
    }quadrect_t;

    /* 四叉树节点类型结构 */
    typedef struct quadnode_t
    {
    quadrect_t rect; //节点所代表的矩形区域
    list_t *lst_object; //节点数据, 节点类型一般为链表,可存储多个对象
    struct quadnode_t *sub[4]; //指向节点的四个孩子
    }quadnode_t;

    /* 四叉树类型结构 */
    typedef struct quadtree_t
    {
    quadnode_t *root;
    int depth; // 四叉树的深度
    }quadtree_t;


    四叉树的建立

    1、利用四叉树分网格,如本文的第一张图<四层完全四叉树结构示意图>,根据左图的网格图形建立如右图所示的完全四叉树。

    伪码:

    Funtion QuadTreeBuild ( depth, rect )

       {

    QuadTree->depth = depth;

     

    /*创建分支,root树的根,depth深度,rect根节点代表的矩形区域*/

    QuadCreateBranch (  root, depth, rect );

       }

     

    Funtion QuadCreateBranch ( n, depth,rect )

       {

    if ( depth!=0 )

       {

    n = new node;    //开辟新节点

    n ->rect = rect; //将该节点所代表的矩形区域存储到该节点中

    将rect划成四份 rect[UR], rect[UL], rect[LL], rect[LR];

     

    /*创建各孩子分支*/

    QuadCreateBranch ( n->sub[UR], depth-1, rect [UR] );

    QuadCreateBranch ( n->sub[UL], depth-1, rect [UL] );

    QuadCreateBranch ( n->sub[LL], depth-1, rect [LL] );

    QuadCreateBranch ( n->sub[LR], depth-1, rect [LR] );

       }

       }


    2、假设在一个矩形区域里有N个对象,如下左图一个黑点代表一个对象,每个对象的坐标位置都是已知的,用四叉树的一个节点存储一个对象,构建成如下右图所示的四叉树。

     

     

    方法也是采用递归的方法对该矩形进行划分分区块,分完后再往里分,直到每一个子矩形区域里只包含一个对象为止。

    伪码:

    Funtion QuadtreeBuild()

      {

         Quadtree = {empty};
         For (i = 1;i<n;i++)      //遍历所有对象

    {

       QuadInsert(i, root);//将i对象插入四叉树

    }          

             剔除多余的节点;       //执行完上面循环后,四叉树中可能有数据为空的叶子节点需要剔除
      }    


    Funtion QuadInsert(i,n)      //该函数插入后四叉树中的每个节点所存储的对象数量不是1就是0

      {  

         if(节点n有孩子)

     {      

        通过划分区域判断i应该放置于n节点的哪一个孩子节点c;       

        QuadInsert(i,c);

     }

         else if(节点n存储了一个对象)

     {

        为n节点创建四个孩子;

        将n节点中的对象移到它应该放置的孩子节点中;

        通过划分区域判断i应该放置于n节点的哪一个孩子节点c;

        QuadInsert(i,c);

     }

         else if(n节点数据为空)    

     {

        将i存储到节点n中;

     }

      } 

     

    (以上两种建立方法作为举一反三之用)

     

    用四叉树查找某一对象

    1、采用盲目搜索,与二叉树的递归遍历类似,可采用后序遍历或前序遍历或中序遍历对其进行搜索某一对象,时间复杂度为O(n)。

     

    2、根据对象在区域里的位置来搜索,采用分而治之思想,时间复杂度只与四叉树的深度有关。比起盲目搜索,这种搜索在区域里的对象越多时效果越明显

     

     

    伪码:

    Funtion find ( n, pos, )

      {

          If (n节点所存的对象位置为 pos所指的位置 )

              Return n;

          If ( pos位于第一象限 )

              temp = find ( n->sub[UR], pos );

          else if ( pos位于第二象限)

              temp = find ( n->sub[UL], pos );

          else if ( pos位于第三象限 )

              temp = find ( n->sub[LL], pos );

          else  //pos 位于第四象限

              temp = find ( n->sub[LR], pos );

          return temp;   

      } 

    结语:

    熟话说:结构之法,算法之道。多一种数据结构就多一种解决问题的方法,多一种方法就多一种思维模式。祝君学习愉快!^_^

     ==============================================

    声明:版权所有,转载请注明出处: http://blog.csdn.net/zhanxinhang/article/details/6706217

    参考:维基百科、百度百科

    参考:CS267: Lecture 24, Apr 11 1996 Fast Hierarchical Methods for the N-body Problem, Part 1

     


    ---------------------
    作者:zhanxinhang
    来源:CSDN
    原文:https://blog.csdn.net/zhanxinhang/article/details/6706217
    版权声明:本文为博主原创文章,转载请附上博文链接!

    转载于:https://www.cnblogs.com/vana/p/10948784.html

    展开全文
  • 线性四叉树的实现C++

    2020-11-06 19:28:39
    线性四叉树的实现 1)线性四叉树只存储最后的叶节点信息,包括叶节点的位置,大小和深度(根据数组下标可以直接得到)。 2)使用节点引用类型的vector容器表示一颗完全四叉树。 3) 完全四叉树的父节点数组下标为i时...

    线性四叉树的实现

    1)线性四叉树只存储最后的叶节点信息,包括叶节点的位置,大小和深度(根据数组下标可以直接得到)。
    2)使用节点引用类型的vector容器表示一颗完全四叉树。
    3) 完全四叉树的父节点数组下标为i时,对应的子节点下标为4*i+num,num∈{1,2,3,4}。

    不足:
    1.为了通过数组下标明确父节点与子节点的关系,采用的是完全四叉树的结构,由于地理空间对象可能分布不均衡,这样会导致四叉树生成一棵极为不平衡的树,也会造成树结构的不平衡以及存储空间的极大浪费。
    2.为了判断是否是叶子结点,在数组声明时,将数组元素的leaf成员声明为true,但是在插入数据之前并不知道树的深度,需要预留大量空间,并对数组中所有元素赋初值,导致时间和vector空间的浪费。
    3.存储非叶子节点的vector空间浪费。

    
    #include <iostream>
    #include <vector>
    #include<cstdlib>
    #include<math.h>
    #include <time.h>
    #include<fstream>
    const int MAX_NUM=100;
    using namespace std;
    struct Region;
    //最小外接矩形
    struct Region {
    	int right;
    	int left;
    	int up;
    	int bottom;
    };
    //点
    struct Point {
    	float x;
    	float y;	
    }p;
    //定义四叉树的节点
    struct QuadtNode {
       vector<Point> list;//存储四叉树该节点的所有坐标
       int depth;//四叉树的深度
       int size;//记录节点数,最大值MAX_NUM
       bool leaf;//记录是否为叶子节点
      Region region;  
    };
    vector<Point> xy;
    vector<Point> a_xy;
    vector< QuadtNode> q;
    vector< QuadtNode> &quadtree= q;//节点的vector容器来表示一颗四叉树
    void creatQuadtree();//创建空四叉树
    void insertQuadtree(long int , Point );//插入一个坐标
    void regionSet(QuadtNode node, int b, int u, int l, int r);//更新MBR
    void splitNode(long int index);//节点分裂
    void queryEle(int index, Point ele);//点查询
    void out();//文件输出
    int main()
    {
       long int i;
       quadtree.resize(100000);
      // cout << quadtree.capacity();
    	for (i = 0; i < 100000; i++) {
    		quadtree[i].leaf = 1;
    		quadtree[i].size = 0;
    		//cout<<quadtree[i].leaf;
    	}
    	//creatQuadtree();
    	//for (vector<QuadtNode>::iterator i = quadtree.begin(); i < quadtree.end(); i++) {
    		
    	Point p;
    	srand((int)time(NULL));//随机数
    	for (int i = 0; i < 1000; i++) {
    		p.y = (float)(rand() % 360 - 180 + (float)(rand() % 1000) / 1000);
    		p.x = (float)(rand() % 180 - 90 + (float)(rand() % 1000) / 1000);
    		insertQuadtree(0, p);
    		a_xy.push_back(p);
    	}
    	//for (vector<QuadtNode>::iterator it = quadtree.begin(); it < quadtree.end(); it++) {
    
    	//	if ((*it).leaf == 1&&(*it).leaf!=NULL)
    	//		for (vector<Point>::iterator count = (*it).list.begin(); count < (*it).list.end(); count++) {
    
    	//			cout << (*count).x << "," << (*count).y << endl;
    	//		}
    	//}
    	Point ele;
    	ele.x = -24;
    	ele.y = -20;
    	queryEle(0, ele);
    	out();
    }
    //查询
    void queryEle( int index,  Point ele) {
    	if (quadtree[index].leaf == 1) {
    		printf("附近点有%d个,分别是:\n", quadtree[index].size);
    		for (int j = 0; j < quadtree[index].size; j++) {
    			printf("%f,%f\n", quadtree[index].list[j].x, quadtree[index].list[j].y);
    			xy.push_back(quadtree[index].list[j]);
    		}
    		return;
    	}
    
    	double mid_vertical = (quadtree[index].region.up + quadtree[index].region.bottom) / 2;
    	double mid_horizontal = (quadtree[index].region.left + quadtree[index].region.right) / 2;
    
    	if (ele.x > mid_vertical) {
    		if (ele.y > mid_horizontal) {
    			queryEle(4 * index + 1, ele);
    		}
    		else {
    			queryEle(4 * index + 4, ele);
    		}
    	}
    	else {
    		if (ele.y > mid_horizontal) {
    			queryEle(4 * index + 2, ele);
    		}
    		else {
    			queryEle(4 * index + 3, ele);
    		}
    	}
    }
    //创建空四叉树
    void creatQuadtree()
    {
    	QuadtNode node;
    	p.x = 0;
    	p.y = 0;
    	node.list.push_back(p);
    	node.size = 0;
    	node.depth = 0;
    	node.region.bottom = -90;
    	node.region.up = 90;
    	node.region.left = -180;
    	node.region.right = 180;
    	node.leaf = 1;
    	quadtree.push_back(node);
    }
    //插入一个点,index是当前节点的下标
    void insertQuadtree(long int index, Point p)
    {
    	if (quadtree[index].leaf==true ) {//如果当前节点是叶子节点
    		if ((quadtree[index].size + 1 )> MAX_NUM){//节点数据已满
    			splitNode(index);//节点分裂			
    			insertQuadtree(index, p);
    		}
    		else {
    			quadtree[index].list.push_back(p);//节点未满则插入点坐标
    			quadtree[index].size++;	//更新节点所包含点数		
    		}
    		return;
    	}
    	//进入四分区域
    	double mid_vertical = (quadtree[index].region.up + quadtree[index].region.bottom) / 2;
    	double mid_horizontal = (quadtree[index].region.left + quadtree[index].region.right) / 2;
    	if (p.x > mid_vertical) {
    		if (p.y > mid_horizontal) {
    			insertQuadtree(4 * index + 1, p);//
    		}
    		else {
    			insertQuadtree(4 * index + 4, p);
    		}
    	}
    	else {
    		if (p.y > mid_horizontal) {
    			insertQuadtree(4 * index + 2, p);
    		}
    		else {
    			insertQuadtree(4 * index + 3, p);
    		}
    	}	
    }
    //更新MBR
    void regionSet(QuadtNode node,int b,int u,int l,int r )
    {	
    	node.region.bottom = b;
    	node.region.up = u;
    	node.region.left = l;
    	node.region.right = r;
    }
    //分裂节点
    void splitNode(long int index) {
    	double mid_vertical = (quadtree[index].region.up + quadtree[index].region.bottom) / 2;
    	double mid_horizontal = (quadtree[index].region.left + quadtree[index].region.right) / 2;
    	quadtree[index].leaf = 0;
    	regionSet(quadtree[4 * index + 1], mid_vertical, quadtree[4 * index + 1].region.up, mid_horizontal, quadtree[4 * index + 1].region.right);
    	regionSet(quadtree[4 * index + 2], mid_vertical, quadtree[4 * index + 2].region.up, quadtree[4*index+2].region.left, mid_horizontal);
    	regionSet(quadtree[4 * index + 3], quadtree[4 * index + 3].region.bottom, mid_vertical, mid_horizontal, quadtree[4 * index + 3].region.right);
    	regionSet(quadtree[4 * index + 4], quadtree[4 * index + 4].region.bottom, mid_vertical, quadtree[4 * index + 4].region.left, mid_horizontal);
    	for (int i = 0; i < quadtree[index].size; i++) {		
    		insertQuadtree(index, quadtree[index].list[i]);		
    		quadtree[index].size--;
    	} 
    	
    }
    //文件输出
    void out() {
    	fstream ofs1;
    	int i, j;
    	ofs1.open("XY.txt", ios::out);
    	for (i = 0; i < xy.size(); i++) {
    		ofs1 << xy[i].x << " ";
    		ofs1 << xy[i].y << endl;
    	}
    	fstream ofs2;
    	ofs2.open("allXY.txt", ios::out);
    	for (i = 0; i < a_xy.size(); i++) {
    		ofs2 << a_xy[i].x << " ";
    		ofs2 << a_xy[i].y << endl;
    	}
    
    }## 标题
    
    展开全文
  • 常规四叉树的结构如图所示,地理空间对象都存储在叶子节点上,中间节点以及根节点不存储地理空间对象。 四叉树示意图 四叉树对于区域查询,效率比较高。但如果空间对象分布不均匀,随着地理空间对象的不..

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

    代码有点长,有需要的朋友可以借鉴并自己优化。
    ————————————————
    版权声明:本文为CSDN博主「周旭光」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/zhouxuguang236/article/details/12312099

    展开全文
  • 原博客地址还有c++源码。。。 四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成个相等的子...四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的...
  • 一个线性四叉树编码的试题

    万次阅读 2018-06-27 17:58:57
    四叉树压缩第一次 M 0 1 2 3 4 5 6 7 8 12 16 20 24 25 26 27 28 29 30 31 32 36 40 44 45 46 47 48 52 53 54 55 56 60 值 1 1 0 ...
  • 四叉树数据结构 四叉树数据结构 常规四叉树 线性四叉树 1 四叉树分割的基本思想 k k 把一副图像或一副栅格地图2 x2 ,k>1等分成部分逐 块检查其格网值 如果某个子区的所有格网都含有相 2 3 1 同的值则子区不再分割 ...
  • #include #include #include #include #include using namespace std;int tree[400][4];///四叉树的数组 int leaf[350];///存储叶子节点 int image[16][16];///图像的矩阵 int m;///叶
  • 关于二叉树、四叉树和八叉树 树(tree)是一种常用的数据结构。它是由一个或多个节点组成的有限集T,它有一个特定节点,成为根节点。其余节点分为m(m大于等于0)个互不相交的有限集T0,T1,...,Tm-1,其中每个...
  • 四叉树编码-浅谈

    千次阅读 2014-12-06 10:15:00
     3,若单一则不再分割(即作为四叉树的叶子节点存储);若不单一,则分别对各个象限重复1,2的过程,直到所有象限的像元值都单一为止.  4,凡是属性值相同的子象限,不论大小,均作为最后的存储单元(作为一个叶子节点). ...
  • 一个入门四叉树例子

    千次阅读 2014-05-06 17:57:15
    概述   四叉树读书笔记  源代码: http://www.pudn.com/downloads343/sourcecode/windows/opengl/detail1500968.html   正文:
  • 四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成个相等的子空间,...四叉树的结构比较简单,并且当空间数据对象分布比较均匀时,具有比较高的空间数据插入和查询效率,因
  • 四叉树和希尔伯特曲线做空间索引

    千次阅读 2018-03-17 17:16:56
    本文着重于对四叉树与八叉树的原理与结构的介绍,帮助您在脑海中建立四叉树与八叉树的基本思想。本文并不对这两种数据结构同时进行详解,而只对四叉树进行详解,因为八叉树的建立可由四叉树的建立推得。若有不足之.....
  • 地理信息系统地理考研冲刺背诵宝典地理信息系统: 地理信息系统: 地理信息系统: 地理信息系统: 是由计算机硬件、软和不同的方法组成系统,该设支持 是由计算机硬件、软和不同的方法组成系统,该设支持 是由计算机...
  • 2D碰撞检测算法比较:栅格和四叉树

    千次阅读 多人点赞 2017-03-29 22:33:29
    本文主要比较三种算法: 1.普通遍历 2.栅格算法 3.四叉树算法
  • gis原理时做的作业,感觉挺麻烦 四叉树索引 c#

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,977
精华内容 3,190
关键字:

常规四叉树