#### Archived

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

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

## 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 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;jAddData(newData) }}

1. 1
2. 2
Rutin
25
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 22
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631764
• Total Posts
3002209
×