\( \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 Arrangements
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Arr_walk_along_line_point_location< Arrangement > Class Template Reference
Point Location

#include <CGAL/Arr_walk_along_line_point_location.h>

Definition

The Arr_walk_along_line_point_location class implements a very simple point-location (and vertical ray-shooting) strategy that improves the naive one. The algorithm considers an imaginary vertical ray emanating from the query point, and simulates a walk along the zone of this ray, starting from the unbounded face until reaching the query point. In dense arrangements this walk can considerably reduce the number of traversed arrangement edges, with respect to the naïve algorithm.

The walk-along-a-line point-location object (just like the naïve one) does not use any auxiliary data structures. Thus, attaching it to an existing arrangement takes constant time, and any ongoing updates to this arrangement do not affect the point-location object. It is therefore recommended to use the "walk" point-location strategy for arrangements that are constantly changing, especially if the number of issued queries is not large.

Is Model Of:

ArrangementPointLocation_2

ArrangementVerticalRayShoot_2

See Also
ArrangementPointLocation_2
ArrangementVerticalRayShoot_2
CGAL::Arr_point_location_result<Arrangement>
CGAL_ARR_POINT_LOCATION_VERSION
Examples:
Arrangement_on_surface_2/edge_manipulation_curve_history.cpp, Arrangement_on_surface_2/incremental_insertion.cpp, and Arrangement_on_surface_2/vertical_ray_shooting.cpp.