CGAL 4.7  2D Arrangements

Modules  
CGAL::insert()  
Functions  
template<class GeomTraitsA , class GeomTraitsB , class GeomTraitsRes , class TopTraitsA , class TopTraitsB , class TopTraitsRes , class OverlayTraits >  
void  CGAL::overlay (const Arrangement_2< GeomTraitsA, TopTraitsA > &arr1, const Arrangement_2< GeomTraitsB, TopTraitsB > &arr2, Arrangement_2< GeomTraitsRes, TopTraitsRes > &arr_res, OverlayTraits &ovl_tr) 
Computes the overlay of two arrangements arr1 and arr2 , and sets the output arrangement res to represent the overlaid arrangement. More...  
template<typename Traits , typename Dcel1 , typename Dcel2 , typename ResDcel , typename OverlayTraits >  
void  CGAL::overlay (const Arrangement_with_history_2< Traits, Dcel1 > &arr1, const Arrangement_with_history_2< Traits, Dcel2 > &arr2, Arrangement_with_history_2< Traits, ResDcel > &res, OverlayTraits &ovl_tr) 
Computes the overlay of two arrangements with history arr1 and arr2 , and sets the output arrangement with history res to represent the overlaid arrangement. More...  
template<typename Traits , typename Dcel , typename OutputIterator >  
OutputIterator  CGAL::decompose (const Arrangement_2< Traits, Dcel > &arr, OutputIterator oi) 
Produces the symbolic vertical decomposition of a given arrangement, performing a batched vertical rayshooting query from all arrangement vertices, such that every vertex is associated with a pair of objects, one corresponds to the arrangement feature that lies below it, and the other corresponds to the feature that lies above it. More...  
template<class GeomTraits , class TopTraits , class Curve , class PointLocation >  
bool  CGAL::do_intersect (Arrangement_on_surface_2< GeomTraits, TopTraits > &arr, const Curve &c, const PointLocation &pl) 
Checks if a given curve or \( x\)monotone curve intersects an existing arrangement's edges or vertices. More...  
template<typename Traits , typename Dcel , typename PointLocation >  
Arrangement_2< Traits, Dcel > ::Halfedge_handle  CGAL::insert_non_intersecting_curve (Arrangement_2< Traits, Dcel > &arr, const typename Traits::X_monotone_curve_2 &xc, const PointLocation &pl=walk_pl) 
Inserts a given \( x\)monotone curve into a given arrangement, where the interior of the given curve is disjoint from all existing arrangement vertices and edges. More...  
template<typename Traits , typename Dcel , InputIterator >  
void  CGAL::insert_non_intersecting_curves (Arrangement_2< Traits, Dcel > &arr, InputIterator first, InputIterator last) 
Inserts a set of \( x\)monotone curves in a given range into a given arrangement. More...  
template<typename Traits , typename Dcel , typename PointLocation >  
Arrangement_2< Traits, Dcel > ::Vertex_handle  CGAL::insert_point (Arrangement_2< Traits, Dcel > &arr, const typename Traits::Point_2 &p, const PointLocation &pl=walk_pl) 
Inserts a given point into a given arrangement. More...  
template<typename Traits , typename Dcel >  
bool  CGAL::is_valid (const Arrangement_2< Traits, Dcel > &arr) 
Checks the validity of a given arrangement. More...  
template<typename Traits , typename Dcel >  
Arrangement_2< Traits, Dcel > ::Face_handle  CGAL::remove_edge (Arrangement_2< Traits, Dcel > &arr, typename Arrangement_2< Traits, Dcel >::Halfedge_handle e) 
Removes an edge given by one of the twin halfedges that forms it, from a given arrangement. More...  
template<typename Traits , typename Dcel >  
bool  CGAL::remove_vertex (Arrangement_2< Traits, Dcel > &arr, typename Arrangement_2< Traits, Dcel >::Vertex_handle v) 
Attempts to removed a given vertex from a given arrangement. More...  
template<class GeomTraits , class TopTraits , class OutputIterator , class PointLocation >  
OutputIterator  CGAL::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. More...  
template<class Traits , class Dcel >  
Size  CGAL::remove_curve (Arrangement_with_history_2< Traits, Dcel > &arr, typename Arrangement_with_history_2< Traits, Dcel >::Curve_handle ch) 
Removes a given curve from a given arrangement. More...  
OutputIterator CGAL::decompose  (  const Arrangement_2< Traits, Dcel > &  arr, 
OutputIterator  oi  
) 
Produces the symbolic vertical decomposition of a given arrangement, performing a batched vertical rayshooting query from all arrangement vertices, such that every vertex is associated with a pair of objects, one corresponds to the arrangement feature that lies below it, and the other corresponds to the feature that lies above it.
The output of this function can be readily used for inserting vertical walls and physically decomposing the arrangement into pseudotrapezoids. To do this, it is convenient to process the vertices in an ascending \( xy\)lexicographic order. The visible objects are therefore returned through an output iterator, which pairs each finite arrangement vertex with the two features it "sees", such that the vertices are given in ascending \( xy\)lexicographic order.
Produces the symbolic vertical decomposition of the arr
arrangement. More precisely, it performs a batched vertical rayshooting query from all arrangement vertices, such that every vertex is associated with a pair of objects, one corresponding to the arrangement feature that lies below it, while the other corresponds to the feature that lies above it. The query results are returned through the output iterator, which pairs each finite arrangement vertex with a pair of Object
s, the first represents the feature below the vertex, and the second represents the feature that lies above it. Each Object
may be one of the following:
Halfedge_const_handle
, if the vertex is located above (or below) an edge. The given halfedge is always directed from right to left. In case there is no concrete edge below (or above) the vertex, and the arrangement is unbounded, then the object returned is a fictitious halfedge. Face_const_handle
, in case there is no edge below (or above) the vertex, and the arrangement is bounded. Vertex_const_handle
, in case the vertex is located vertically above (or below) another arrangement vertex. The function returns a pasttheend iterator for its output sequence.
Requirements
OutputIterator::value_type
must be pair<Arrangement_2::Vertex_const_handle, pair<Object, Object> >
.
#include <CGAL/Arr_vertical_decomposition_2.h>
bool CGAL::do_intersect  (  Arrangement_on_surface_2< GeomTraits, TopTraits > &  arr, 
const Curve &  c,  
const PointLocation &  pl  
) 
Checks if a given curve or \( x\)monotone curve intersects an existing arrangement's edges or vertices.
If the give curve is not an \( x\)monotone curve then the function subdivides the given curve into \( x\)monotone subcurves and isolated vertices . Each subcurve is in turn checked for intersection. The function uses the zone algorithm to check if the curve intersects the arrangement. First, the curve's left endpoint is located. Then, its zone is computed starting from its left endpoint location. The zone computation terminates when an intersection with an arrangement's edge/vertex is found or when the right endpoint is reached.
A given pointlocation object is used for locating the left endpoint of the given curve in the existing arrangement. By default, the function uses the "walk along line" pointlocation strategy  namely an instance of the class Arr_walk_along_line_point_location<Arrangement_2<Traits,Dcel> >
.
Checks if the given curve or \( x\)monotone curve c
intersects edges or vertices of the existing arrangement arr
.
pl
must be attached to the given arrangement arr
.Requirements
c
is \( x\)monotone then the instantiated GeomTraits
class must model the ArrangementXMonotoneTraits_2
concept. If c
is a curve then the instantiated GeomTraits
class must model the ArrangementTraits_2
concept. That is, it should define the Curve_2
type, and support its subdivision into \( x\)monotone subcurves (and perhaps isolated points). pl
, must model the ArrangementPointLocation_2
concept. #include <CGAL/Arrangement_2.h>
Arrangement_2<Traits,Dcel>::Halfedge_handle CGAL::insert_non_intersecting_curve  (  Arrangement_2< Traits, Dcel > &  arr, 
const typename Traits::X_monotone_curve_2 &  xc,  
const PointLocation &  pl = walk_pl 

) 
Inserts a given \( x\)monotone curve into a given arrangement, where the interior of the given curve is disjoint from all existing arrangement vertices and edges.
Under this assumption, it is possible to locate the endpoints of the given curve in the arrangement, and use one of the specialized insertion memberfunctions of the arrangement according to the results. The insertion operations creates a single new edge, that is, two twin halfedges, and the function returns a handle for the one directed lexicographically in increasing order (from left to right).
A given pointlocation object is used for answering the two pointlocation queries on the given curve endpoints. By default, the function uses the "walk along line" pointlocation strategy  namely, an instance of the class Arr_walk_along_line_point_location<Arrangement_2<Traits,Dcel> >
.
pl
must be attached to the given arrangement arr
.Requirements
Traits
class must model the restricted ArrangementBasicTraits_2
concept, as no intersections are computed. pl
must model the ArrangementPointLocation_2
concept. #include <CGAL/Arrangement_2.h>
void CGAL::insert_non_intersecting_curves  (  Arrangement_2< Traits, Dcel > &  arr, 
InputIterator  first,  
InputIterator  last  
) 
Inserts a set of \( x\)monotone curves in a given range into a given arrangement.
The insertion is performed in an aggregated manner, using the sweepline algorithm. The input curves should be pairwise disjoint in their interior and pairwise interiordisjoint from all existing arrangement vertices and edges.
Requirements
Traits
class must model the ArrangementBasicTraits_2
concept, as no intersections are computed. InputIterator::value_type
must be Traits::X_monotone_curve_2
#include <CGAL/Arrangement_2.h>
Arrangement_2<Traits,Dcel>::Vertex_handle CGAL::insert_point  (  Arrangement_2< Traits, Dcel > &  arr, 
const typename Traits::Point_2 &  p,  
const PointLocation &  pl = walk_pl 

) 
Inserts a given point into a given arrangement.
It uses a given pointlocation object to locate the given point in the given arrangement. If the point conincides with an existing vertex, there is nothing left to do; if it lies on an edge, the edge is split at the point. Otherwise, the point is contained inside a face, and is inserted as an isolated vertex inside this face. By default, the function uses the "walk along line" pointlocation strategy  namely, an instance of the class Arr_walk_along_line_point_location<Arrangement_2<Traits,Dcel> >
. In either case, the function returns a handle for the vertex associated with the point.
pl
must be attached to the given arrangement arr
.Requirements
Traits
class must model the ArrangementXMonotoneTraits_2
concept. Not all expressions listed by this concept are required. In fact the traits class must model the ArrangementBasicTraits_2
concept, and support the splitting functionality. pl
, must model the ArrangementPointLocation_2
concept. #include <CGAL/Arrangement_2.h>
bool CGAL::is_valid  (  const Arrangement_2< Traits, Dcel > &  arr) 
Checks the validity of a given arrangement.
Invokes the member function arr.is_valid()
to verify the topological correctness of the arrangement. Then it performs additional validity tests. It checks that all \( x\)monotone curves associated with arrangement edges are pairwise disjoint in their interior. Then it makes sure that all holes and all isolated vertices are located within the proper arrangement faces. Note that the test carried out by this function may take a considerable amount of time; it is recommended to be used only for debugging purposes.
Requirements
The instantiated traits class must model the concept ArranagmentXMonotoneTraits_2
.
#include <CGAL/Arrangement_2.h>
void CGAL::overlay  (  const Arrangement_2< GeomTraitsA, TopTraitsA > &  arr1, 
const Arrangement_2< GeomTraitsB, TopTraitsB > &  arr2,  
Arrangement_2< GeomTraitsRes, TopTraitsRes > &  arr_res,  
OverlayTraits &  ovl_tr  
) 
Computes the overlay of two arrangements arr1
and arr2
, and sets the output arrangement res
to represent the overlaid arrangement.
Computes the overlay of two input arrangement objects, and returns the overlaid arrangement. All three arrangements can be instantiated with different geometric traits classes and different Dcel classes (encapsulated in the various topologytraits classes). The geometry traits of the resulting arrangement is used to construct the resulting arrangement. This means that all the types (e.g., Traits::Point_2
, Traits::Curve_2
, and Traits::Point_2
) of both input arrangements have to be convertible to the types in the resulting arrangement. A given overlaytraits object is used to properly construct the overlaid Dcel that represents the resulting arrangement.
res
does not refer to either arr1
or arr2
(that is, "self overlay" is not supported).ovl_tr
must model the OverlayTraits
concept, which is able to construct records of the ResDcel
class on the basis of the Dcel1
and Dcel2
records that induce them.OverlayTraits
#include <CGAL/Arr_overlay_2.h>
void CGAL::overlay  (  const Arrangement_with_history_2< Traits, Dcel1 > &  arr1, 
const Arrangement_with_history_2< Traits, Dcel2 > &  arr2,  
Arrangement_with_history_2< Traits, ResDcel > &  res,  
OverlayTraits &  ovl_tr  
) 
Computes the overlay of two arrangements with history arr1
and arr2
, and sets the output arrangement with history res
to represent the overlaid arrangement.
The function also constructs a consolidated set of curves that induce res
.
Computes the overlay of two input arrangement objects, and returns the overlaid arrangement. All three arrangements can be instantiated with different geometric traits classes and different Dcel classes (encapsulated in the various topologytraits classes). The geometry traits of the resulting arrangement is used to construct the resulting arrangement. This means that all the types (e.g., Traits::Point_2
, Traits::Curve_2
, and Traits::Point_2
) of both input arrangements have to be convertible to the types in the resulting arrangement. A given overlaytraits object is used to properly construct the overlaid Dcel that represents the resulting arrangement.
res
does not refer to either arr1
or arr2
(that is, "self overlay" is not supported).ovl_tr
must model the OverlayTraits
concept, which is able to construct records of the ResDcel
class on the basis of the Dcel1
and Dcel2
records that induce them.OverlayTraits
#include <CGAL/Arr_overlay_2.h>
Size CGAL::remove_curve  (  Arrangement_with_history_2< Traits, Dcel > &  arr, 
typename Arrangement_with_history_2< Traits, Dcel >::Curve_handle  ch  
) 
Removes a given curve from a given arrangement.
The curve is specified by its handle ch
, from the arrangement arr
, by deleting all the edges it induces. The function returns the number of deleted edges.
#include <CGAL/Arrangement_with_history_2.h>
Arrangement_2<Traits,Dcel>::Face_handle CGAL::remove_edge  (  Arrangement_2< Traits, Dcel > &  arr, 
typename Arrangement_2< Traits, Dcel >::Halfedge_handle  e  
) 
Removes an edge given by one of the twin halfedges that forms it, from a given arrangement.
Once the edge is removed, if the vertices associated with its endpoints become isolated, they are removed as well. The call remove_edge(arr, e)
is equivalent to the call arr.remove_edge (e, true, true)
. However, this free function requires that Traits
be a model of the refined concept ArrangementXMonotoneTraits_2
, which requires merge operations on \( x\)monotone curves. If one of the endvertices of the given edge becomes redundant after the edge is removed (see remove_vertex()
for the definition of a redundant vertex), it is removed, and its incident edges are merged. If the edgeremoval operation causes two faces to merge, the merged face is returned. Otherwise, the face to which the edge was incident before the removal is returned.
Requirements
ArrangementXMonotoneTraits_2
. #include <CGAL/Arrangement_2.h>
bool CGAL::remove_vertex  (  Arrangement_2< Traits, Dcel > &  arr, 
typename Arrangement_2< Traits, Dcel >::Vertex_handle  v  
) 
Attempts to removed a given vertex from a given arrangement.
The vertex can be removed if it is either an isolated vertex, (and has no incident edge,) or if it is a redundant vertex. That is, it has exactly two incident edges, whose associated curves can be merged to form a single \( x\)monotone curve. The function returns a boolean value that indicates whether it succeeded removing the vertex from the arrangement.
Requirements
Traits
class must model the ArrangementXMonotoneTraits_2
concept. Not all expressions listed by this concept are required. In fact the traits class must model the ArrangementBasicTraits_2
concept and support the merging functionality. #include <CGAL/Arrangement_2.h>
OutputIterator CGAL::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 arrangement's vertices, edges and faces that the \( x\)monotone curve intersects. The order of the objects is the order that they are discovered when traversing the \( x\)monotone curve from left to right.
A given pointlocation object is used for answering pointlocation queries during the insertion process. By default, the function uses the "walk along line" pointlocation strategy  namely an instance of the class Arr_walk_along_line_point_location<Arrangement_2<Traits,Dcel> >
.
Compute the zone of the given \( x\)monotone curve c
in the arrangement arr
.
pl
must be attached to the given arrangement arr
.Requirements
GeomTraits
class must model the ArrangementXMonotoneTraits_2
concept. pl
, must model the ArrangementPointLocation_2
concept. #include <CGAL/Arrangement_2.h>