Trying to make a simple rectangle/bin packer in C. Takes a given area and finds placement for any given size rectangle.
About after 4 recursions is when I get the segmentation fault.
#include <stdio.h>
#include <stdlib.h>
typedef struct node_type PackNode;
struct node_type {
int x , y;
int width , height;
int used;
struct node_type *left;
struct node_type *right;
};
typedef struct point_type PackPoint;
struct point_type {
int x,y;
};
PackNode _clone(PackNode *node) {
PackNode clone;
clone.used = 0;
clone.x = node->x;
clone.y = node->y;
clone.width = node->width;
clone.height= node->height;
clone.left = NULL;
clone.right= NULL;
return clone;
}
PackNode root;
int rcount;
PackPoint* recursiveFind(PackNode *node, int w, int h) {
PackPoint rp;
PackPoint *p = NULL;
rcount++;
printf ("rcount = %u\n", rcount);
//left is not null go to left, if left didn't work try right.
if (node->left!=NULL) {
//move down to left branch
p = recursiveFind(node->left, w, h);
if (p!=NULL) {
return p;
} else {
p = recursiveFind(node->right, w, h);
return p;
}
} else {
//If used just return null and possible go to the right branch;
if (node->used==1 || w > node->width || h > node->height) {
return p;
}
//if current node is exact size and hasn't been used it return the x,y of the mid-point of the rectangle
if (w==node->width && h == node->height) {
node->used=1;
rp.x = node->x+(w/2);
rp.y = node->y+(h/2);
p = &rp;
return p;
}
//If rectangle wasn't exact fit, create branches from cloning it's parent.
PackNode l_clone = _clone(node);
PackNode r_clone = _clone(node);
node->left = &l_clone;
node->right = &r_clone;
//adjust branches accordingly, split up the current unused areas
if ( (node->width - w) > (node->height - h) )
{
node->left->width = w;
node->right->x = node->x + w;
node->right->width = node->width - w;
} else {
node->left->height = h;
node->right->y = node->y + h;
node->right->height = node->height - h;
}
p = recursiveFind(node->left, w, h);
return p;
}
return p;
}
int main(void) {
root = malloc(
root.x=0;
root.y=0;
root.used=0;
root.width=1000;
root.height=1000;
root.left=NULL;
root.right=NULL;
int i;
PackPoint *pnt;
int rw;
int rh;
for (i=0;i<10;i++) {
rw = random()%20+1;
rh = random()%20+1;
pnt = recursiveFind(&root, rw, rh);
printf("pnt.x,y: %d,%d\n",pnt->x,pnt->y);
}
return 0;
}
