Point Location

Classes
class	CGAL::Arr_landmarks_point_location< Arrangement, Generator >
class	CGAL::Arr_naive_point_location< Arrangement >
class	CGAL::Arr_point_location_result< Arrangement >
	A unary metafunction to determine the return type of a point-location or vertical ray-shoot query. More...
class	CGAL::Arr_trapezoid_ric_point_location< Arrangement >
class	CGAL::Arr_walk_along_line_point_location< Arrangement >

Macros
#define	CGAL_ARR_POINT_LOCATION_VERSION
	The macro CGAL_ARR_POINT_LOCATION_VERSION can be used to configure the point-location query API. More...

Functions
template<typename Traits , typename Dcel , typename InputIterator , typename OutputIterator >
OutputIterator	CGAL::locate (const Arrangement_2< Traits, Dcel > &arr, InputIterator points_begin, InputIterator points_end, OutputIterator oi)
	Performs a batched point-location operation on a given arrangement. More...

Macro Definition Documentation

#define CGAL_ARR_POINT_LOCATION_VERSION

The macro CGAL_ARR_POINT_LOCATION_VERSION can be used to configure the point-location query API.

In particular, it determines which version of the result type of the point-location and vertical ray-shooting queries should be used by models of the concepts ArrangementPointLocation_2 and ArrangementVerticalRayShoot_2, and by the free function locate. The CGAL_ARR_POINT_LOCATION_VERSION should be defined before any CGAL header is included.

• CGAL_ARR_POINT_LOCATION_VERSION == 1, the result type is set to be CGAL::Object.
• CGAL_ARR_POINT_LOCATION_VERSION == 2, the result type is set to be boost::variant<Vertex_const_handle,Halfedge_const_handle,Face_const_handle>, where Vertex_const_handle, Halfedge_const_handle, and Face_const_handle are the corresponding nested types in a CGAL::Arrangement_2 instance.

See Also

ArrangementPointLocation_2

ArrangementVerticalRayShoot_2

CGAL::Arr_point_location_result<Arrangement>

#include <CGAL/Arr_point_location_result.h>

Function Documentation

template<typename Traits , typename Dcel , typename InputIterator , typename OutputIterator >

OutputIterator CGAL::locate	(	const Arrangement_2< Traits, Dcel > &	arr,
		InputIterator	points_begin,
		InputIterator	points_end,
		OutputIterator	oi
	)

Performs a batched point-location operation on a given arrangement.

It accepts a range of query points, and locates each point in the arrangement. The query results are returned through the output iterator. Each query result is given as a pair of the query point and an object representing the arrangement feature that contains it, namely a discriminated union container of the bounded types Face_const_handle, Halfedge_const_handle, and Vertex_const_hanlde. The resulting pairs in the output sequence are sorted in increasing \( xy\)-lexicographical order of the query points. The function returns a past-the-end iterator of the output sequence.

Requirements

• InputIterator::value_type must be Arrangement_2::Point_2.
• OutputIterator::value_type must be convertible to std::pair<Arrangement_2::Point_2, Arr_point_location_result<Arrangement_2>::Type>.

A Note on Backwards Compatibility
This function used to return CGAL::Object up to CGAL version 4.2. Starting with CGAL version 4.3 the return type is determined by the metafunction CGAL::Arr_point_location_result. To preserve backwards compatibility CGAL::Object can be constructed from the new return type implicitly, but switching to the new style is recommended. To enable the old style without any overhead, the macro CGAL_ARR_POINT_LOCATION_VERSION can be defined to 1 before any CGAL header is included.

See Also

CGAL::Arr_point_location_result<Arrangement>

CGAL_ARR_POINT_LOCATION_VERSION

#include <CGAL/Arr_batched_point_location.h>

Examples:

Arrangement_on_surface_2/batched_point_location.cpp.