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

Question

我的四叉树插入函数似乎没有拆分树，它对我尝试插入的第一个节点工作正常，但对第二个节点不起作用。我真的无法指出哪里出了问题。如果你们能帮我找出为什么它不会插入以及我如何解决这个问题，我将不胜感激。 post 的底部是输出。

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

代码基于 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：抱歉忘记上传我的更新（只显示 main 和 insert 因为没有其他改变）代码所以这里是：

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
/*

如果有人对我如何改进它有任何建议，我将不胜感激。

Answer 1

这里：

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

SW->insert(c) 调用对 insert(...) 的第二次调用，当该调用到达 return 时，控制 returns 到 this 调用，而不是调用堆栈中位于其上方的 main() 。因此，控制权从 if 语句传递出去并继续进行到 cout<<"13\n"。我建议你在 SW->insert(c);.

之后加上一个 return 语句

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

split = true;
child = NULL;

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

至于输出的最后几行：

0
0x61feec
0x61fee0

我不知道他们是什么意思；当我运行你的代码时，它们不会出现。您一定是在没有告诉我们的情况下对 main 进行了一些其他更改。

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

quadtree wont insert a node or split

c++

collision-detection