Friday, November 13, 2009

Rectangle intersection problem with tree datastructure

The problem here is to write a program that will find all the rectangles that intersects with a given rectangle once the left bottom and top right of the rectangles are given.

#include < stdio.h>
#include < stdlib.h>
#include < sys/stat.h>


struct rect {
int x,y;
struct rect *left,*right,*rtpoint;
};

int xmin,ymin,xmax,ymax;

typedef struct rect rec;
rec *root=NULL,*newptr=NULL;

void find(int x1,int cnd) {
rec *parent=NULL,*tptr=NULL;
rec *ptr=root;
while(ptr!=NULL) {
parent=ptr;
if(cnd==0) {
//if( ((ptr->x > x1) && (ptr->rtpoint)->x < x1) || ((ptr->x < x1) && ((ptr->rtpoint)->x>x1) ) )
if(ptr->rtpoint!=NULL) {
if(check(ptr)) {
printf("\nIntersects (%d,%d) - (%d, %d)\n",ptr->x,ptr->y,(ptr->rtpoint)->x,(ptr->rtpoint)->y);
(ptr->rtpoint)->rtpoint=NULL;
ptr->rtpoint=NULL;
}
}
}
if(ptr->x > x1)
ptr=ptr->left;
else
ptr=ptr->right;
}
if(cnd==1) {
if(parent->x > x1 )
parent->left=newptr;
else
parent->right=newptr;
}
}

int check(rec *temp) {
rec *temp2=temp->rtpoint;
int ys=temp->y,xs=temp->x;
int yr=temp2->y,xr=temp2->x,t;
if(ys>yr) {
t=ys;
ys=yr;
yr=t;
}
if(xs>xr) {
t=xs;
xs=xr;
xr=t;
}
return !( (yr <= ymin) || (ys >= ymax) || (xr <= xmin) || (xs >= xmax) );
}

void preorder(rec *ptr) {
if(ptr!=NULL) {
preorder(ptr->left);
printf("x=%d y=%d\n",ptr->x,ptr->y);
preorder(ptr->right);
}
}
void bt_free() {
if(root==NULL)
return;
bt_free(root->left);
bt_free(root->right);
free(root);
}

int main() {

FILE * fp;
int temp;
rec *temp_ptr=NULL;
struct stat stFileInfo;
char filename[50];
do {
printf ("Enter the filename to get data : ");
gets(filename);
temp=stat(filename,&stFileInfo);
if(temp!=0) {
printf("File doesnt exist!!! \n");
}
}while(temp != 0);
fp = fopen(filename,"r");
while(fscanf(fp,"%d %d %d %d",&xmin,&ymin,&xmax,&ymax) > 0) {
if(root==NULL) {
root=(rec *)malloc(sizeof(rec));
root->x=xmin;
root->y=ymin;
root->left=NULL;
root->right=NULL;
temp_ptr=root;
newptr=(rec *)malloc(sizeof(rec));
newptr->left=NULL;
newptr->right=NULL;
newptr->rtpoint=temp_ptr;
newptr->x=xmax;
newptr->y=ymax;
find(xmax,1);
temp_ptr->rtpoint=newptr;
}
else {
newptr=(rec *)malloc(sizeof(rec));
newptr->left=NULL;
newptr->right=NULL;
newptr->x=xmin;
newptr->y=ymin;
temp_ptr=newptr;
find(xmin,1);
newptr=(rec *)malloc(sizeof(rec));
newptr->left=NULL;
newptr->right=NULL;
newptr->rtpoint=temp_ptr;
newptr->x=xmax;
newptr->y=ymax;
find(xmax,1);
temp_ptr->rtpoint=newptr;
}
}
fclose(fp);
printf("Tree created successfully\nPreorder traversal follows\n");
preorder(root);
printf("\nEnter the test rectangle co-ordinates seperated by comas\n");
scanf("%d,%d,%d,%d",&xmin,&ymin,&xmax,&ymax);
if(xmin>xmax) {
temp=xmin;
xmin=xmax;
xmax=temp;
temp=ymin;
ymin=ymax;
ymax=temp;
}
find(xmin,0);
find(xmax,0);
bt_free();
return 0;
}


Sample input file
6 6 11 11
0 0 2 2
9 9 12 12
60 0 70 100
7 2 8 12

1 comment:

  1. hello :-)

    I have some question with the program.

    If the test rectangle is (0,0,50,50)

    the program will output (6,6,11,11) (0,0,2,2) and (12,12,9,9) but lost (7,2,8,12)

    ReplyDelete