3.4.4 Quad-tree

The quad-tree is the two-dimensional equivalent of the oct-tree. The space containing the geometry is recursively decomposed into $ 4$ sub-spaces respectively. As with the oct-tree the recursion stops if one of several possible terminal situations occurs.

Figure 3.18: Mesh and resulting quad-tree structure of a triangulated rectangle.
\begin{figure}\centering\psfig{file=pics/quad-rotated, width=0.8\linewidth}\par\end{figure}

Fig. 3.18 depicts a triangulated rectangular area and the resulting leaf structure when the triangles are inserted into the tree.