class Rect
{
public:
int x = 0, y = 0, w = 100, h = 100;
Rect(int x, int y, int w, int h) :x(x), y(y), w(w), h(h){}
Rect(){};
};
class Point
{
public:
int x = 90, y = 10;
Point(){};
Point(int x, int y) :x(x), y(y){};
};
class QuadTree
{
public:
Rect *rect;
int depth = 0;
vector<QuadTree*> child;
vector<Point*> obj;
void insert(Point* p)
{
obj.push_back(p);
}
void insert(QuadTree* child)
{
if (child == 0)return;
this->child.push_back(child);
}
QuadTree* getByPoint(Point*p)//获取该点的Node
{
if (p->x > rect->x + rect->w && p->y > rect->y + rect->h)return 0;
if (child.size() ==0) return this;
int cx = (rect->x + rect->w) / 2;
int cy = (rect->y + rect->h) / 2;
int index = 0;
if (p->x > cx && p->y > cy)
{
index = 0;
}
else if (p->x<=cx && p->y>=cy)
{
index = 1;
}
else if (p->x <= cx && p->y <= cy)
{
index = 2;
}
else if (p->x>cx&&p->y<cy)
{
index = 3;
}
return child[index]->getByPoint(p);
return 0;
for (int i = 0; i < child.size(); i++)
{
QuadTree * b = child[i]->getByPoint(new Point(p->x / 2, p->y / 2));
if (b == 0)
{
}
else
{
return b->getByPoint(new Point(p->x/2,p->y/2));
}
}
// if (child.size() != 0)return 0;
if (p->x >= rect->x && p->x <= rect->x + rect->w)
{
if (p->y >= rect->y && p->y <= rect->y + rect->h)
{
cout << " find " << endl;
return this;
}
}
return 0;
cout << "root " << rect->x << " " << rect->y << endl;
}
/*QuadTree * getObjs(Rect* rec)
{
QuadTree * n=0;
for (auto & node : child)
{
if (node->getObjs(rec) == 0)
{
n = node;
}
}
if (n)
{
return n->getObjs(rec);
}
return 0;
}*/
Rect** split()
{
Rect ** ret = new Rect *[4];
ret[0] = new Rect;
ret[1] = new Rect;
ret[2] = new Rect;
ret[3] = new Rect;
int x = rect->x;
int y = rect->y;
int w = rect->w;
int h = rect->h;
for (int i = 0; i < 4; i++)
{
ret[i]->h = h / 2;
ret[i]->w = w / 2;
}
ret[0]->x = (x + w) / 2;
ret[0]->y = (y + h) / 2;
ret[1]->x = x;
ret[1]->y =( y+h) / 2;
ret[2]->x = x;
ret[2]->y = y;
ret[3]->x = (x+w) / 2;
ret[3]->y = y;
return ret;
}
};
QuadTree* creater(int depth, Rect* rect)
{
if (depth == 0) return 0;
QuadTree * Parent = new QuadTree;
Parent->depth = depth;
Parent->rect = rect;
Rect ** path4 = Parent->split();
Parent->insert(creater(depth - 1, path4[0]));
Parent->insert(creater(depth - 1, path4[1]));
Parent->insert(creater(depth - 1, path4[2]));
Parent->insert(creater(depth - 1, path4[3]));
return Parent;
}
int main(...)
{
QuadTree *root = creater(4, new Rect(0, 0, 100, 100));
QuadTree* area = root->getByPoint(new Point(14,14));
system("pause");
return 0;
}