c++ - 我的 QuadTree 实现遇到问题

Question

我正致力于用 C++ 实现四叉树，在过去的一段时间里，我一直无法解决我的段错误。问题是，我到处都有指点，但不太确定我的问题出在哪里。我已经用不同的语言实现了我的代码，只是想测试我的 C++ 技能，但这妨碍了我。

代码如下:

四叉树.h:

#ifndef QUADTREE_QUADTREE_H
#define QUADTREE_QUADTREE_H

#endif //QUADTREE_QUADTREE_H
#include <vector>
using namespace std;

class Point
{
public:
    Point(double x, double y);
    double x;
    double y;
};

class Rectangle
{
public:
    Rectangle(double x, double y, double width, double height);
    double x;
    double y;
    double width;
    double height;
    bool contains(Point* p);
};

class QuadTree
{
public:
    QuadTree();
    QuadTree(Rectangle* boundary, int capacity);
    Rectangle* boundary = new Rectangle(200,200,200,200);
    QuadTree* qt = new QuadTree(boundary, 4);
//    Rectangle* boundary;
    Point* p;
    int capacity;
    vector<Point*> points;
    QuadTree* NE;
    QuadTree* NW;
    QuadTree* SW;
    QuadTree* SE;
    bool divided;
    void subdivide();
    void buildTree();
    void insertToNode(Point* p);

};

四叉树.cpp

#include "quadtree.h"
#include <random>


Point::Point(double x, double y)
{
    this->x = x;
    this->y = y;
}

Rectangle::Rectangle(double x, double y, double width, double height)
{
    this->x = x;
    this->y = y;
    this->width = width;
    this->height = height;
}

bool Rectangle::contains(Point* p)
{
    return (p->x > this->x - this->width && p->x < this->x + this->width && p->y > this->y - this->height && p->y < this->y + this->height);
}

QuadTree::QuadTree() {}

QuadTree::QuadTree(Rectangle* boundary, int capacity)
{
    this->boundary = boundary;
    this->capacity = capacity;
    this->divided = false;
}

void QuadTree::subdivide()
{
    Rectangle* nw = new Rectangle(this->boundary->x + this->boundary->width/2, this->boundary->y - this->boundary->height/2, this->boundary->width/2, this->boundary->height/2);
    Rectangle* ne = new Rectangle(this->boundary->x - this->boundary->width/2, this->boundary->y - this->boundary->height/2, this->boundary->width/2, this->boundary->height/2);
    Rectangle* sw = new Rectangle(this->boundary->x + this->boundary->width/2, this->boundary->y + this->boundary->height/2, this->boundary->width/2, this->boundary->height/2);
    Rectangle* se = new Rectangle(this->boundary->x - this->boundary->width/2, this->boundary->y + this->boundary->height/2, this->boundary->width/2, this->boundary->height/2);
    this->NE = new QuadTree(ne, 1);
    this->NW = new QuadTree(nw, 1);
    this->SW = new QuadTree(sw, 1);
    this->SE = new QuadTree(se, 1);
    this->divided = true;
}

void QuadTree::buildTree()
{
    std::random_device rd; // obtain a random number from hardware
    std::mt19937 eng(rd()); // seed the generator
    std::uniform_int_distribution<> distr(0, 199); // define the range

    for(int i = 0; i < 1; i++)
    {
        Point* p = new Point(distr(eng), distr(eng));
        this->qt->insertToNode(p);
    }
}

void QuadTree::insertToNode(Point* p)
{
    if(!this->boundary->contains(p))
    {
        return;
    }

    if(this->points.size() < this->capacity)
    {
        this->points.push_back(p);
    }
    else
    {
        if(!this->divided)
        {
            this->subdivide();
        }

    }
    this->NE->insertToNode(p);
    this->NW->insertToNode(p);
    this->SW->insertToNode(p);
    this->SE->insertToNode(p);
}

Answer 1

您的构造函数将递归调用自身，直到您用完堆栈空间。

您已经为 qt 指定了一个默认值，它将分配另一个 QuadTree 项。由于2参数构造函数没有为qt提供不同的初始值，所以会分配另一个QuadTree对象，递归调用构造函数，直到用完栈空间或内存。

您需要重新考虑qt 正在做什么。有必要吗？