사지 수 알고리즘 원리 와 실현

원리
사지 수 인 코딩 의 기본 사상 은 먼저 그림 이나 격자 지도 (, k > 1, 부족 하면 보 망) 등 을 네 개의 1 급 글자 블록 으로 나 누고 순 서 는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 이다.그리고 블록 별로 그 중의 모든 격자 속성 값 (또는 그 레이스 케 일 값) 을 검사 합 니 다. 같 으 면 이 글 자 는 다시 나 누 지 않 습 니 다.만약 다르다 면 이 덩어리 를 4 개의 2 급 덩어리 로 나 누 어 라.모든 하위 블록 의 속성 이나 그 레이스 케 일이 같 을 때 까지 이렇게 재 귀적 으로 분할 합 니 다.
2. 알고리즘 실현

 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("
");

22         return;

23     }

24 

25     else

26     {

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