在我的Quadtree中插入点问题

Question

我做了一个Quadtree，并且正在将点插入其中，为了确保它起作用，我制作了一种方法，以显示我第一个矩形中所有点的x和y如果将此矩形分为矩形，它也显示了这些矩形。但是我有一个问题。解决方案可能很简单，但我找不到。

代码：

main.cpp

#include "QTree.h"
using namespace std;
int main(int argc, char const *argv[])
{
    Rectangle rect1 = {0, 0, 500, 500};
    QTree arbre(rect1);
    Point point;
    for(int i = 0; i < 5; i ++)
    {
        point.x = 10;
        point.y = 10;
        arbre.Insert(point);
    }
    arbre.AfficherPoints();
    return 0;
}

qtree.h

#ifndef _QTREE_H
#define _QTREE_H
#define CAPACITE_MAX     4
struct Point
{
    int x;
    int y;
};
struct Rectangle
{
    int x;
    int y;
    long w;
    long h;
};
class QTree
{
public:
    QTree(Rectangle r);
    ~QTree();
    void Insert(Point p);
    bool Contient(const Point &p) const;
    void AfficherPoints() const;
private:
    void m_Diviser();
    Rectangle m_rect;
    Point *m_points[CAPACITE_MAX];
    QTree *m_fils[4];
};
#endif

qtree.cpp

#include "QTree.h"
#include <iostream>
QTree::QTree(Rectangle r) 
{
    m_rect = r;
    for(int i = 0; i < CAPACITE_MAX; i ++)
    {
        m_points[i] = nullptr;
    }
    for(int i = 0; i < 4; i ++)
    {
        m_fils[i] = nullptr;
    }
}
QTree::~QTree() 
{
    for(int i = 0; i < CAPACITE_MAX; i ++)
    {
        delete(m_points[i]);
    }
    for(int i = 0; i < 4; i ++)
    {
        delete(m_fils[i]);
    }
}
void QTree::m_Diviser()
{
    Rectangle nw, ne, sw, se;
    nw = {m_rect.x, m_rect.y, m_rect.w/2, m_rect.h/2};
    m_fils[0] = new QTree(nw);
    ne = {m_rect.x + m_rect.w/2, m_rect.y, m_rect.w/2, m_rect.h/2};
    m_fils[1] = new QTree(ne);
    sw = {m_rect.x, m_rect.y + m_rect.h/2, m_rect.w/2, m_rect.h/2};
    m_fils[2] = new QTree(sw);
    se = {m_rect.x + m_rect.w/2, m_rect.y + m_rect.h/2, m_rect.w/2, m_rect.h/2};
    m_fils[3] = new QTree(se);
}
bool QTree::Contient(const Point &p) const
{
    // retourne Vrai si le poitn peut etre dans le rectangle ou pas en tenant compte de ses coordonnes uniquement
    // std::cout << p.x << " " << p.y << std::endl;
    return((p.x >= m_rect.x && p.x < m_rect.x + m_rect.w) //x
            && (p.y >= m_rect.y && p.y < m_rect.y + m_rect.h)); // y
}
void QTree::Insert(Point p)
{
    if(m_points[CAPACITE_MAX - 1] == nullptr) // Si il reste de la place pour le point
    {
        for(int i = 0; i < CAPACITE_MAX; i ++) // on lui trouve une place
        {
            if(m_points[i] == nullptr)
            {
                m_points[i] = &p;  // on l'ajoute
                return; // return : on ajoute le point une seule fois pas plus
            }
        }
    } else { // Sinon on insert le poitn dans un des rectangles fils
        if(m_fils[0] == nullptr) m_Diviser(); // On verifie que le rectangle principale a bien ete divisé
        for(int i = 0; i < 4; i ++) // On parcourt les rectangles fils pour ajouter le point
        {
            if(m_fils[i]->Contient(p))
            {
                m_fils[i]->Insert(p); // Si les coordonnees du point son dans le rect fils on le met dedans
                return; // pas besoin de regarder les autres rect
            }
        }
    }
}
void QTree::AfficherPoints() const
{
    for(int i = 0; i < CAPACITE_MAX; i ++)
    {
        if(m_points[i] != nullptr) 
        {
            std::cout << i << " : Point(" << m_points[i]->x << ", " << m_points[i]->y << ")" << std::endl;
        } else {
            std::cout << i << " : Vide" << std::endl;
        }
    }
    if(m_fils[0] != nullptr)
    {
        for(int i = 0; i < 4; i ++)
        {
            m_fils[i]->AfficherPoints();
        }
    }
}

结果：

0 : Point(10, 10)
1 : Point(10, 10)
2 : Point(10, 10)
3 : Point(10, 10)
0 : Point(4201500, 4218999) // Should have been Point(10, 10)
1 : Vide
2 : Vide 
3 : ...

Answer 1

您正在存储一个指向通过值传递的参数的指针：

m_points[i] = &p;  // on l'ajoute

QTree::Insert返回该变量被破坏，您最终有一个无效的指针。

要么按值存储您的点：

Point m_points[CAPACITE_MAX];

或在存储重点时制作副本：

m_points[i] = new Point(p);  // on l'ajoute