The class Triangulation_hierarchy_3 implements a triangulation augmented with a data structure which allows fast point location queries. As proved in [Dev02], this structure has an optimal behavior when it is built for Delaunay triangulations. It can however be used for other triangulations.
#include <CGAL/Triangulation_hierarchy_3.h>
It is templated by a parameter which must be instantiated by one of the CGAL triangulation classes. In the current implementation, only Delaunay_triangulation_3 is supported for Tr.
Tr::Vertex has to be a model of the concept
TriangulationHierarchyVertexBase_3.
Tr::Geom_traits has to be a model of the concept
DelaunayTriangulationTraits_3.
Tr
Triangulation_hierarchy_3<Tr> offers exactly the same functionalities as Tr. Most of them (point location, insertion, removal...) are overloaded to improve their efficiency by using the hierarchic structure.
Note that, since the algorithms that are provided are randomized, the running time of constructing a triangulation with a hierarchy may be improved when shuffling the data points.
However, the I/O operations are not overloaded. So, writing a hierarchy into a file will lose the hierarchic structure and reading it from the file will result in an ordinary triangulation whose efficiency will be the same as Tr.