I implemented Quad as BST, but I try to split it this way, but it's not working well

Question

If wsplit = 1 I want to split base on width, else height.

threshold will be defined should split or not.

tx, ty will be the left top coordinate of the Quad. sx = Width of the original image

It will work like

(tx:ty = 0:0     w = 512,   h = 512,  wsplit = 1) ---> A

after split

(tx:ty =  0 :0     w = 256,   h = 512,  wsplit = 0) ---> B
(tx:ty = 256:0     w = 256,   h = 512,  wsplit = 0) ---> C

will in the BST (Quadtree)

so I did

Quad *split(Image *im, Quad *root, int threshold) {
  if (root == NULL)
    return NULL;
  if (similar(im, root, threshold) == 0){ //this will define should split or not
    int tx = root->tx;;
    int ty = root->ty;
    int w = root->w;
    int h = root->h;
    int wsplit = root->wsplit;
    int sx = root->sx;
    int tx2,ty2,w1,w2,h1,h2;
    if(wsplit==0){
      h1 = (int)floor(h/2);
      h2 = h-h1;
      ty2 = ty+h1;
      wsplit = 1;
    }
    else{
      w1 = (int)floor(w/2);
      w2 = w-w1;
      tx2 = tx+w1;
      wsplit = 0;
    }
    Quad *first = NULL;
    Quad *second = NULL;
    first = new_Quad(tx, ty, w1, h1, wsplit, sx);
    second = new_Quad(tx2, ty2, w2, h2, wsplit, sx);
    root = quad_delete(root, tx, ty);
    root = insert(root, first);
    root = insert(root, second);
  }
  split(im, root->left, threshold);
  split(im, root->right, threshold);
  return root;
}

to split all into half, but I don't know why it's not working.

`floor` in C is a floating-point operation, not what you want when exact answers are critical. It's also pointless because `h/2` was integer division and already [rounds toward zero to an integer](https://stackoverflow.com/questions/3602827/what-is-the-behavior-of-integer-division). So if `h,w` are nonnegative then you can safely just do `h1 = h/2;`. If they could be negative, and rounding toward minus infinity is really what you want, then you write a couple more lines of code to do it with integer arithmetic. — Nate Eldredge, Mar 28 '21 at 21:01

score 2 · Accepted Answer · answered Mar 28 '21 at 20:30

It looks like the issue is that you are forgetting to initialize all variables. You should ensure you initialize all of the variables in both the if and the else part:

if (wsplit == 0) {
    w1 = w;   // was missing
    w2 = w;   // was missing
    h1 = h / 2;
    h2 = h - h1;
    tx1 = tx; // was missing
    tx2 = tx; // was missing
    ty1 = ty; // was missing
    ty2 = ty + h1;
    wsplit = 1;
} else {
    // same issues here
    ...
}

Note that your compiler should warn you about possibly uninitialized variables. If you haven't done so already, enable compiler warnings. Then also fix all the warnings produced by your compiler.

I implemented Quad as BST, but I try to split it this way, but it's not working well

1 Answers1