\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.11 - 2D Arrangements
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Modules | Functions
Free Functions
2D Arrangement Reference

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 ray-shooting 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...
 

Function Documentation

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 ray-shooting 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 pseudo-trapezoids. 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 ray-shooting 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 Objects, 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.
  • An empty object, in case the vertex is the top end-vertex of a vertical edge, we define there is no feature below it. Similarly, if it is the bottom end-vertex of a vertical edge, we define that there is no feature above it.

The function returns a past-the-end 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>

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.

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 point-location 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" point-location 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.

Precondition
If provided, pl must be attached to the given arrangement arr.

Requirements

  • If 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).
  • The point-location object pl, must model the ArrangementPointLocation_2 concept.

#include <CGAL/Arrangement_2.h>

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.

Under this assumption, it is possible to locate the endpoints of the given curve in the arrangement, and use one of the specialized insertion member-functions 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 point-location object is used for answering the two point-location queries on the given curve endpoints. By default, the function uses the "walk along line" point-location strategy - namely, an instance of the class Arr_walk_along_line_point_location<Arrangement_2<Traits,Dcel> >.

Precondition
If provided, pl must be attached to the given arrangement arr.

Requirements

#include <CGAL/Arrangement_2.h>

Examples:
Arrangement_on_surface_2/bgl_primal_adapter.cpp, Arrangement_on_surface_2/dcel_extension.cpp, Arrangement_on_surface_2/dcel_extension_io.cpp, Arrangement_on_surface_2/face_extension.cpp, Arrangement_on_surface_2/face_extension_overlay.cpp, Arrangement_on_surface_2/incremental_insertion.cpp, Arrangement_on_surface_2/observer.cpp, Arrangement_on_surface_2/overlay.cpp, and Arrangement_on_surface_2/unbounded_non_intersecting.cpp.
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.

The insertion is performed in an aggregated manner, using the sweep-line algorithm. The input curves should be pairwise disjoint in their interior and pairwise interior-disjoint from all existing arrangement vertices and edges.

Requirements

  • The instantiated 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>

Examples:
Arrangement_on_surface_2/global_insertion.cpp, and Arrangement_on_surface_2/predefined_kernel_non_intersecting.cpp.
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.

It uses a given point-location 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" point-location 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.

Precondition
If provided, pl must be attached to the given arrangement arr.

Requirements

#include <CGAL/Arrangement_2.h>

template<typename Traits , typename Dcel >
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>

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.

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 topology-traits 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 overlay-traits object is used to properly construct the overlaid Dcel that represents the resulting arrangement.

Precondition
res does not refer to either arr1 or arr2 (that is, "self overlay" is not supported).
The overlay-traits object 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.
See Also
OverlayTraits

#include <CGAL/Arr_overlay_2.h>

Examples:
Arrangement_on_surface_2/face_extension_overlay.cpp, Arrangement_on_surface_2/overlay.cpp, and Arrangement_on_surface_2/overlay_unbounded.cpp.
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.

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 topology-traits 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 overlay-traits object is used to properly construct the overlaid Dcel that represents the resulting arrangement.

Precondition
res does not refer to either arr1 or arr2 (that is, "self overlay" is not supported).
The overlay-traits object 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.
See Also
OverlayTraits

#include <CGAL/Arr_overlay_2.h>

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.

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>

Examples:
Arrangement_on_surface_2/edge_manipulation_curve_history.cpp.
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.

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 end-vertices 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 edge-removal 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

#include <CGAL/Arrangement_2.h>

Examples:
Arrangement_on_surface_2/global_removal.cpp, and Arrangement_on_surface_2/observer.cpp.
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.

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

#include <CGAL/Arrangement_2.h>

Examples:
Arrangement_on_surface_2/global_removal.cpp.
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.

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 point-location object is used for answering point-location queries during the insertion process. By default, the function uses the "walk along line" point-location 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.

Precondition
If provided, pl must be attached to the given arrangement arr.

Requirements

#include <CGAL/Arrangement_2.h>