begin of advanced section  advanced  begin of advanced section


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>

Is Model for the Concept


Inherits From


See Also

Discussion of the different point location strategies in the introduction of Planar_map reference pages.

end of advanced section  advanced  end of advanced section