What is a Quad Tree?

A quaternary tree, also known as a quadtree, is a tree-like data structure with four sub-blocks on each node. Quaternary trees are often used in the analysis and classification of two-dimensional spatial data. It divides the data into four quadrants. The data range can be square or rectangular or any other shape.

A quad-tree is a data structure that is a data structure with up to four subtrees per node.

Quadtrees are the only suitable algorithm for locating pixels in a two-dimensional picture. Because in two-dimensional space (graphs are often described), planar pixels can be repeatedly divided into four parts, and the depth of the tree is determined by the complexity of pictures, computer memory, and graphics.

Quadtrees can be used to place and

• Decomposable into its own blocks

• Each block has node capacity. When a node reaches its maximum capacity, the node splits

• Tree-like data structures are distinguished according to the quaternary tree method

Quaternary trees can be classified using their data form representation. The items in the data form are: area, point, line, and curve. Quaternary trees can also be classified, regardless of whether the shape of the tree is independent of the processed rank data. The morphology of some quaternary trees is shown below ^[1]

1. Point Quadtree

The point quadtree is similar to the KD tree. The difference between the two is that in the point quadtree, the space is divided into four rectangles. The four different polygons are: SW, NW, SE, NE. The search process is similar to the KD tree. When a point is included in the search range, it is recorded. When a subtree and the search range overlap, it is passed through.

2.PR Quad Tree (Point Region Quadtree)

The PR quadtree is a variant of the point quadtree, which does not use points in the data set to split the space. In the PR quadtree, each time a space is divided, a square is divided into four equal sub-squares, which are performed sequentially until the content of each square does not exceed a given bucket amount (such as an object).

3.MX Quad Tree

The space is divided into four rectangles. The four different polygons are: SW, NW, SE, NE. Each time the space is divided, a square is divided into four equal sub-squares, which are performed sequentially until the content of each square does not exceed a given bucket amount (such as an object).

All data is at the same depth of the quadtree, and multiple points can be connected by a pointer.

4. Quadtree index based on fixed grid division

In the quadtree, the spatial element ID is recorded in each leaf node covered by its outer envelope rectangle, but when the four sibling nodes of the same father are to record the spatial element ID, only The spatial element identification is recorded on the father node, and advances to the upper level according to this rule.

5. Linear sortable quadtree index

First, the quadtree is decomposed into a binary tree, that is, a layer of virtual nodes is inserted between the parent node layer and the child node layer. The virtual nodes are not used to record the spatial elements, and then the nodes are processed in the order of traversal tree Encoding, including the virtual nodes added ^[2]

• Image representation

• Spatial index.

• Efficient collision detection in two dimensions.

• Hidden surface determination of terrain data.

• Stores scattered data, such as spreadsheets, or formatted information with some matrix calculations.

• Multidimensional field solution. (Computational Fluid Dynamics, Electromagnetics)

• Life game simulation program ^[3] .