How to make quadtree algorithm

Question

i'm making an algorithm called Quadtree, so i've tried this code that i made but the output is incorrect

input 8 8
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 0 0
0 0 1 1 1 0 0 0

output
0

the code i've tried

#include <iostream>
#include <string>

using namespace std;

int m[128][128];
int nJawaban;
string jawaban[128*128];

bool homogen(int r, int c, int k) {
   int val = m[r][c];
   for (int i = r; i < r+k; i++) {
      for (int j = c; j < c+k; j++) {
         if (m[i][j] != val) {
            return false;
         }
      }
   }
   return true;
}
// i think it's here
void quadtree(int r, int c, int k, string s){
   if (m[r][c] == m[r-1][c-1]) {
      if (m[r][c] == 1) {
         jawaban[nJawaban] = "1" + s;
         nJawaban++;
      }
   } else {
      quadtree(r, c, k/2, s+"0");
      quadtree(r, c+(k/2), k/2, s+"1");
      quadtree(r, c, r+k-1, s+"0");
      quadtree(r, c, r+k-1, s+"1");
   }
}

int main(){
   int r, c;
   scanf("%d %d", &r, &c);

   int maxRc = max(r, c);
   int pow2 = 1;
   while (pow2 < maxRc){
      pow2 *= 2;
   }

   for (int i = 0; i < pow2; i++) {
      for (int j = 0; j < pow2; j++) {
         m[i][j] = 0;
      }
   }

   for (int i = 0; i < r; i++){
      for (int j = 0; j < c; j++){
         scanf("%d", &m[i][j]);
      }
   }

   nJawaban = 0;
   quadtree(0, 0, pow2, "");

   printf("%d\n", nJawaban);
   for (int i = 0; i < nJawaban; i++) {
      printf("%s\n", jawaban[i].c_str());
   }

   return 0;
}

input:
8 8
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 0 0
0 0 1 1 1 0 0 0

expected output:
11
112
113
1211
1212
1213
123
130
131
1320
1321
1322

note: some of the var name is written in indonesian language and i'm trying to make this code without (using namespace std) and also fix the code

i've watched youtube video and reading some stackoverflow answer
https://www.youtube.com/watch?v=xFcQaig5Z2A
Efficient (and well explained) implementation of a Quadtree for 2D collision detection
nevertheless i can't correct my mistake but i can point out where the mistake is. My question here is how to correct this mistake or even provide better algorithm
edit: it's still didn't work

Maybe the blatant warning issued for `if (m[r][c] == m[r][c])` always being true because it's literally a comparison-to-self has something to do with your problem. — WhozCraig, Jun 22 '21 at 06:47
from what i interpret from the videos i've watched the base case of this recursion is when all of the quadtree is homogeneous — HD-coders64, Jun 22 '21 at 06:49
That has nothing to do with what I just said. Look at the code. At what point do you expect `if (m[r][c] == m[r][c])` to be *false* and thus lead to the `else` case which is where the recursion actually transpires? I.e. do you understand nothing in the else-block containing your recursion is ever being called? — WhozCraig, Jun 22 '21 at 06:51
"My question here is how to correct this mistake or even provide better algorithm." Try understanding what you wrote, or start again from scratch in the place where you know the mistake is. Go over the code line by line and understand what it is doing. To improve it there is no secret but practice, fail and learn from your mistakes. — cstml, Jun 22 '21 at 06:59
I honestly don't understand the confusion. Do you *ever* expect `if (m[r][c] == m[r][c])` to be *false* ? If so, *how* ? If not, then look at your code and consider what the ramifications of that assessment are? The `else` block mated to that always-true `if` condition will *never* execute. That `else` block is where *all* your recursion takes place. Run your code in a debugger and set a breakpoint on any line within that `else` block the program will *never* break on breakpoint. I do not know how I can explain it any better than that, including the debug option for you to see for yourself. — WhozCraig, Jun 22 '21 at 08:46
@WhozCraig bear with me, i've changed the code and still got 0 output — HD-coders64, Jun 22 '21 at 11:16
D-E-B-U-G-G-E-R . Seriously. Take a **small** known-answer test (KAT) and walk it through your program. Set a breakpoint on your recursions and you'll see they're *not being called*. The entire else-block is never entered. Further, with the given change your code invokes undefined behavior. when `r` and `c` are initially zero (0) per the initial invoke with `quadtree(0, 0, pow2, "");` the ensuing `if (m[r][c] == m[r-1][c-1])` will be synonymous with `if (m[0][0] == m[-1][-1])` which is clearly not good. — WhozCraig, Jun 22 '21 at 11:23

How to make quadtree algorithm

0 Answers0