Editing Quadtree (section)

==Mesh generation using quadtrees==
This section summarizes a chapter from a book by Har-Peled and de Berg et al.<ref name=":2">{{Cite book|title=Geometric approximation algorithms|last=Har-Peled|first=S.|publisher=Mathematical Surveys and Monographs Vol. 173, American mathematical society|year=2011|chapter=Good Triangulations and Meshing}}</ref><ref>{{Cite book|title=Computational Geometry Algorithms and Applications|last1=de Berg|first1=M.|last2=Cheong|first2=O.|last3=van Kreveld|first3=M.|last4=Overmars|first4=M. H.|publisher=Springer-Verlag|year=2008|edition=3rd|chapter=Quadtrees Non-Uniform Mesh Generation}}</ref>

[[Mesh generation]] is essentially the [[point-set triangulation|triangulation of a point set]] for which further processing may be performed. As such, it is desirable for the resulting triangulation to have certain properties (like non-uniformity, triangles that are not "too skinny", large triangles in sparse areas and small triangles in dense ones, etc.) to make further processing quicker and less error-prone. Quadtrees built on the point set can be used to create meshes with these desired properties.
[[File:Fig-mesh-gen-balanced-leaves.svg|thumb|A balanced leaf has at most one corner in a side.]]
Consider a leaf of the quadtree and its corresponding cell <math>v</math>. We say <math>v</math> is ''balanced'' (for mesh generation) if the cell's sides are intersected by the corner points of neighbouring cells at most once on each side. This  means that the quadtree levels of leaves adjacent to <math>v</math> differ by at most one from the level of <math>v</math>. When this is true for all leaves, we say the whole quadtree is balanced (for mesh generation).

Consider the cell <math>v</math> and the <math>5\times 5</math> neighbourhood of same-sized cells centred at <math>v</math>. We call this neighbourhood the ''extended cluster''. We say the quadtree is ''well-balanced'' if it is balanced, and for every leaf <math>u</math> that contains a point of the point set, its extended cluster is also in the quadtree and the extended cluster contains no other point of the point set.

Creating the mesh is done as follows:
# Build a quadtree on the input points.
# Ensure the quadtree is balanced. For every leaf, if there is a neighbour that is too large, subdivide the neighbour. This is repeated until the tree is balanced. We also make sure that for a leaf with a point in it, the nodes for each leaf's extended cluster are in the tree.
# For every leaf node <math>v</math> that contains a point, if the extended cluster contains another point, we further subdivide the tree and rebalance as necessary. If we needed to subdivide, for each child <math>u</math> of <math>v</math> we ensure the nodes of <math>u</math>'s extended cluster are in the tree (and re-balance as required).
# Repeat the previous step until the tree is well-balanced.
# Transform the quadtree into a triangulation.
We consider the corner points of the tree cells as vertices in our triangulation. Before the transformation step we have a bunch of boxes with points in some of them. The transformation step is done in the following manner: for each point, warp the closest corner of its cell to meet it and triangulate the resulting four quadrangles to make "nice" triangles (the interested reader is referred to chapter 12 of Har-Peled<ref name=":2" /> for more details on what makes "nice" triangles).

The remaining squares are triangulated according to some simple rules. For each regular square (no points within and no corner points in its sides), introduce the diagonal. Due to the way in which we separated points with the well-balancing property, no square with a corner intersecting a side is one that was warped. As such, we can triangulate squares with intersecting corners as follows. If there is one intersected side, the square becomes three triangles by adding the long diagonals connecting the intersection with opposite corners. If there are four intersected sides, we split the square in half by adding an edge between two of the four intersections, and then connect these two endpoints to the remaining two intersection points. For the other squares, we introduce a point in the middle and connect it to all four corners of the square as well as each intersection point.

At the end of it all, we have a nice triangulated mesh of our point set built from a quadtree.