advanced |
The Pm_walk_along_a_line_point_location<Planar_map> class implements a walk-along-a-line algorithm which improves the naive one. Unlike the naive algorithm which goes over all the edges of the planar map, the walk algorithm starts with the unbounded face and ``walks'' along the zone of the vertical ray emanating from the query point. This reduces the number of halfedges that are traversed in a query. Like the naive strategy, the walk strategy does not use an additional structure. The updating operations are empty and therefore modifying operations such as split_edge and merge_edge take constant time.
#include <CGAL/Pm_walk_along_line_point_location.h>
advanced |