CGAL 4.12.1  2D Arrangements

#include <CGAL/Arr_landmarks_point_location.h>
The Arr_landmarks_point_location
class implements a Jump & Walk algorithm, where special points, referred to as "landmarks", are chosen in a preprocessing stage, their place in the arrangement is found, and they are inserted into a datastructure that enables efficient nearestneighbor search (a Kdtree). Given a query point, the nearest landmark is located and a "walk" strategy is applied from the landmark to the query point.
There are various strategies to select the landmark set in the arrangement, where the strategy is determined by the Generator
template parameter. The following landmarkgenerator classes are available:
Arr_landmarks_vertices_generator
 The arrangement vertices are used as the landmarks set.
Arr_random_landmarks_generator
 \( n\) random points in the bounding box of the arrangement are chosen as the landmarks set.
Arr_halton_landmarks_generator
 \( n\) Halton points in the bounding box of the arrangement are chosen as the landmarks set.
Arr_middle_edges_landmarks_generator
 The midpoint of each arrangement edge is computed, and the resulting set of points is used as the landmarks set. This generator can be applied only for arrangements of line segments.
Arr_grid_landmarks_generator
 The Arr_landmarks_vertices_generator
class is the default generator and used if no Generator
parameter is specified.
It is recommended to use the landmarks pointlocation strategy when the application frequently issues pointlocation queries on a rather static arrangement that the changes applied to it are mainly insertions of curves and not deletions of them.