Как вырастить это Quadtree на каждом узле - PullRequest
Новая
       23

Как вырастить это Quadtree на каждом узле

0 голосов
/ 26 февраля 2019

Я создал Quadtree, который изначально является единым квадродеревом уровня 2. 

struct qnode {
  int level;
  double xy[2];
  struct qnode *child[4];
};
typedef struct qnode Node;

int main( int argc, char **argv ) {

  Node *head;

  // make the head node
  head = makeNode( 0.0,0.0, 0 );

  // make a tree

  //full level 2 tree
  makeChildren( head );
  makeChildren( head->child[0] );
  makeChildren( head->child[1] );
  makeChildren( head->child[2] );
  makeChildren( head->child[3] );
}

// сделать узел в заданном месте (x, y) и уровне 

Node *makeNode( double x, double y, int level ) {

  int i;

  Node *node = (Node *)malloc(sizeof(Node));

  node->level = level;

  node->xy[0] = x;
  node->xy[1] = y;

  for( i=0;i<4;++i )
    node->child[i] = NULL;

  return node;
}

// разделить листовые узлы на 4 дочерних элемента 

void makeChildren( Node *parent ) {

  double x = parent->xy[0];
  double y = parent->xy[1];

  int level = parent->level;

  double hChild = pow(2.0,-(level+1));

  parent->child[0] = makeNode( x,y, level+1 );
  parent->child[1] = makeNode( x+hChild,y, level+1 );
  parent->child[2] = makeNode( x+hChild,y+hChild, level+1 );
  parent->child[3] = makeNode( x,y+hChild, level+1 );

  return;
}

Как пройти через каждый узел и вырастить дерево равномерно в каждом узле?

1 Ответ

0 голосов
/ 26 февраля 2019

Рекурсивный подход кажется правильным.Примерно так: 

void growTree(Node * root) {
    for(int i=0; i<4; i++) {
        if(root->child[i] == NULL) root->child[i] = makeNode(0,0,root->level+1);
        else growTree(root->child[i]);
    }
}

Я бы также предложил изменить дизайн makeNode.Примерно так: 

Node *makeNode(double x, double y, Node * node) {
    int level = node->level;
    // copy old body of makeNode here
}

Также измените на это: 

typedef struct Node {
  int level;
  double xy[2];
  struct Node *child[4];
} Node;

Нет причин иметь разные имена для struct Node и Node.Если вы хотите скрыть определение struct Node, используйте это: 

struct Node {
  int level;
  double xy[2];
  struct Node *child[4];
};

typedef struct Node Node;
...