CGAL 4.7 - 2D Arrangements: Free Functions

\( \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.7 - 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 `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.
- 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

- The instantiated `Traits` class must model the restricted `ArrangementBasicTraits_2` concept, as no intersections are computed.
- The point-location object `pl` must model the `ArrangementPointLocation_2` concept.

`#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

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

`#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

- The instantiated traits class must model the concept `ArrangementXMonotoneTraits_2`.

`#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

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

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

- The instantiated `GeomTraits` class must model the `ArrangementXMonotoneTraits_2` concept.
- The point-location object `pl`, must model the `ArrangementPointLocation_2` concept.

`#include <CGAL/Arrangement_2.h>`