\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.5 - 2D Periodic Triangulations
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Periodic_2_triangulation_hierarchy_2< PTr > Class Template Reference
Main Classes

#include <CGAL/Periodic_2_triangulation_hierarchy_2.h>

Inherits from

PTr.

Definition

The class Periodic_2_triangulation_hierarchy_2 implements a triangulation augmented with a data structure which allows fast point location queries.

Parameters

It is templated by a parameter which must be instantiated by one of the CGAL periodic triangulation classes. In the current implementation, only Periodic_2_Delaunay_triangulation_2 is supported for PTr.

Template Parameters
PTr::Vertexhas to be a model of the concept Periodic_2TriangulationHierarchyVertexBase_2.
PTr::Geom_traitshas to be a model of the concept Periodic_2DelaunayTriangulationTraits_2.

Inheritance

Periodic_2_triangulation_hierarchy_2 offers exactly the same functionalities as PTr. Most of them (point location, insertion, removal \( \ldots\) ) are overloaded to improve their efficiency by using the hierarchical 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 hierarchical structure and reading it from the file will result in an ordinary triangulation whose efficiency will be the same as PTr.

Implementation

The data structure is a hierarchy of triangulations. The triangulation at the lowest level is the original triangulation where operations and point location are to be performed. Then at each succeeding level, the data structure stores a triangulation of a small random sample of the vertices of the triangulation at the preceding level. Point location is done through a top-down nearest neighbor query. The nearest neighbor query is first performed naively in the top level triangulation. Then, at each following level, the nearest neighbor at that level is found through a randomized walk performed from the nearest neighbor found at the preceding level. Because the number of vertices in each triangulation is only a small fraction of the number of vertices of the preceding triangulation the data structure remains small and achieves fast point location queries on real data.

See Also
CGAL::Periodic_2_triangulation_hierarchy_vertex_base_2
CGAL::Periodic_2_Delaunay_triangulation_2