0

I'm currently learning C++ by creating an N body simulation. In order to improve the number of bodies in my simulations I'm trying to implement the Barnes Hut approximation method. I'm actually coding a QuadTree structure in C++ (see below).

In order to construct my tree, I define three classes :

  • class Point : Corresponding to the bodies of my simulation with x and y position as attributes
  • class Rectangle : Corresponding to the properties of the leaves of my tree with position and dimension attributes
  • class QuadTree : Corresponding to my QuadTree and its children (leaves) and a Rectangle object, a vector of Point objects, four leaves objects (QuadTree) and a boolean to say if it contain leaves or not.

I wrote a main function where I define my tree with its boudaries and I divide it to make appear four leaves. Then I ask informations about my tree and the associated subtrees using the function void QuadTree::get_information(). This function allows to show some information about the current tree by displaying if it has children or not (divided), its boudaries, and the points it contains. If it has children, then we apply the function QuadTree::get_information() on each child and we repeat the process.

The problem is that the code give an error of this kind : 

QuadTree : Capacity =  1, Divided (0:False, 1:True) = 0
Rectangle : Center Position = (0, 0), Width = 10, Height = 10
-------------------
-------------------
QuadTree : Capacity =  1, Divided (0:False, 1:True) = 1
Rectangle : Center Position = (0, 0), Width = 10, Height = 10
 Northwest :
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Aborted (core dumped)

It seems that I have a problem of allocation memory. I think I make a bad use of the pointers NW, NE, SW, SE defined in the QuadTree class.

I'm not an expert of the utilisation of the memory allocation on C++, maybe I do a naive error. Do you see something wrong about the way a manage these pointers ? Could you suggest a solution to my problem and make run my algorithm ?

Thank you so much for your time ! :) 

#include <iostream> //For console output/input
#include <fstream>  //Allows to read/write files 
#include <math.h>   //Basic mathematic functions 
#include <vector>   //For dynamic arrays 
#include <string>   //Operations on strings 
#include <tuple>
#include <cmath>
#include <sstream>
using namespace std;

class Point 
{
    public : 

    double get_x();
    double get_y();
    void set_x(double xp);
    void set_y(double yp);

    void get_information();

    private : 

    double x;
    double y;
};

double Point::get_x(){return x;}
double Point::get_y(){return y;}
void Point::set_x(double xp){x = xp;}
void Point::set_y(double yp){y = yp;}


class Rectangle
{
    public : 

    double get_x();
    double get_y();
    double get_w();
    double get_h();

    void set_x(double xc);
    void set_y(double yc);
    void set_w(double wc);
    void set_h(double hc);

    bool contain(Point pt);

    void get_information();

    private : 

    double x; 
    double y; 
    double w;
    double h;
};

double Rectangle::get_x() {return x;}
double Rectangle::get_y() {return y;}
double Rectangle::get_w() {return w;}
double Rectangle::get_h() {return h;}

void Rectangle::set_x(double xc) {x = xc;}
void Rectangle::set_y(double yc) {y = yc;}
void Rectangle::set_w(double wc) {w = wc;}
void Rectangle::set_h(double hc) {h = hc;}


class QuadTree 
{
    public : 

    Rectangle get_boundary(); 
    int get_capacity();
    void set_boundary(double xc, double yc, double wc, double hc);
    void set_rectangle(Rectangle rect);
    void set_capacity(int capacity); 

    void insert(Point pt);
    void subdivide();
    void set_divided();
    bool is_divided();

    void get_information(); 

    QuadTree getNW();
    QuadTree getNE();
    QuadTree getSW();
    QuadTree getSE();
    void setNW(QuadTree nw);
    void setNE(QuadTree ne);
    void setSW(QuadTree sw);
    void setSE(QuadTree se);


    private : 

    QuadTree* NW=NULL;
    QuadTree* NE=NULL;
    QuadTree* SW=NULL;
    QuadTree* SE=NULL;
    Rectangle boundary;
    vector<Point> p;
    bool divided = false;
};

QuadTree QuadTree::getNW(){return *NW;}
QuadTree QuadTree::getNE(){return *NE;}
QuadTree QuadTree::getSW(){return *SW;}
QuadTree QuadTree::getSE(){return *SE;}

void QuadTree::setNW(QuadTree nw){NW=&nw;}
void QuadTree::setNE(QuadTree ne){NE=&ne;}
void QuadTree::setSW(QuadTree sw){SW=&sw;}
void QuadTree::setSE(QuadTree se){SE=&se;}

bool QuadTree::is_divided(){return divided;}
bool Rectangle::contain(Point pt)
{
    return (pt.get_x() > get_x() - get_w() 
    and     pt.get_x() < get_x() + get_w()
    and     pt.get_y() > get_y() - get_h()
    and     pt.get_y() < get_y() + get_h());
}
Rectangle QuadTree::get_boundary() {return boundary;}
void QuadTree::set_boundary(double xc, double yc, double wc, double hc)
{
    boundary.set_x(xc); 
    boundary.set_y(yc);
    boundary.set_w(wc);
    boundary.set_h(hc);
}

//int QuadTree::get_capacity() {return n;}
//void QuadTree::set_capacity(int capacity) {n = capacity;}
void QuadTree::set_divided() {divided = true;}
void QuadTree::set_rectangle(Rectangle rect) {boundary = rect;}
void QuadTree::subdivide()
{
    double xc = boundary.get_x(); 
    double yc = boundary.get_y();
    double wc = boundary.get_w(); 
    double hc = boundary.get_h();
    Rectangle nw;
    nw.set_x(xc-wc/2.);
    nw.set_y(yc+hc/2.);
    nw.set_w(wc/2.);
    nw.set_h(hc/2.);
    Rectangle ne;
    ne.set_x(xc+wc/2.);
    ne.set_y(yc+hc/2.);
    ne.set_w(wc/2.);
    ne.set_h(hc/2.);
    Rectangle sw;
    sw.set_x(xc-wc/2.);
    sw.set_y(yc-hc/2.);
    sw.set_w(wc/2.);
    sw.set_h(hc/2.);
    Rectangle se; 
    se.set_x(xc-wc/2.);
    se.set_y(yc+hc/2.);
    se.set_w(wc/2.);
    se.set_h(hc/2.);

    QuadTree oNW, oNE, oSW, oSE; 
    oNW.set_rectangle(nw); 
    oNE.set_rectangle(ne); 
    oSW.set_rectangle(sw); 
    oSE.set_rectangle(se); 

    setNW(oNW);
    setNE(oNE);
    setSW(oSW);
    setSE(oSE);
    //NW = &oNW;
    //NE = &oNE; 
    //SW = &oSW;
    //SE = &oSE;
}

void QuadTree::insert(Point pt)
{
    if (! get_boundary().contain(pt) ) {cout<<"Hello 1"<<endl; return; }
    if (p.size() < 1) 
    {
        cout<<"Hello 2"<<endl; 
        p.push_back(pt); // Insert element at the end
    }
    else 
    {
        if (!divided)
        {
            QuadTree::subdivide();
            QuadTree::set_divided();   
        }
    }
        NW->insert(pt);
        NE->insert(pt);
        SW->insert(pt);
        SE->insert(pt);
}

void Point::get_information(){cout<<"Point : x = "<<get_x()<<"; y = "<<get_y()<<endl;}
void Rectangle::get_information(){cout<<"Rectangle : Center Position = ("<<get_x()<<", "<<get_y()<<"), Width = "<<get_w()<<", Height = "<<get_h()<<endl;}
void QuadTree::get_information()
{
    cout<<"QuadTree : Capacity = "<<" 1"<<", Divided (0:False, 1:True) = "<<divided<<endl;
    boundary.get_information(); 
    /*cout<<"Points_in : "<<endl; 
    int siz = p.size();
    for (int ii=0; ii<siz; ii++)
    {
        p[ii].get_information();
    }*/
    if (divided) {
    cout<<" Northwest : "<<endl;
    getNW().get_information();
    cout<<" Northeast : "<<endl;
    getNE().get_information();
    cout<<" Southwest : "<<endl;
    getSW().get_information();
    cout<<" Southeast : "<<endl;
    getSE().get_information();
    }
}


int main()
{
    QuadTree tree; 
    tree.set_boundary(0., 0., 10., 10.);
    tree.get_information();
    cout<<"-------------------"<<endl;
    tree.subdivide();
    tree.set_divided();
    cout<<"-------------------"<<endl;
    tree.get_information();
}
Loann Brahimi
  • 1
  • 1
    [`std::bad_alloc`](https://en.cppreference.com/w/cpp/memory/new/bad_alloc) is typically thrown when you run out of available memory (or when your memory becomes to fragmented that it's not possible to allocate a contiguous chunk of the requested size). – Some programmer dude Nov 18 '18 at 07:15
  • 2
    Oh and you have some cases of [*undefined behavior*](https://en.wikipedia.org/wiki/Undefined_behavior) in the code, as you store pointers to local variables whose life-time will end before you dereference those pointers. See e.g. `setNW`. The argument `nw` is a *local variable* which will (in a sense) cease to exist immediately when the function ends, leaving you with an invalid pointer in `NW`. You need to fix all those errors before you can trust any behavior of your programs. Also note that compiler are good at detecting such errors, so please enable more warnings from it. – Some programmer dude Nov 18 '18 at 07:18
  • It is a good case to use a tool like valgrind or some equivalent. In general, for such problems, it directly indicates the line number where the error is. – Damien Nov 18 '18 at 07:25
  • 2
    All this copying by value somehow gives me the impression as if a Java or C# programmer switched to C++, noticed that QuadTree `{ QuadTree nw; };` did not compile, so introduced pointers, managed to adjust the code until fully compiling (taking addresses, dereferencing pointers) - without having understood the nature behind. A good [C++ book](https://stackoverflow.com/a/388282/1312382) might be of great help then. – Aconcagua Nov 18 '18 at 07:36
  • Originally posted on [physics.se]: https://physics.stackexchange.com/q/441603/25301 – Kyle Kanos Nov 20 '18 at 13:03

0 Answers0