# Thread: Quad-tree algorithm problems

1. ## Quad-tree algorithm problems

Hi everyone,

I am trying to make a quadtree compression algorithmn for tga files, but have come across a lot of problems which I am not sure how to solve. If anybody could help me out that would be greatly appreciated. Thanks

Here is the current code I have:
Code:
```#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>

#define HEADERSIZE 18

void CreateNode(unsigned int Bounding[4],unsigned int ParentID,unsigned int NodeID); //creates nodes, used to create the quadtree
unsigned int CalcNodeNum(unsigned int max,unsigned int min); //create
typedef struct
{
unsigned char R;
unsigned char G;
unsigned char B;
} Pixel;

void checkFP (FILE *fp);

typedef struct quadtreeNode
{
unsigned char R;
unsigned char G;
unsigned char B;
quadtreeNode *ptr_NW;
quadtreeNode *ptr_NE;
quadtreeNode *ptr_SW;
quadtreeNode *ptr_SE;
};
bool RGBcheck(int x,int y,Pixel Image[],int width,int height);

void quad(int initialWidth, int EndWidth,int initialHeight,int EndHeight ,quadtreeNode *newNode,quadtreeNode *ptr_root, quadtreeNode *ptr_next, quadtreeNode *ptr_previous, Pixel Image[],int width,int height);
void newnode(int initialWidth, int EndWidth, int initialHeight, int EndHeight, quadtreeNode *newNode,quadtreeNode *ptr_root, quadtreeNode *ptr_next, quadtreeNode *ptr_previous, Pixel Image[], int width,int height);
void checkImage(int initialWidth, int initialHeight, int EndWidth, int EndHeight, quadtreeNode *newNode, quadtreeNode *ptr_root,quadtreeNode *ptr_next, quadtreeNode *ptr_previous, Pixel Image[], int width,int height);
int main(void)
{

int c;
char word[2];
FILE * fp;

printf("\nLoading Header ... ");fflush(stdout);
//fp = fopen("ghg.tga", "rb");
fp = fopen("gf.tga", "rb");

checkFP(fp);
unsigned char header[HEADERSIZE];
for(c=0;c<HEADERSIZE;c++)
{
fscanf(fp, "%c", &header[c]);
}

int width   = (header[13]<<8)+header[12];
int height   = (header[15]<<8)+header[14];
printf("Done (%dx%d). Ver. 1.1\n", width, height);
fflush(stdout);

Pixel Image[width*height];
printf("Loading Data ... \n");fflush(stdout);
printf("%d\n", width);
for(c=0;c<width*height;c++)
{
fscanf(fp, "%c", &Image[c].B);
fscanf(fp, "%c", &Image[c].G);
fscanf(fp, "%c", &Image[c].R);

}
struct quadtreeNode *ptr_root; //
struct quadtreeNode *ptr_next;
struct quadtreeNode *ptr_previous;

struct quadtreeNode *newNode;
ptr_root = newNode;
newNode = (quadtreeNode *)malloc(sizeof(quadtreeNode));

ptr_root->ptr_NW = NULL;
ptr_root->ptr_NE= NULL;
ptr_root->ptr_SW = NULL;
ptr_root->ptr_SE = NULL;
ptr_next = newNode;
ptr_previous = newNode;

int initialWidth = 0;
int initialHeight = 0;
int EndWidth = width;
int EndHeight = height;

checkImage(initialWidth,initialHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height);
fclose(fp);
printf("Done.\n");fflush(stdout);

printf ("\n\n==============================\n%d",width*height);
printf("Done.\n");fflush(stdout);
gets(word);
gets(word);
return EXIT_SUCCESS;
}
// create new node/leaf node
void newnode(int initialWidth, int EndWidth, int initialHeight, int EndHeight, quadtreeNode *newNode,quadtreeNode *ptr_root, quadtreeNode *ptr_next, quadtreeNode *ptr_previous, Pixel Image[], int width, int height)
{
printf("new node\n");fflush(stdout);
// newNode = new struct quadtreeNode;
//     ptr_next->ptr_NW->ptr_NW= NULL;
//     ptr_next->ptr_NW->ptr_NE = NULL;
//     ptr_next->ptr_NW->ptr_SW = NULL;
//     ptr_next->ptr_NW->ptr_SE = NULL;
//
//     newNode = new struct quadtreeNode;
//     ptr_next->ptr_NE->ptr_NW = NULL;
//     ptr_next->ptr_NE->ptr_NE = NULL;
//     ptr_next->ptr_NE->ptr_SW = NULL;
//     ptr_next->ptr_NE->ptr_SE = NULL;
//
//     newNode = new struct quadtreeNode;
//     ptr_next->ptr_SW->ptr_NW = NULL;
//     ptr_next->ptr_SW->ptr_NE = NULL;
//     ptr_next->ptr_SW->ptr_SW = NULL;
//     ptr_next->ptr_SW->ptr_SE = NULL;
//
//     newNode = new struct quadtreeNode;
//     ptr_next->ptr_SE->ptr_NW = NULL;
//     ptr_next->ptr_SE->ptr_NE = NULL;
//     ptr_next->ptr_SE->ptr_SW = NULL;
//     ptr_next->ptr_SE->ptr_SE = NULL;

//quad each pointer
quad(initialWidth,EndWidth,initialHeight,EndHeight,newNode,ptr_root,ptr_next->ptr_NW,ptr_next,Image,width,height);
quad(initialWidth,EndWidth,initialHeight,EndHeight,newNode,ptr_root,ptr_next->ptr_NE,ptr_next,Image,width,height);
quad(initialWidth,EndWidth,initialHeight,EndHeight,newNode,ptr_root,ptr_next->ptr_SW,ptr_next,Image,width,height);
quad(initialWidth,EndWidth,initialHeight,EndHeight,newNode,ptr_root,ptr_next->ptr_SE,ptr_next,Image,width,height);
}
//checks the image
void checkImage(int initialWidth, int initialHeight, int EndWidth, int EndHeight, quadtreeNode *newNode, quadtreeNode *ptr_root, quadtreeNode *ptr_next, quadtreeNode *ptr_previous, Pixel Image[], int width,int height)
{
//     printf("***********Check image************\n");
//     printf("Initial width : %d Initial Height : %d\n",initialWidth,initialHeight);
//     printf("End width : %d End height : %d\n", EndWidth,EndHeight);
//     printf("For Y = %d ; Y < %d; Y++\n",initialHeight,EndHeight);
//     printf("For X = %d ; X < %d; X++\n",initialWidth,EndWidth);
//     printf("Cell width %d\n",EndWidth-initialWidth);
//     printf("Width %d\n",width);
//     printf("check image\n");fflush(stdout);

for(int y = initialHeight;y<EndHeight;y++)
{
for(int x = initialWidth; x<EndWidth;x++)
{
if ((RGBcheck(x,y,Image,width,height) == false))   //if pixels dont match
{

printf(" R: %d :  G %d :  B %d Coords X:%d,Y:%d Width %d Height %d\n",Image[x+(y*width)].R, Image[x+(y*width)].G, Image[x+(y*width)].B,x,y,width,height);
newnode(initialWidth,initialHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_next,ptr_previous,Image,width,height);
fflush(stdout);
}
// else //if width and height are both equal to 1 pixel
// {
//     printf("width/height are 1 pixel in width\n");
//create new node - need to go back
//   newnode(initialWidth,initialHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_previous,Image,width,height);
//********************************************************************************************************************************************//
//problem is here
//not sure if i need this
//go back to previous pointers (can i do this like this?) or do i need to loop through it
// ptr_previous->ptr_NW->R = Image[x+(width * y)].R;
//                       ptr_previous->ptr_NW->G = Image[x+(width * y)].G;
//                       ptr_previous->ptr_NW->B = Image[x+(width * y)].B;
//                       ptr_previous->ptr_NE->R = Image[x+(width * y)].R;
//                       ptr_previous->ptr_NE->G = Image[x+(width * y)].G;
//                       ptr_previous->ptr_NE->B = Image[x+(width * y)].B;
//                       ptr_previous->ptr_SW->R = Image[x+(width * y)].R;
//                       ptr_previous->ptr_SW->G = Image[x+(width * y)].G;
//                       ptr_previous->ptr_SW->B = Image[x+(width * y)].B;
//                       ptr_previous->ptr_SE->R = Image[x+(width * y)].R;
//                       ptr_previous->ptr_SE->G = Image[x+(width * y)].G;
//                       ptr_previous->ptr_SE->B = Image[x+(width * y)].B;
//********************************************************************************************************************************************//
//  }
//}
else //if pixels match
{
printf(" R: %d :  G %d :  B %d Coords X:%d,Y:%d Width %d Height %d\n",Image[x+(y*width)].R, Image[x+(y*width)].G, Image[x+(y*width)].B,x,y,width,height);
//ptr_next->R = Image[x+(width * y)].R;
// ptr_next->G = Image[x+(width * y)].G;
// ptr_next->B = Image[x+(width * y)].B;
// not sure how to go to next quadrant of image here
}
}
}

}

// split the image into quadrants
void quad(int initialWidth, int EndWidth,int initialHeight,int EndHeight ,quadtreeNode *newNode, quadtreeNode *ptr_root,quadtreeNode *ptr_next, quadtreeNode *ptr_previous, Pixel Image[],int width,int height)
{
int middlePoint = ((EndWidth - initialWidth)/2);
int newWidth = initialWidth + middlePoint;
int newHeight = initialHeight + middlePoint;
int newEndWidth = EndWidth/2;
int newEndHeight = EndHeight/2;

int y;
int x;
//     printf("\n");
//     printf("Width : %d Height : %d\n",width,height);
//     printf("**************Quad*****************\n");
//     printf("Initial width : %d Initial Height : %d\n",initialWidth,initialHeight);
//     printf("End width : %d End height : %d\n", EndWidth,EndHeight);
//     printf("New End width : %d New End height : %d\n", newEndWidth,newEndHeight);
//     printf("Middlepoint : %d \n", middlePoint);
//    printf("***********************************\n");

if((initialWidth == EndWidth/2)||(initialWidth > EndWidth/2)&&(initialHeight == EndHeight/2) && (initialHeight > EndHeight/2))
{

checkImage(initialWidth,initialHeight,newWidth,newHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //topleft
checkImage(newWidth,initialHeight,EndWidth,newHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //top right
checkImage(initialWidth,newHeight,newWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom left
checkImage(newWidth,newHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom right
}
if((initialWidth == EndWidth/2)||(initialWidth > EndWidth/2))
{
checkImage(initialWidth,initialHeight,newWidth,newEndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //topleft
checkImage(newWidth,initialHeight,EndWidth,newEndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //top right
checkImage(initialWidth,newEndHeight,newWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom left
checkImage(newWidth,newEndHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom right
}
if((initialHeight == EndHeight/2)||(initialHeight > EndHeight/2))
{
checkImage(initialWidth,initialHeight,newEndWidth,newHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //topleft
checkImage(newEndWidth,initialHeight,EndWidth,newHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //top right
checkImage(initialWidth,newHeight,newEndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom left
checkImage(newEndWidth,newHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom right
}
else
{
checkImage(initialWidth,initialHeight,newEndWidth,newEndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //topleft
checkImage(newEndWidth,initialHeight,EndWidth,newEndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //top right
checkImage(initialWidth,newEndHeight,newEndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom left
checkImage(newEndWidth,newEndHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height);//bottom right
}
//printf("***********************************\n");
//printf("\n************************Top left************************\n");
//for(y=initialHeight;y<newEndHeight;y++)
//{
//    for (x=initialWidth;x<newEndWidth;x++)
//     {
//             printf(" R: %d :  G %d :  B %d Coords X:%d,Y:%d Width %d Height %d\n",Image[x+(y*width)].R, Image[x+(y*width)].G, Image[x+(y*width)].B,x,y,width,height);
//     }
//}
//printf("***********************************\n");
//printf("\n************************Top right************************\n");
//for(y=initialHeight;y<newEndHeight;y++)
//{
//    for (x=newEndWidth;x<EndWidth;x++)
//     {
//             printf(" R: %d :  G %d :  B %d Coords X:%d,Y:%d Width %d Height %d\n",Image[x+(y*width)].R, Image[x+(y*width)].G, Image[x+(y*width)].B,x,y,width,height);
//     }
//}
//printf("***********************************\n");
//printf("\n************************Bottom left************************\n");
//for(y=newEndHeight;y<EndHeight;y++)
//{
//  for (x=initialWidth;x<newEndWidth;x++)
//     {
//             printf(" R: %d :  G %d :  B %d Coords X:%d,Y:%d Width %d Height %d\n",Image[x+(y*width)].R, Image[x+(y*width)].G, Image[x+(y*width)].B,x,y,width,height);
//     }
//}
//
//printf("***********************************\n");
//printf("\n************************Bottom right ************************\n");
//for(y=newEndHeight;y<EndHeight;y++)
//{
//  for (x=newEndWidth;x<EndWidth;x++)
//     {
//             printf(" R: %d :  G %d :  B %d Coords X:%d,Y:%d Width %d Height %d\n",Image[x+(y*width)].R, Image[x+(y*width)].G, Image[x+(y*width)].B,x,y,width,height);
//     }
//}

}

void checkFP(FILE * fp)
{
char word[2];
if(fp==NULL)
{
printf("File not found : Press any key to exit");
gets(word);
gets(word);
exit(EXIT_FAILURE);
}
}

// checks pixels
bool RGBcheck(int x,int y,Pixel Image[],int width,int height)
{
if ((Image[x+(y*width)].R == Image[x+(y*width)+1].R)&&(Image[x+(y*width)].G == Image[x+(y*width)+1].G)&&(Image[x+(y*width)].B == Image[x+(y*width)+1].B))
{
// printf("*\n");
return true;
}
else
{

return false;
}

}```
Regards Maiden

2. So apart from being ugly and non-portable code, what's the problem?

3. Well the problem is the quad function doesn't work at all, it doesn't quad the image. Any help would be appreciated

Popular pages Recent additions