The traits class Arr_polyline_traits_2<SegmentTraits> is a model of the ArrangementTraits_2 concept. It handles piecewise linear curves, commonly referred to as polylines. Each polyline is a chain of segments, where each two neighboring segments in the chain share a common endpoint. The traits class exploits the functionality of the SegmentTraits template-parameter to handle the segments that comprise the polyline curves.

The class instantiated for the template parameter SegmentTraits must be a model of the ArrangementTraits_2 concept that handles line segments (e.g., Arr_segment_traits_2<Kernel> or Arr_non_caching_segment_cached_traits_2<Kernel>, where the first alternative is recommended).

The number type used by the injected segment traits should support exact rational arithmetic (that is, the number type should support the arithmetic operations +, -, × and ÷ that should be carried out without loss of precision), in order to avoid robustness problems, although other inexact number types could be used at the user's own risk.

#include <CGAL/Arr_polyline_traits_2.h>

Is Model for the Concepts


Class Arr_polyline_traits_2<SegmentTraits>::Curve_2

The Curve_2 class nested within the polyline traits is used to represent general continuous piecewise-linear curves (a polyline can be self-intersecting) and support their construction from any range of points.

The copy and default constructor as well as the assignment operator are provided for polyline curves. In addition, an operator<< for the curves is defined for standard output streams, and an operator>> for the curves is defined for standard input streams.


A bidirectional iterator that allows traversing the points that comprise a polyline curve.

A bidirectional iterator that allows traversing the points that comprise a polyline curve.


Arr_polyline_traits_2<SegmentTraits>::Curve_2 pi;
default constructor that constructs an empty polyline.

template <class InputIterator>
Arr_polyline_traits_2<SegmentTraits>::Curve_2 pi ( Iterator first, Iterator last);
constructs a polyline defined by the given range of points [first, last) (the value-type of InputIterator must be SegmentTraits::Point_2. If the range contains (n + 1) points labeled (p0,p1,...,pn), the generated polyline consists of n segments, where the kth segment is defined by the endpoints [pk-1,pk]. The first point in the range is considered as the source point of the polyline while the last point is considered as its target.
Precondition: There are at least two points in the range.

Access Functions

size_t pi.points () returns the number of points that comprise the polyline. Note that if there are n points in the polyline, it is comprised of (n - 1) segments.

const_iterator pi.begin () returns an iterator pointing at the source point of the polyline.

const_iterator pi.end () returns an iterator pointing after the end of the polyline.

const_iterator pi.rbegin () returns an iterator pointing at the target point of the polyline.

const_iterator pi.rend () returns an iterator pointing before the beginning of the polyline.

size_t pi.size () returns the number of line segments comprising the polyline (equivalent to pi.points() - 1).

typename SegmentTraits::X_monotone_curve_2
pi [ size_t k ] returns the kth segment of the polyline.
Precondition: k is not greater or equal to pi.size() - 1.

Bbox_2 pi.bbox () return a bounding box of the polyline pi.


void pi.push_back ( Point_2 p) adds a new point to the polyline, which becomes the new target point of pi.

void pi.clear () resets the polyline.

Class Arr_polyline_traits_2<SegmentTraits>::X_monotone_curve_2

The X_monotone_curve_2 class nested within the polyline traits is used to represent x-monotone piecewise linear curves. It inherits from the Curve_2 type. It has a default constructor and a constructor from a range of points, just like the Curve_2 class. However, there is precondition that the point range define an x-monotone polyline.

The points that define the x-monotone polyline are always stored in an ascending lexicographical xy-order, so their order may be reversed with respect to the input sequence. Also note that the x-monotonicity ensures that an x-monotone polyline is never self-intersecting (thus, a self-intersecting polyline will be subdivided to several interior-disjoint x-monotone subcurves).

See Also