SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Arrangement_on_surface_2.h File Reference

#include <boost/mpl/assert.hpp>
#include <CGAL/Arr_tags.h>
#include <CGAL/Arr_enums.h>
#include <CGAL/HalfedgeDS_iterator.h>
#include <CGAL/Arrangement_2/Arrangement_2_iterators.h>
#include <CGAL/In_place_list.h>
#include <CGAL/Arr_default_dcel.h>
#include <CGAL/Arr_observer.h>
#include <CGAL/Arr_accessor.h>
#include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h>
#include <CGAL/function_objects.h>
#include <CGAL/Iterator_project.h>
#include <CGAL/Iterator_transform.h>
#include <map>
#include <vector>
#include <algorithm>
#include <CGAL/Arrangement_2/Arrangement_on_surface_2_impl.h>
#include <CGAL/Arrangement_2/Arrangement_on_surface_2_global.h>

Include dependency graph for Arrangement_on_surface_2.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::_Is_concrete_vertex
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::_Is_valid_vertex
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::_Is_valid_halfedge
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::_Is_valid_face
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::_Is_unbounded_face
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::Edge_iterator
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::Edge_const_iterator
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::Unbounded_face_iterator
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::Unbounded_face_const_iterator
struct	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::_Halfedge_to_ccb_circulator
struct	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::_Const_halfedge_to_ccb_circulator
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::Isolated_vertex_iterator
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::Isolated_vertex_const_iterator
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::_Valid_vertex_iterator
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::Vertex
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::Halfedge
class	Arrangement_on_surface_2< GeomTraits_, TopTraits_ >::Face
Functions
template<class GeomTraits , class TopTraits , class Curve , class PointLocation >
void	insert (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, const Curve &c, const PointLocation &pl, typename PointLocation::Point_2 *=0)
template<class GeomTraits , class TopTraits , class Curve >
void	insert (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, const Curve &c)
template<class GeomTraits , class TopTraits , class InputIterator >
void	insert (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, InputIterator begin, InputIterator end)
template<class GeomTraits , class TopTraits >
void	insert (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, const typename GeomTraits::X_monotone_curve_2 &c, const Object &obj)
template<class GeomTraits , class TopTraits , class PointLocation >
Arrangement_on_surface_2 < GeomTraits, TopTraits > ::Halfedge_handle	insert_non_intersecting_curve (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, const typename GeomTraits::X_monotone_curve_2 &c, const PointLocation &pl)
template<class GeomTraits , class TopTraits >
Arrangement_on_surface_2 < GeomTraits, TopTraits > ::Halfedge_handle	insert_non_intersecting_curve (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, const typename GeomTraits::X_monotone_curve_2 &c)
template<class GeomTraits , class TopTraits , class InputIterator >
void	insert_non_intersecting_curves (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, InputIterator begin, InputIterator end)
template<class GeomTraits , class TopTraits >
Arrangement_on_surface_2 < GeomTraits, TopTraits > ::Face_handle	remove_edge (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, typename Arrangement_on_surface_2< GeomTraits, TopTraits >::Halfedge_handle e)
template<class GeomTraits , class TopTraits , class PointLocation >
Arrangement_on_surface_2 < GeomTraits, TopTraits > ::Vertex_handle	insert_point (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, const typename GeomTraits::Point_2 &p, const PointLocation &pl)
template<class GeomTraits , class TopTraits >
Arrangement_on_surface_2 < GeomTraits, TopTraits > ::Vertex_handle	insert_point (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, const typename GeomTraits::Point_2 &p)
template<class GeomTraits , class TopTraits >
bool	remove_vertex (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, typename Arrangement_on_surface_2< GeomTraits, TopTraits >::Vertex_handle v)
template<class GeomTraits , class TopTraits >
bool	is_valid (const Arrangement_on_surface_2< GeomTraits, TopTraits > &arr)
template<class GeomTraits , class TopTraits , class OutputIterator , class PointLocation >
OutputIterator	zone (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, const typename GeomTraits::X_monotone_curve_2 &c, OutputIterator oi, const PointLocation &pl)
template<class GeomTraits , class TopTraits , class OutputIterator >
OutputIterator	zone (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, const typename GeomTraits::X_monotone_curve_2 &c, OutputIterator oi)
template<class GeomTraits , class TopTraits , class Curve , class PointLocation >
bool	do_intersect (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, const Curve &c, const PointLocation &pl)
template<class GeomTraits , class TopTraits , class Curve >
bool	do_intersect (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, const Curve &c)

---

Detailed Description

The header file for the Arrangement_on_surface_2<Traits,Dcel> class.

---

Function Documentation

template<class GeomTraits , class TopTraits , class Curve , class PointLocation >

bool do_intersect	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		const Curve &	c,
		const PointLocation &	pl
	)

Checks if the given curve/x-monotone curve intersects the existing arrangement.

Parameters:

arr	The arrangement.
c	The curve/x-monotone curve.
pi	The point location strategy that is used to locate the starting point.

Returns:

True if the curve intersect the arrangement, false otherwise.

Here is the call graph for this function:

template<class GeomTraits , class TopTraits , class Curve >

bool do_intersect	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		const Curve &	c
	)

Checks if the given curve/x-monotone curve intersects the existing arrangement. Overloaded version with no point location object - the walk point-location strategy is used as default.

Parameters:

arr	The arrangement.
c	The x-monotone curve/curve.

Returns:

True if the curve intersect the arrangement, false otherwise.

Here is the call graph for this function:

template<class GeomTraits , class TopTraits , class Curve , class PointLocation >

void insert	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		const Curve &	c,
		const PointLocation &	pl,
		typename PointLocation::Point_2 *	= 0
	)

Insert a curve or x-monotone curve into the arrangement (incremental insertion). The inserted curve can be x-monotone (or not) and may intersect the existing arrangement.

Parameters:

arr	The arrangement.
cv	The curve to be inserted.
pl	A point-location object associated with the arrangement.

Here is the call graph for this function:

template<class GeomTraits , class TopTraits , class Curve >

void insert	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		const Curve &	c
	)

Insert a curve or x-monotone curve into the arrangement (incremental insertion). The inserted curve can be x-monotone (or not) and may intersect the existing arrangement. The default "walk" point-location strategy is used for the curve insertion.

Parameters:

arr	The arrangement.
cv	The curve to be inserted.

Here is the call graph for this function:

template<class GeomTraits , class TopTraits , class InputIterator >

void insert	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		InputIterator	begin,
		InputIterator	end
	)

Insert a range of curves or x-monotone curves into the arrangement (aggregated insertion). The inserted curves may intersect one another and may also intersect the existing arrangement.

Parameters:

arr	The arrangement.
begin	An iterator for the first curve in the range.
end	A past-the-end iterator for the curve range.

Precondition:

The value type of the iterators must be Curve_2.

Here is the call graph for this function:

template<class GeomTraits , class TopTraits >

void insert	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		const typename GeomTraits::X_monotone_curve_2 &	c,
		const Object &	obj
	)

Insert an x-monotone curve into the arrangement (incremental insertion) when the location of the left endpoint of the curve is known and is given as an isertion hint. The inserted x-monotone curve may intersect the existing arrangement.

Parameters:

arr	The arrangement.
cv	The x-monotone curve to be inserted.
obj	An object that represents the location of cv's left endpoint in the arrangement.

Here is the call graph for this function:

template<class GeomTraits , class TopTraits , class PointLocation >

Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle insert_non_intersecting_curve	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		const typename GeomTraits::X_monotone_curve_2 &	c,
		const PointLocation &	pl
	)

Insert an x-monotone curve into the arrangement, such that the curve interior does not intersect with any existing edge or vertex in the arragement (incremental insertion).

Parameters:

arr	The arrangement.
c	The x-monotone curve to be inserted.
pl	A point-location object associated with the arrangement.

Precondition:

The interior of c does not intersect any existing edge or vertex.

Returns:

A handle for one of the new halfedges corresponding to the inserted curve, directed (lexicographically) from left to right.

Here is the call graph for this function:

Here is the caller graph for this function:

template<class GeomTraits , class TopTraits >

Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle insert_non_intersecting_curve	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		const typename GeomTraits::X_monotone_curve_2 &	c
	)

Insert an x-monotone curve into the arrangement, such that the curve interior does not intersect with any existing edge or vertex in the arragement (incremental insertion). The default point-location strategy is used for the curve insertion.

Parameters:

arr	The arrangement.
c	The x-monotone curve to be inserted.

Precondition:

The interior of c does not intersect any existing edge or vertex.

Returns:

A handle for one of the new halfedges corresponding to the inserted curve, directed (lexicographically) from left to right.

Here is the call graph for this function:

template<class GeomTraits , class TopTraits , class InputIterator >

void insert_non_intersecting_curves	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		InputIterator	begin,
		InputIterator	end
	)

Insert a range of pairwise interior-disjoint x-monotone curves into the arrangement, such that the curve interiors do not intersect with any existing edge or vertex in the arragement (aggregated insertion).

Parameters:

arr	The arrangement.
begin	An iterator for the first x-monotone curve in the range.
end	A past-the-end iterator for the x-monotone curve range.

Precondition:

The value type of the iterators must be X_monotone_curve_2. The curves in the range are pairwise interior-disjoint, and their interiors do not intersect any existing edge or vertex.

Here is the call graph for this function:

Here is the caller graph for this function:

template<class GeomTraits , class TopTraits , class PointLocation >

Arrangement_on_surface_2<GeomTraits, TopTraits>::Vertex_handle insert_point	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		const typename GeomTraits::Point_2 &	p,
		const PointLocation &	pl
	)

Insert a vertex that corresponds to a given point into the arrangement. The inserted point may lie on any existing arrangement feature.

Parameters:

arr	The arrangement.
p	The point to be inserted.
pl	A point-location object associated with the arrangement.

Returns:

A handle to the vertex that corresponds to the given point.

Here is the call graph for this function:

Here is the caller graph for this function:

template<class GeomTraits , class TopTraits >

Arrangement_on_surface_2<GeomTraits, TopTraits>::Vertex_handle insert_point	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		const typename GeomTraits::Point_2 &	p
	)

Insert a vertex that corresponds to a given point into the arrangement. The inserted point may lie on any existing arrangement feature.

Parameters:

arr	The arrangement.
p	The point to be inserted.

Returns:

A handle to the vertex that corresponds to the given point.

Here is the call graph for this function:

template<class GeomTraits , class TopTraits >

bool is_valid

(

const Arrangement_on_surface_2< GeomTraits, TopTraits > &

arr

)

Check the validity of the arrangement. In particular, check that the edegs are disjoint-interior, and the holes are located in their proper position.

Parameters:

arr	The arrangement.

Returns:

Whether the arrangement is valid.

Here is the call graph for this function:

template<class GeomTraits , class TopTraits >

Arrangement_on_surface_2<GeomTraits, TopTraits>::Face_handle remove_edge	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		typename Arrangement_on_surface_2< GeomTraits, TopTraits >::Halfedge_handle	e
	)

Remove an edge from the arrangement. In case it is possible to merge the edges incident to the end-vertices of the removed edge after its deletion, the function performs these merges as well.

Parameters:

arr	The arrangement.
e	The edge to remove (one of the pair of twin halfegdes).

Returns:

A handle for the remaining face.

Here is the call graph for this function:

template<class GeomTraits , class TopTraits >

bool remove_vertex	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		typename Arrangement_on_surface_2< GeomTraits, TopTraits >::Vertex_handle	v
	)

Remove a vertex from the arrangement.

Parameters:

arr	The arrangement.
v	The vertex to remove.

Returns:

Whether the vertex has been removed or not.

Here is the call graph for this function:

template<class GeomTraits , class TopTraits , class OutputIterator , class PointLocation >

OutputIterator zone	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		const typename GeomTraits::X_monotone_curve_2 &	c,
		OutputIterator	oi,
		const PointLocation &	pl
	)

Compute the zone of the given x-monotone curve in the existing arrangement. Meaning, it output the arrangment's vertices, edges and faces that the x-monotone curve intersects.

Parameters:

arr	The arrangement.
c	The x-monotone curve that its zone was computed.
oi	Output iterator of CGAL::Object to insert the zone elements to.
pi	The point location strategy that is used to locate the starting point.

Returns:

The output iterator that the curves were inserted to.

Here is the call graph for this function:

Here is the caller graph for this function:

template<class GeomTraits , class TopTraits , class OutputIterator >

OutputIterator zone	(	Arrangement_on_surface_2< GeomTraits, TopTraits > &	arr,
		const typename GeomTraits::X_monotone_curve_2 &	c,
		OutputIterator	oi
	)

Compute the zone of the given x-monotone curve in the existing arrangement. Overloaded version with no point location object - the walk point-location strategy is used as default.

Parameters:

arr	The arrangement.
c	The x-monotone curve that its zone was computed.
oi	Output iterator of CGAL::Object to insert the zone elements to.

Returns:

The output iterator that the curves were inserted to.

Here is the call graph for this function: