previous up next Dissertation Thomas Binder contents
 Previous: 3.4.3 Jump-and-Walk   Up: 3.4 Core Data-Structure Layer   Next: 3.4.5 Binary-Tree

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.


previous up next   contents
 Previous: 3.4.3 Jump-and-Walk   Up: 3.4 Core Data-Structure Layer   Next: 3.4.5 Binary-Tree
2003-03-27