can you explain in very much detail about how quadtrees work ? Can you give an e

Question

can you explain in very much detail about how quadtrees work ? Can you give an example implementation of a quadtree class ?

Explanation / Answer

Quadtrees are 2D data structures, useful for efficient representation of 2D data (such as images), and lookup in a 2D space (where are those monsters?) In this tutorial, we focus on the implementation of quad trees that represent 2D data efficiently; that is, where quadtrees can be used to compress data. Although quadtrees can be used with a variety of data types, we will focus on colour data (images) in this tutorial. In part 2 we will look at more general applications, such as occupancy maps and force fields. We also look at the properties of data that determines whether it is suitable to represent as a quadtree. Quadtrees take advantage of the fact that cells in a grid are often the same as adjacent cells – for example, a green pixel is very likely surrounded by other green pixels. Thus, we do not need a data point for every pixel, as we do when we use a grid – we can use a single point for an entire section of the grid. EXAMPLE: //------------------------------------- // MAIN //------------------------------------- int _tmain(int argc, _TCHAR* argv[]) { // Obtain all the points from the CSV file ReadCSV("input_01.csv"); // Initialize the root node Node* rootNode = new Node(0, 0, 512, 512); const int rootNumPoints = g_pointArray.size(); for(int i = 0; i pointArray.push_back(g_pointArray[i]); } // Create the quadTree BuildQuadTree(rootNode); getch(); delete rootNode; return 0; } //------------------------------------- // BUILD QUAD TREE //------------------------------------- void BuildQuadTree(Node* n) { if(n->pointArray.size() > POINT_THRESHOLD) { for(int i = 0; i < 4; i++) { Node* nodeIn = new Node(0, 0, 0, 0); nodeIn = BuildNode(n->child[i], n, i); BuildQuadTree(nodeIn); } } } //------------------------------------- // BUILD NODE //------------------------------------- Node* BuildNode(Node* n, Node* nParent, int index) { cout posX = nParent->posX + (nParent->posX / 2); n->posY = nParent->posY; break; case 2: // Bottom right n->posX = nParent->posX + (nParent->posX / 2); n->posY = nParent->posY + (nParent->posY / 2); break; case 3: // Bottom left n->posX = nParent->posX; n->posY = nParent->posY + (nParent->posY / 2); break; } // Width and height of the child node is simply 1/2 of the parent node's width and height n->width = nParent->width / 2; n->height = nParent->height / 2; // The points within the child node are also based on the index, similiarily to the position const int numParentPoints = nParent->pointArray.size(); switch(index) { case 0: // Top left for(int i = 0; i pointArray[i].x < (nParent->width / 2) ) && (nParent->pointArray[i].y < (nParent->height / 2) ) ) { // Add the point to the child node's point array n->pointArray.push_back(nParent->pointArray[i]); } } break; case 1: // Top right for(int i = 0; i pointArray[i].x > (nParent->width / 2) ) && (nParent->pointArray[i].y < (nParent->height / 2) ) ) { // Add the point to the child node's point array n->pointArray.push_back(nParent->pointArray[i]); } } break; case 2: // Bottom right for(int i = 0; i pointArray[i].x > (nParent->width / 2) ) && (nParent->pointArray[i].y > (nParent->height / 2) ) ) { // Add the point to the child node's point array n->pointArray.push_back(nParent->pointArray[i]); } } break; case 3: // Bottom left for(int i = 0; i pointArray[i].x < (nParent->width / 2) ) && (nParent->pointArray[i].y > (nParent->height / 2) ) ) { // Add the point to the child node's point array n->pointArray.push_back(nParent->pointArray[i]); } } break; } return n; }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.