2D Arrangement Reference

Ron Wein, Eric Berberich, Efi Fogel, Dan Halperin, Michael Hemmer, Oren Salzman, and Baruch Zukerman

This package can be used to construct, maintain, alter, and display arrangements in the plane. Once an arrangement is constructed, the package can be used to obtain results of various queries on the arrangement, such as point location. The package also includes generic implementations of two algorithmic frameworks, that are, computing the zone of an arrangement, and line-sweeping the plane, the arrangements is embedded on. These frameworks are used in turn in the implementations of other operations on arrangements. Computing the overlay of two arrangements, for example, is based on the sweep-line framework. Arrangements and arrangement components can also be extended to store additional data. An important extension stores the construction history of the arrangement, such that it is possible to obtain the originating curve of an arrangement subcurve.

Introduced in: CGAL 2.1
BibTeX: cgal:wfzh-a2-24b
License: GPL
Windows Demo: 2D Arrangements

Given a set \( \mathcal{C}\) of planar curves, the arrangement \( {\mathcal A}({\mathcal C})\) is the subdivision of the plane induced by the curves in \( \mathcal{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.

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
• CGAL::Arr_closed_side_tag
• CGAL::Arr_contracted_side_tag
• CGAL::Arr_identified_side_tag

Concepts

• ArrangementDcel
• ArrangementDcelWithRebind
• ArrangementDcelVertex
• ArrangementDcelHalfedge
• ArrangementDcelFace
• ArrangementDcelOuterCcb
• ArrangementDcelInnerCcb
• ArrangementDcelIsolatedVertex
• ArrangementBasicTopologyTraits
• ArrangementBasicTraits_2
• ArrangementConstructXMonotoneCurveTraits_2
• ArrangementConstructCurveTraits_2
• ArrangementLandmarkTraits_2
• ArrangementXMonotoneTraits_2
• ArrangementTraits_2
• ArrangementHorizontalSideTraits_2
• ArrangementVerticalSideTraits_2
• ArrangementIdentifiedVerticalTraits_2
• ArrangementIdentifiedHorizontalTraits_2
• ArrangementOpenBoundaryTraits_2
• ArrangementSphericalBoundaryTraits_2
• ArrangementInputFormatter
• ArrangementOutputFormatter
• ArrangementWithHistoryInputFormatter
• ArrangementWithHistoryOutputFormatter
• ArrangementPointLocation_2
• ArrangementVerticalRayShoot_2
• ArrangementOpenLeftTraits_2
• ArrangementOpenRightTraits_2
• ArrangementOpenBottomTraits_2
• ArrangementOpenTopTraits_2
• ArrangementClosedLeftTraits_2
• ArrangementClosedRightTraits_2
• ArrangementClosedBottomTraits_2
• ArrangementClosedTopTraits_2
• ArrangementContractedLeftTraits_2
• ArrangementContractedRightTraits_2
• ArrangementContractedBottomTraits_2
• ArrangementContractedTopTraits_2
• ArrangementLeftSideTraits_2
• ArrangementRightSideTraits_2
• ArrangementBottomSideTraits_2
• ArrangementTopSideTraits_2
• ArrangementTopologyTraits

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::IsOnXIdentification_2
• ArrTraits::IsOnYIdentification_2
• ArrTraits::CompareYAtX_2
• ArrTraits::CompareYAtXLeft_2
• ArrTraits::CompareYAtXRight_2
• ArrTraits::Equal_2
• ArrTraits::ParameterSpaceInX_2
• ArrTraits::ParameterSpaceInY_2
• ArrTraits::CompareXOnBoundary_2
• ArrTraits::CompareYOnBoundary_2
• ArrTraits::CompareXNearBoundary_2
• ArrTraits::CompareYNearBoundary_2
• ArrTraits::CompareXOnBoundaryOfCurveEnd_2
• ArrTraits::Intersect_2
• ArrTraits::Split_2
• ArrTraits::AreMergeable_2
• ArrTraits::Merge_2
• ArrTraits::MakeXMonotone_2
• ArrTraits::Approximate_2
• ArrTraits::ConstructXMonotoneCurve_2
• ArrTraits::ConstructCurve_2

Classes

• CGAL::Arrangement_on_surface_2<GeometryTraits_2,TopologyTraits>
• CGAL::Arrangement_on_surface_with_history_2<GeometryTraits_2,TopologyTraits>
• CGAL::Arrangement_2<Traits,Dcel>
• CGAL::Arrangement_with_history_2<Traits,Dcel>
• CGAL::Arr_accessor<Arrangement>
• CGAL::Arr_observer<Arrangement>
• CGAL::Arrangement_2::Vertex
• CGAL::Arrangement_2::Halfedge
• CGAL::Arrangement_2::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_geodesic_arc_on_sphere_traits_2<Kernel,x,y>
• 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>
• CGAL::Arr_vertex_index_map<Arrangement>
• CGAL::Arr_face_index_map<Arrangement>
• CGAL::Arr_point_location_result<Arrangement>
• CGAL::Arr_bounded_planar_topology_traits_2<GeometryTraits_2,Dcel>
• CGAL::Arr_unb_planar_topology_traits_2<GeometryTraits_2,Dcel>
• CGAL::Arr_spherical_topology_traits_2<GeometryTraits_2,Dcel>

Macros

• CGAL_ARR_POINT_LOCATION_VERSION

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::IO::read()
• CGAL::IO::write()
• CGAL::remove_curve()
• CGAL::operator<<
• CGAL::operator<<

Draw an Arrangemen_2 object

• CGAL::draw<>()

Modules
	Concepts
	Geometry Traits Classes
	DCEL
	I/O
	Point Location
	Overlay
	Computes the overlay of two arrangements with history arr1 and arr2, and sets the output arrangement with history res to represent the overlaid arrangement.
	Free Functions
	Drawing
	Tags
	Macros
	Enumerations

Classes
class	CGAL::Arr_accessor< Arrangement >
class	CGAL::Arr_bounded_planar_topology_traits_2< GeometryTraits_2, Dcel >
class	CGAL::Arr_face_index_map< Arrangement >
	Arr_face_index_map maintains a mapping of face handles of an attached arrangement object to indices (of type unsigned int). More...
class	CGAL::Arr_observer< Arrangement >
class	CGAL::Arr_spherical_topology_traits_2< GeometryTraits_2, Dcel >
class	CGAL::Arr_unb_planar_topology_traits_2< GeometryTraits_2, Dcel >
class	CGAL::Arr_vertex_index_map< Arrangement >
	Arr_vertex_index_map maintains a mapping of vertex handles of an attached arrangement object to indices (of type unsigned int). More...
class	CGAL::Arrangement_2< Traits, Dcel >
class	CGAL::Arrangement_on_surface_2< GeometryTraits, TopologyTraits >
class	CGAL::Arrangement_on_surface_with_history_2< GeometryTraits, TopologyTraits >
class	CGAL::Arrangement_with_history_2< Traits, Dcel >