Archived

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

quadtrees

This topic is 6018 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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