В настоящее время я изучаю C ++, создавая симуляцию N тела.Чтобы улучшить количество тел в моём моделировании, я пытаюсь реализовать метод приближения Барнс-Хата.Я на самом деле кодирую структуру QuadTree в C ++ (см. Ниже).
Для построения моего дерева я определяю три класса:
- Точка класса: Соответствует телам моего моделирования с позициями x и y в качестве атрибутов
- class Rectangle: Соответствует свойствам листьев моего дерева с атрибутами позиции и измерения
- class QuadTree: Соответствует моему QuadTree и его дочерним элементам (листьям) и объекту Rectangle, вектору объектов Point, четырем листамобъекты (QuadTree) и логическое значение, чтобы сказать, содержит ли оно листья или нет.
Я написал основную функцию, в которой я определяю свое дерево с его границами и делю его так, чтобы на нем были четыре листа.Затем я запрашиваю информацию о моем дереве и связанных поддеревьях, используя функцию void QuadTree :: get_information ().Эта функция позволяет отображать некоторую информацию о текущем дереве, отображая, есть ли у него дочерние элементы (разделенные), его границы и точки, которые оно содержит.Если у него есть дочерние элементы, мы применяем функцию QuadTree :: get_information () к каждому дочернему элементу и повторяем процесс.
Проблема в том, что код выдает ошибку такого типа:
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)
Кажется, у меня проблема с выделением памяти.Я думаю, что я неправильно использую указатели NW, NE, SW, SE, определенные в классе QuadTree.
Я не эксперт по использованию распределения памяти на C ++, возможно, я делаю наивную ошибку.Вы видите что-то неправильное в том, как управлять этими указателями?Не могли бы вы предложить решение моей проблемы и запустить мой алгоритм?
Большое вам спасибо за ваше время!:)
#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=≠}
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();
}