Quadrant tree

Quadrant trees can be classified according to the type of data they represent — space, points, lines, curves. They can also be divided according to whether the shape of the tree depends on the order of data processing. Some types of quadrant trees:

Region quadtree

Quadrant trees dividing the space ( English region quadtree ) represent any part of two-dimensional space dividing it into 4 quadrants, sub-quadrants and so on, and each leaf of the tree corresponds to a certain area. Each tree node has either 4 descendants, or they do not exist at all (at the leaves). Space-breaking quadrant trees are not fully trees, since the position of the sub-quadrants is data independent. A more correct name is prefix trees ( English trie ).

A tree of height n can be used to represent an image consisting of 2 ⁿ × 2 ⁿ pixels, where each pixel has a value of 0 or 1. The root of the tree represents the entire area of ​​the image. If not all pixels are just zeros or only ones, it breaks. In this case, each sheet corresponds to a set of pixels - either only from zeros or only from ones.

Space-breaking quadrant trees can also be used to represent the variable resolution of a data set. For example, temperature information can be stored in the form of a quadrant tree, each node of which stores the average temperature of the daughter nodes.

If a tree is used to represent many points (for example, the latitude and longitude of the positions of any cities), the areas are divided up until the leaves contain no more than one point.

Point quadtree

Quadtree trees that store point information ( English point quadtree ) - a type of binary trees used to store information about points on the plane. The shape of the tree depends on the data order. The use of such trees is very effective in comparing the ordered points of the plane, and the processing time is O (log n) .

Node structure

A node of a quadrant tree that stores information about points on a plane is similar to a node of a binary tree with the caveat that the node of the first has four descendants (one for each quadrant) instead of two (“right” and “left”). The node key consists of two components (for x and y coordinates). Thus, the tree node contains the following information:

• 4 pointers: quad ['NW'] , quad ['NE'] , quad ['SW'] , and quad ['SE'] ,
• point described as follows:
  • key key , usually expresses x and y coordinates,
  • value , for example, name.

Edge quadtree

Quadtree trees that store line information ( edge quadtree ) are used to describe lines and curves. The curves are described by exact approximations by dividing the cells into very small ones. This can lead to an unbalanced tree, which will mean problems with indexing.

Polygonal map quadtree

Quadrant trees that store information about polygons ( English polygonal map quadtree / PMQuadtree ) may contain information about polygons, including degenerate ones (having isolated vertices or faces) ^[1] .

• Representation of images.
   
• Spatial Databases .
• Effective collision detection in two dimensions.
• Cutting off invisible parts of the landscape ( English view frustum culling ).
• Data storage for tabular or matrix calculations.
• Computations associated with multidimensional fields (in computational fluid dynamics , electromagnetism ).
• Simulation of the game Life ^[2] .
• Calculation of the states of the observed dynamic system ^[3] .
• Analysis of parts of fractal images.

Quadrant trees are a two-dimensional analogue of octant trees .

The following code demonstrates the use of quadrant trees to store point information. Other construction approaches are possible.

Data Structures

The following data structures are intended to be used.

  // Simple structure to represent a point or vector
 struct XY
 {
   float x;
   float y;

   function __construct ( float _x, float _y) {...}
 }

 // Bounding box aligned to the coordinate axes
 // (axis-aligned bounding box, AABB), half dimension centered
 struct AABB
 {
   XY center;
   XY halfDimension;

   function __construct ( XY center, XY halfDimension) {...}
   function containsPoint ( XY p) {...}
   function intersectsAABB ( AABB other) {...}
 }

QuadTree Class

The class represents the 4-tree and the root node.

  class QuadTree
 {
   // Constant - the number of elements that can be stored in one node
   constant int QT_NODE_CAPACITY = 4;

   // Bounding box aligned to the coordinate axes,
   // shows the borders of the tree
   AABB boundary;

   // Points
   Array of XY [size = QT_NODE_CAPACITY] points;

   // Descendants
   QuadTree * northWest;
   QuadTree * northEast;
   QuadTree * southWest;
   QuadTree * southEast;

   // Methods
   function __construct ( AABB _boundary) {...}
   function insert ( XY p) {...}
   function subdivide () {...} // Create 4 descendants dividing the quadrant into 4 equal parts
   function queryRange ( AABB range) {...}
 }

Insert

The following method inserts a point into the corresponding quadrant of the tree, splitting, if necessary.

  class QuadTree {
  ...

   // Insert point
   function insert ( XY p)
   {
     // Ignore non-tree objects
     if (! boundary.containsPoint (p))
       return false ;  // Object cannot be added

     // If there is room, insert 
     if (points.size <QT_NODE_CAPACITY)
     {
       points.append (p);
       return true ;
     }

     // Next, you need to divide the area and add a point to some node
     if (northWest == null )
       subdivide ();

     if (northWest-> insert (p)) return true ;
     if (northEast-> insert (p)) return true ;
     if (southWest-> insert (p)) return true ;
     if (southEast-> insert (p)) return true ;

     // For some reason, the insertion may not succeed (which should not actually happen)
     return false ;
   }
 }

Range entry

The following method finds all points in a certain range.

  class QuadTree
 {
   ...

   // Find points in the range
   function queryRange ( AABB range)
   {
     // Prepare an array for the result
     Array of XY pointsInRange;

     // Cancel if the range does not match the quadrant
     if (! boundary.insersectsAABB (range))
       return pointsInRange;  // Empty list

     // Check objects of the current level
     for ( int p: = 0; p <points.size; p ++)
     {
       if (range.containsPoint (points [p]))
         pointsInRange.append (points [p]);
     }

     // Stop if there are no more children
     if (northWest == null )
       return pointsInRange;

     // Add all descendant points
     pointsInRange.appendArray (northWest-> queryRange (range));
     pointsInRange.appendArray (northEast-> queryRange (range));
     pointsInRange.appendArray (southWest-> queryRange (range));
     pointsInRange.appendArray (southEast-> queryRange (range));

     return pointsInRange;
   }
 }

• Binary Space Split
• K-dimensional tree
• Oktoderevo
• R-tree
• Spatial database

Notes

Sources

1. Raphael Finkel and JL Bentley. Quad Trees: A Data Structure for Retrieval on Composite Keys (Eng.) // Acta Informatica : journal. - 1974. - Vol. 4 , no. 1 . - P. 1-9 . - DOI : 10.1007 / BF00288933 .
2. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry. - 2nd revised. - Springer-Verlag , 2000. - ISBN 3-540-65620-0 . Chapter 14: Quadtrees: pp. 291-306.
3. [ http://infolab.usc.edu/csci585/Spring2008/den_ar/p182-samet.pdf Storing a Collection of Polygons Using

Quadtrees] ( unopened ) (July 1985). Date of treatment March 23, 2012. Archived October 2, 2012.

• Java quad tree example and explanation
• A discussion of the Quadtree and an application
• Considerable discussion and demonstrations of Spatial Indexing
• Example C # code for a quad tree
• Javascript Implementation of the QuadTree used for collision detection
• C ++ Implementation of a QuadTree used for spatial indexing of triangles
• Quadtree Search JavaScript implementation