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 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.

2003-03-27


Previous: 3.4.3 Jump-and-Walk Up: 3.4 Core Data-Structure Layer Next: 3.4.5 Binary-Tree