Class

CGAL::Arr_segment_traits_2<Kernel>

Definition

The traits class Arr_segment_traits_2<Kernel> is a model of the ArrangementTraits_2 concept, which allows the construction and maintenance of arrangements of line segments. It should be parameterized with a Cgal-kernel model that is templated in turn with a number type. To avoid numerical errors and robustness problems, the number type should support exact rational arithmetic - that is, the number type should support the arithmetic operations +, -, × and ÷ carried out without loss of precision.

For example, instantiating the traits template with kernels, such as Cartesian<Quotient<MP_Float> >, or Homogeneous<Gmpz>, ensures the exact and robust operation of the application. In particular, the Cartesian<Gmpq> achieves the fastest running times in most cases. Using other inexact number types (for example, instantiating the template with Simple_cartesian<double>) is at the user's own risk: Selecting an inexact number type usually leads to faster running time at the expense of possible robustness problems.

For optimal performance, we recommend instantiating the traits class with the default Exact_predicates_exact_constructions_kernel provided by Cgal. Using this kernel guarantees exactness and robustness, while it incurs only a minor overhead (in comparison to working with a fast, inexact number type) for most inputs.

Arr_segment_traits_2<Kernel> defines Kernel::Point_2 as its point type. However, it does not define Kernel::Segment_2 as its curve type, as one may expect. The reason is that the kernel segment is represented by its two endpoints only, while the traits class needs to store extra data with its segments, in order to efficiently operate on them. Nevertheless, the nested X_monotone_curve_2 and Curve_2 types (in this case both types refer to the same class, as every line segment is (weakly) x-monotone) can however be converted to the type Kernel::Segment_2.

Arr_segment_traits_2<Kernel> achieves faster running times than the Arr_non_caching_segment_traits_2<Kernel> traits-class, when arrangements with relatively many intersection points are constructed. It also allows for working with less accurate, yet computationally efficient number types, such as Quotient<MP_Float>, which represents floating-point numbers with an unbounded mantissa, but with a bounded exponent. Using this traits class is therefore highly recommended for almost all applications that rely on arrangements of line segments. On the other hand, Arr_segment_traits_2<Kernel> uses more space and stores extra data with each segment, so constructing arrangements of huge sets of non-intersecting segments (or segments that intersect very sparsely) could be more efficient with the Arr_non_caching_segment_traits_2 traits-class.

While Arr_segment_traits_2<Kernel> models the concept ArrangementDirectionalXMonotoneTraits_2, the implementation of the Arr_mergeable_2 operation does not enforce the input curves to have the same direction as a precondition. Moreover, Arr_segment_traits_2<Kernel> supports the merging of curves of opposite directions.

#include <CGAL/Arr_segment_traits_2.h>

Is Model for the Concepts

ArrangementTraits_2
ArrangementLandmarkTraits_2
ArrangementDirectionalXMonotoneTraits_2