首页 > 代码库 > 四叉树算法原理与实现

四叉树算法原理与实现

一、原理

四叉树编码的基本思想是:首先将把一副图像或栅格地图( ,k>1,不足则补网)等分成四个一级字块,顺序为左上,右上,左下,右下;然后逐块检查其中所有格网属性值(或灰度值),若相同,则该字块不再分;若不同,则将该子块进一步分成四个二级子块;如此递归地分割,直到每个子块的属性或灰度均相等为止。

二、算法实现

 1 //实现四叉树编码 2  3 #include"stdio.h" 4 void Qutree(int arysize,int level,float curary[] )//arysize 表示矩阵长度,level表示等级,curary[]表示当前矩阵 5 { 6      7     float fi=curary[0]; 8     int i; 9     //遍历当前数组,是否同构10     for(i=0;i<=arysize*arysize-1;i++)11     {12         if(fi!=curary[i])13         {14             break;15         }16 17     }18     if(i==arysize*arysize)19     {20         printf("%d,%f",level,fi);21         printf("\n");22         return;23     }24 25     else26     {27         arysize/=2;28         float *ary1=new float[arysize*arysize];29         float *ary2=new float[arysize*arysize];30         float *ary3=new float[arysize*arysize];31         float *ary4=new float[arysize*arysize];32         for(i=0;i<arysize;i++)33         {34             for(int j=0;j<arysize;j++)35             {36                 //左上37                 ary1[i*arysize+j]=curary[i*(arysize*2)+j];38                 //右上39                 ary2[i*arysize+j]=curary[i*(arysize*2)+(arysize+j)];40                 //左下41                 ary3[i*arysize+j]=curary[(arysize+i)*(arysize*2)+j];42                 //右下43                 ary4[i*arysize+j]=curary[(arysize+i)*(arysize*2)+(arysize+j)];44             }45         }46     47       level++;48       Qutree(arysize,level,ary1);49       Qutree(arysize,level,ary2);50       Qutree(arysize,level,ary3);51       Qutree(arysize,level,ary4);52 53     }54 55 }56 int main()57 {58     //float aa[16]={1,1,2,2,1,1,3,3,4,2,1,2,3,4,3,4};59     //Qutree(4,0,aa);60     float aa[64]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};61     Qutree(8,0,aa);62     return 0;63 64 }

参考资料:地理信息系统原理与算法(吴立新 、史文中编著)P176

四叉树算法原理与实现