Archived

This topic is now archived and is closed to further replies.

jho

quadtrees

Recommended Posts

I would like to know how to store the 3D data (x,y,z) in a quadtree. Right now I store all my points in a 2D array. I The application would call a function findclosest(x,y, tolerance) to find a closest point in x and y only. Z is ignored. As you can see a linear search through the array is currently done. Is there a way to store this information in a quadtree? I read a tutorial already, but I don''t know where to start. Let''s say a node should contain n number of points, I would need a way to insert a point and restructure the tree at anytime.. It seems very complex to program. So what should I do when my boss suddenly ask me to implement a quadtree on a monday morning?

Share this post


Link to post
Share on other sites
When you add a data item to a leaf node, just check to see if that data will cause the number of items in that node to exceed n. If so, create 4 new child nodes and partition the data between them.

  
const int MaxDataPerNode;

class CQuadtree
{
public:
CQuadtree** child;
CData* data;
int dataCount;

...

void AddData(CData*);
};

void CQuadtree::AddData(CData* newData)
{
if(NULL == child)
{
// this is a leaf node

if(dataCount == MaxDataPerNode)
{
// This new data takes us over the limit.

//Create some child nodes...

child = new CQuadtree*[4];
for(int i = 0;i<4;i++)
child[i] = new CQuadtree;
for(int j = 0;j<dataCount;j++)
AddData(data[i]);
AddData(newData);
delete[] data[];
dataCount = 0;
}
else
{
data[dataCount] = newData;
dataCount++;
}
}
else
{
// determine which of the child nodes the data belongs in

// and call child[i]->AddData(newData)

}
}


Share this post


Link to post
Share on other sites