2D Arrangements
Reference Manual

Ron Wein, Efi Fogel, Baruch Zukerman, Dan Halperin, Eric Berberich, and Oren Zalzman

Given a set C of planar curves, the arrangement A(C) is the subdivision of the plane induced by the curves in C into maximally connected cells. The cells can be 0-dimensional (vertices), 1-dimensional (edges) or 2-dimensional (faces).

The class Arrangement_2<Traits,Dcel> encapsulates a data structure that maintains arrangements of arbitrary bounded planar curves. It comes with a variety of algorithms that operate on planar arrangement, such as point-location queries and overlay computations, which are implemented as peripheral classes or as free (global) functions.

32.14   Classified Reference Pages

Enumerations

CGAL::Arr_parameter_space
CGAL::Arr_curve_end
CGAL::Arr_halfedge_direction

Tags

CGAL::Arr_oblivious_side_tag
CGAL::Arr_open_side_tag

Concepts

ArrangementDcel
ArrangementDcelWithRebind
ArrangementDcelVertex
ArrangementDcelHalfedge
ArrangementDcelFace
ArrangementDcelHole
ArrangementDcelIsolatedVertex
 
ArrangementBasicTraits_2
ArrangementLandmarkTraits_2
ArrangementXMonotoneTraits_2
ArrangementTraits_2
ArrangementOpenBoundaryTraits_2
 
ArrangementInputFormatter
ArrangementOutputFormatter
ArrangementWithHistoryInputFormatter
ArrangementWithHistoryOutputFormatter  
ArrangementPointLocation_2
ArrangementVerticalRayShoot_2

Geometric Object Concepts

ArrTraits::Point_2
ArrTraits::XMonotoneCurve_2
ArrTraits::Curve_2

Function Object Concepts

ArrTraits::CompareX_2
ArrTraits::CompareXy_2
ArrTraits::ConstructMinVertex_2
ArrTraits::ConstructMaxVertex_2
ArrTraits::IsVertical_2
ArrTraits::CompareYAtX_2
ArrTraits::CompareYAtXLeft_2
ArrTraits::CompareYAtXRight_2
ArrTraits::Equal_2
ArrTraits::ParameterSpaceInX_2
ArrTraits::ParameterSpaceInY_2
ArrTraits::CompareXAtLimit_2
ArrTraits::CompareXNearLimit_2
ArrTraits::CompareYNearBoundary_2
ArrTraits::Intersect_2
ArrTraits::Split_2
ArrTraits::AreMergeable_2
ArrTraits::Merge_2
ArrTraits::MakeXMonotone_2
ArrTraits::Approximate_2
ArrTraits::ConstructXMonotoneCurve_2

Classes

CGAL::Arrangement_2<Traits,Dcel>
CGAL::Arr_accessor<Arrangement>
CGAL::Arr_observer<Arrangement>
CGAL::Arrangement_with_history_2<Traits,Dcel>
 
CGAL::Arrangement_2<Traits,Dcel>::Vertex
CGAL::Arrangement_2<Traits,Dcel>::Halfedge
CGAL::Arrangement_2<Traits,Dcel>::Face
CGAL::Arr_dcel_base<V,H,F>
CGAL::Arr_default_dcel<Traits>
CGAL::Arr_face_extended_dcel<Traits,FData,V,H,F>
CGAL::Arr_extended_dcel<Traits,VData,HData,FData,V,H,F>
 
CGAL::Arr_segment_traits_2<Kernel>
CGAL::Arr_non_caching_segment_traits_2<Kernel>
CGAL::Arr_linear_traits_2<Kernel>
CGAL::Arr_polyline_traits_2<SegmentTraits>
CGAL::Arr_circle_segment_traits_2<Kernel>
CGAL::Arr_line_arc_traits_2<CircularKernel>
CGAL::Arr_circular_arc_traits_2<CircularKernel>
CGAL::Arr_circular_line_arc_traits_2<CircularKernel>
CGAL::Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>
CGAL::Arr_rational_function_traits_2<AlgebraicKernel_d_1>
CGAL::Arr_Bezier_curve_traits_2<RatKernel,AlgKernel,NtTraits>
CGAL::Arr_algebraic_segment_traits_2<Coefficient>
CGAL::Arr_curve_data_traits_2<Tr,XData,Mrg,CData,Cnv>
CGAL::Arr_consolidated_curve_data_traits_2<Traits,Data>
 
CGAL::Arr_text_formatter<Arrangement>
CGAL::Arr_face_extended_text_formatter<Arrangement>
CGAL::Arr_extended_dcel_text_formatter<Arrangement>
CGAL::Arr_with_history_text_formatter<ArrFormatter>
 
CGAL::Arr_naive_point_location<Arrangement>
CGAL::Arr_walk_along_line_point_location<Arrangement>
CGAL::Arr_trapezoid_ric_point_location<Arrangement>
CGAL::Arr_landmarks_point_location<Arrangement,Generator>

Tags

CGAL::Arr_oblivious_side_tag
CGAL::Arr_open_side_tag

Functions

CGAL::is_valid
CGAL::insert
CGAL::insert_non_intersecting_curve
CGAL::insert_non_intersecting_curves
CGAL::insert_point
CGAL::remove_edge
CGAL::remove_vertex
CGAL::locate
CGAL::decompose
CGAL::overlay
CGAL::read
CGAL::write
CGAL::remove_curve
CGAL::operator<< (go there)
CGAL::operator>> (go there)

32.15   Alphabetical List of Reference Pages

ArrangementBasicTraits_2
ArrangementDcelFace
ArrangementDcelHalfedge
ArrangementDcelHole
ArrangementDcelIsolatedVertex
ArrangementDcelVertex
ArrangementDcelWithRebind
ArrangementDcel
ArrangementInputFormatter
ArrangementLandmarkTraits_2
ArrangementOpenBoundaryTraits_2
ArrangementOutputFormatter
ArrangementPointLocation_2
ArrangementTraits_2
ArrangementVerticalRayShoot_2
ArrangementWithHistoryInputFormatter
ArrangementWithHistoryOutputFormatter
ArrangementXMonotoneTraits_2
Arrangement_2<Traits,Dcel>::Face
Arrangement_2<Traits,Dcel>::Halfedge
Arrangement_2<Traits,Dcel>::Vertex
Arrangement_2<Traits,Dcel>
Arrangement_with_history_2<Traits,Dcel>
ArrTraits::Approximate_2
ArrTraits::AreMergeable_2
ArrTraits::CompareXAtLimit_2
ArrTraits::CompareXNearLimit_2
ArrTraits::CompareXy_2
ArrTraits::CompareX_2
ArrTraits::CompareYAtXLeft_2
ArrTraits::CompareYAtXRight_2
ArrTraits::CompareYAtX_2
ArrTraits::CompareYNearBoundary_2
ArrTraits::ConstructMaxVertex_2
ArrTraits::ConstructMinVertex_2
ArrTraits::ConstructXMonotoneCurve_2
ArrTraits::Curve_2
ArrTraits::Equal_2
ArrTraits::Intersect_2
ArrTraits::IsVertical_2
ArrTraits::MakeXMonotone_2
ArrTraits::Merge_2
ArrTraits::ParameterSpaceInX_2
ArrTraits::ParameterSpaceInY_2
ArrTraits::Point_2
ArrTraits::Split_2
ArrTraits::XMonotoneCurve_2
Arr_accessor<Arrangement>
Arr_algebraic_segment_traits_2<Coefficient>
Arr_Bezier_curve_traits_2<RatKernel,AlgKernel,NtTraits>
Arr_circle_segment_traits_2<Kernel>
Arr_circular_arc_traits_2<CircularKernel>
Arr_circular_line_arc_traits_2<CircularKernel>
Arr_conic_traits_2<RatKernel,AlgKernel,NtTraits>
Arr_consolidated_curve_data_traits_2<Traits,Data>
Arr_curve_data_traits_2<Tr,XData,Mrg,CData,Cnv>
Arr_curve_end
Arr_dcel_base<V,H,F>
Arr_default_dcel<Traits>
Arr_default_overlay_traits<Arrangement>
Arr_extended_dcel<Traits,VData,HData,FData,V,H,F>
Arr_extended_dcel_text_formatter<Arrangement>
Arr_extended_face<FaceBase,FData>
Arr_extended_halfedge<HalfedgeBase,HData>
Arr_extended_vertex<VertexBase,VData>
Arr_face_extended_dcel<Traits,FData,V,H,F>
Arr_face_extended_text_formatter<Arrangement>
Arr_face_overlay_traits<Arr_A,Arr_B,Arr_R,OvlFaceData>
Arr_halfedge_direction
Arr_landmarks_point_location<Arrangement,Generator>
Arr_linear_traits_2<Kernel>
Arr_line_arc_traits_2<CircularKernel>
Arr_naive_point_location<Arrangement>
Arr_non_caching_segment_basic_traits_2<Kernel>
Arr_non_caching_segment_traits_2<Kernel>
Arr_oblivious_side_tag
Arr_observer<Arrangement>
Arr_open_side_tag
Arr_parameter_space
Arr_polyline_traits_2<SegmentTraits>
Arr_rational_function_traits_2<AlgebraicKernel_d_1>
Arr_segment_traits_2<Kernel>
Arr_text_formatter<Arrangement>
Arr_trapezoid_ric_point_location<Arrangement>
Arr_walk_along_line_point_location<Arrangement>
Arr_with_history_text_formatter<ArrFormatter>
decompose
do_intersect
insert_non_intersecting_curves
insert_non_intersecting_curve
insert_point
insert
is_valid
locate
operator<<
operator>>
OverlayTraits
overlay
read
remove_curve
remove_edge
remove_vertex
write
zone