四叉树不会插入节点或拆分

问题描述 投票：1回答：1

我的四叉树的插入功能似乎没有拆分树，它适用于我尝试插入的第一个节点，但不适用于第二个节点。我真的不能指出哪里出错了。如果你们可以帮助我找出为什么它不会插入以及如何解决这个我会很感激。在帖子的底部是输出。

如果您需要更多详细信息，请问，如果问题不够具体，我会在评论中尝试更具体。

该代码基于https://www.geeksforgeeks.org/quad-tree/

我的代码：

    #include <iostream>
using namespace std;

struct Point{
    int x;
    int y;

    Point(int _x, int _y){
        x = _x;
        y = _y;
    }
    Point(){
        x = 0;
        y = 0;
    }
};

struct Square{
    int x, y, w, h;

    Point center;

    Square(int _x, int _y, int _w, int _h){
        x = _x;
        y = _y;
        w = _w;
        h = _h;

        center = Point(x + _w/2, y + _h/2);
    }
    Square(){
        x = 0;
        y = 0;
        w = 0;
        h = 0;

        center = Point(0, 0);
    }
};

struct Node{
    Point point;
    int data;

    Node(Point _p, int _d){
        point = _p;
        data = _d;
    }
    Node(){
        point = Point(0, 0);
        data = 0;
    }

};

class Quad{
    Square area;

    Quad *NE; // top right
    Quad *NW; // top left
    Quad *SE; // bottum right
    Quad *SW; // bottum left

    Node *child; // quad contains a pointer to a node
    bool split;

    public:
        Quad(Square _a){
            area = _a;

            NE = NULL;
            NW = NULL;
            SE = NULL;
            SW = NULL;

            child = NULL;
            split = false;
        }
        Quad(){
            area = Square(0, 0, 0, 0);

            NE = NULL;
            NW = NULL;
            SE = NULL;
            SW = NULL;

            child = NULL;
            split = false;
        }

        bool inRange(Point p){
            return p.x <= area.w + area.x && p.x >= area.x && p.y <= area.h + area.y && p.y > area.y;
        }

        bool insert(Node *c){

            if(area.w >= 1 && area.h >= 1){
                if(child == NULL){
                    child = c;
                    return false;
                } // cant collide if there is nothing to collide with
            }

            if(area.w >= 1 && area.h >= 1 || area.w <= 1 && area.h <= 1){
                if(child != NULL){
                    return true;
                }
            }

            if(child != NULL){
                if(split == false){

                    NW = new Quad( Square(area.x, area.y, area.w/2, area.h/2) );

                    NE = new Quad( Square(area.w/2, area.y, area.w/2, area.h/2) );

                    SW = new Quad( Square(area.x, area.h/2, area.w/2, area.h/2) );

                    SE = new Quad( Square(area.w/2, area.h/2, area.w/2, area.h/2) );

                    split = true;
                    child = NULL;
                }
            }

            if(NW->inRange(c->point)){
                NW->insert(c);
            }
            if(NE->inRange(c->point)){
                NE->insert(c);
            }
            if(SW->inRange(c->point)){
                SW->insert(c);
            }
            if(SE->inRange(c->point)){
                SE->insert(c);
            }


        }

        Node *test(){

            if(child != NULL){
                return child;
            }

            return NULL;
        }

};

int main() {

    Node node_1( Point(10, 10) , 3);
    Node node_2( Point(2, 2) , 2);
    Quad quad( Square(0, 0, 16, 16) );
    cout<<quad.insert(&node_1)<<"\n";
    cout<<quad.insert(&node_2)<<"\n";
    cout<<quad.test();

    return 0;
}
/*Output:
0           this is good
1           this should be a 0
0x23fe14    this should be 0 also
*/

编辑：我对插入函数进行了一些更改，如下所示，但它仍然沿着我希望它没有的路径，因为我不知道该路径意味着什么或如何修复它。

新插入：

bool insert(Node *c){
        if(area.w >= 1 && area.h >= 1){
            cout<<"1\n";
            if(child == NULL){
                cout<<"2\n";
                child = c;
                return 0;
            }
            if(child == c){
                cout<<"3\n";
                return 0;
            }
            if(child != NULL){
                cout<<"4\n";
                if(area.w <= 1 && area.h <= 1){
                    cout<<"5\n";
                    return 0;
                }
                if(split == false){
                    cout<<"6\n";
                    NW = new Quad( Square(area.x, area.y, area.w/2, area.h/2) );

                    NE = new Quad( Square(area.w/2, area.y, area.w/2, area.h/2) );

                    SW = new Quad( Square(area.x, area.h/2, area.w/2, area.h/2) );

                    SE = new Quad( Square(area.w/2, area.h/2, area.w/2, area.h/2) );

                    split = true;
                    child = NULL;
                }
            }
        }


        if(area.center.x < c->point.x){
            cout<<"7\n";

            if(area.center.y < c->point.y){
                cout<<"8\n";
                NE->insert(c);
            }
            if(area.center.y > c->point.y){
                cout<<"9\n";
                SE->insert(c);
            }

        }

        if(area.center.x > c->point.x){
            cout<<"10\n";

            if(area.center.y < c->point.y){
                cout<<"11\n";
                NW->insert(c);
            }
            if(area.center.y > c->point.y){
                cout<<"12\n";
                SW->insert(c);
            }

        }

        cout<<"13\n";
        return 0;

    }
/*output:
1
2    good
0
1
4
6
10
12
1
2
13    shouldn't reach this spot
0
0
0x61feec
0x61fee0

*/

编辑2：抱歉忘记上传我的更新（仅显示主要和插入，因为没有其他更改）代码所以这里是：

Node *insert(Node *c){
        if(area.w >= 1 && area.h >= 1){
            if(child == NULL){
                child = c;
                return child;
            }
            if(child != NULL){
                if(split == false){
                    NW = new Quad( Square(area.x, area.y, area.w/2, area.h/2) );

                    NE = new Quad( Square(area.w/2, area.y, area.w/2, area.h/2) );

                    SW = new Quad( Square(area.x, area.h/2, area.w/2, area.h/2) );

                    SE = new Quad( Square(area.w/2, area.h/2, area.w/2, area.h/2) );

                    split = true;
                }

                if(area.center.x < c->point.x){

                    if(area.center.y < c->point.y){
                        cout<<"NE->";
                        return NE->insert(c);
                    }
                    if(area.center.y > c->point.y){
                        cout<<"SE->";
                        return SE->insert(c);
                    }

                }

                if(area.center.x > c->point.x){

                    if(area.center.y < c->point.y){
                        cout<<"NW->";
                        return NW->insert(c);
                    }
                    if(area.center.y > c->point.y){
                        cout<<"SW->";
                        return SW->insert(c);
                    }

                }

            }

        }

        cout<<"failure\n";
        return NULL;

    }
int main() {

    Node node_1( Point(10, 10) , 3);
    Node node_2( Point(2, 2) , 2);
    Node node_3( Point(6, 6) , 4);
    Node node_4( Point(12, 12) , 6);
    Node node_5( Point(7, 7) , 10);
    Quad quad( Square(0, 0, 16, 16) );
    cout<<quad.insert(&node_1)<<"\nnew node\n";
    cout<<quad.insert(&node_2)<<"\nnew node\n";
    cout<<quad.insert(&node_3)<<"\nnew node\n";
    cout<<quad.insert(&node_4)<<"\nnew node\n";
    cout<<quad.insert(&node_5)<<"\n";
    cout<<quad.test();

    return 0;
}
/*output:    these are good outputs
0x23fdfc
new node
SW->0x23fdf0
new node
SW->SE->0x23fde4
new node
NE->0x23fdd8
new node
SW->SE->NE->0x23fdcc
0x23fdfc
/*

如果有人有任何关于我如何能做得更好的提示，我将不胜感激。

c++ collision-detection
1个回答
0
投票

这里：

      ...
      if(area.center.y > c->point.y){
        cout<<"12\n";
        SW->insert(c);
      }
    }
    cout<<"13\n";
    return 0;
  }

SW->insert(c)调用第二次调用insert(...)，当调用到达return时，控制返回到此调用，而不是调用堆栈中位于其上方的main()。因此，控制权从if声明中消失，然后进入cout<<"13\n"。我建议你在return之后加上SW->insert(c);声明。

这里有一个更严重的问题：

split = true;
child = NULL;

将四元组拆分为新四边形时，将丢弃已存在的节点。我怀疑你的意图。

至于输出的最后几行：

0
0x61feec
0x61fee0

我不知道他们的意思;当我运行你的代码时，它们不会出现。你必须在没有告诉我们的情况下对main做出一些其他的改变。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.