Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Boost Polygon Library: Segment Concept

Polygon Sponsor

Segment Concept

The segment concept tag is segment_concept

To register a user defined type as a model of the segment concept, specialize the geometry concept meta-function for that type.  In the example below CSegment is registered as a model of the segment concept.

template <>
struct geometry_concept<CSegment> { typedef segment_concept type; };

The semantic of a segment is that it has a low and high point.  A std::pair, boost::tuple or boost::array could all be made models of segment by simply providing indirect access to their elements through traits, however, these objects cannot be made a model of both segment and rectangle in the same compilation unit, for obvious reason that duplicate specialization of the geometry_concept struct is illegal, but also because it would make overloading generic function by concept ambiguous if a type modeled more than one concept.

Below is shown the default segment traits. Specialization of these traits is required for types that don't conform to the default behavior.

template
struct segment_traits {
  typedef typename Segment::coordinate_type coordinate_type;
  typedef typename Segment::point_type point_type;

  static inline point_type get(const Segment& segment, direction_1d dir) {
    return segment.get(dir);
  }
};

template
struct segment_mutable_traits {
  typedef typename segment_traits::point_type point_type;

  static inline void set(Segment& segment, direction_1d dir, const point_type& point) {
    segment.set(dir, p);
  }

  static inline Segment construct(const point_type& low, const point_type& high) {
    return Segment(low, high);
  }
};

Functions

template
point_type get(const Segment& segment, direction_1d dir)		 Returns the low or high endpoint of an object that models segment, depending on the direction_1d value. 
template Segment, typename Point>
void set(Segment& segment, direction_1d dir,
         const Point& point)		 Sets the low or high endpoint of an object that models segment to an object that models point, depending on the direction_1d value.
template
Segment construct(const Point1& low, const Point2& high)		 Constructs an object that is a model of segment given the two objects that are models of point.
template Segment2>
Segment1 copy_construct(const Segment2& segment)		 Copy constructs an object that models segment given another segment.
template Segment1, typename Segment2>
Segment1& assign(Segment1& segment1,
                 const Segment2& segment2)		 Copies data from the second object that models segment into the first object that models segment.
template Segment1, typename Segment1>
bool equivalence(const Segment1& segment1,
                 const Segment1& segment2)		 Given two objects that model segment, compares and returns true if their low and high values are respectively equal.
template
int orientation(const Segment& segment,
                const Point& point)
 Implements a robust orientation test of two objects that model segment and point. Returns 0, if the point is collinear to the segment.
Returns 1, if the point lies to the left of the segment.
Returns -1, if the point lies to the right of the segment.
template
int orientation(const Segment1& segment1,
                const Segment2& segment2)		 Implements a robust orientation test of two objects that model segment. Note: segments are treated as math. vectors.
Returns 0, if segments are collinear.
Returns 1, if the second segment is CCW oriented to the first segment.
Returns -1, if the second segment is CW oriented to the first segment.
template Segment, typename Point>
bool contains(const Segment& segment,
    const Point& value, bool consider_touch)
 Returns true if an object that models segment contains an object that models point, else false.
template
bool contains(const Segment1& segment1,
    const Segment2& segment2, bool consider_touch)		 Returns true if the first object contains the second one, else false. Both objects model segment.
template Segment>
point_type low(const Segment& segment)
 Returns the low endpoint of an object that models segment.
template Segment>
point_type high(const Segment& segment)		 Returns the high endpoint of an object that models segment.
template Segment>
point_type center(const Segment& segment)		 Returns the central point of an object that models segment.
template Segment, typename Point>
void low(Segment& segment, const Point& point)		 Sets the low endpoint of an object that models segment.
template Segment, typename Point>
void high(Segment& segment, const Point& point)		 Sets the high endpoint of an object that models of segment.
template Segment>
distance_type length(const Segment& segment)
 Returns length of an object that models segment.
template Segment>
Segment& scale_up(Segment& segment,
    unsigned_area_type factor)		 Multiplies x and y coordinates of both endpoints of an object that models segment by unsigned factor.
template Segment>
Segment& scale_down(Segment& segment,
    unsigned_area_type factor)		 Divides x and y coordinates of both endpoints of an object that models segment by unsigned factor.
template Segment, typename Scale>
Segment& scale(Segment& segment, const Scale& sc) 		Calls the scale member function of the scaling type on the low and high endpoint of an object that models segment and updates the segment with the scaled endpoints.
template Segment, typename Transform>
Segment& transform(Segment& segment, const Transform& tr) 		Calls the transform member function of transform type on the low and high endpoints of an object that models segment and updates the segment with the transformed endpoints.
template Segment>
Segment& move(Segment& segment, orientation_2d
    coordinate_difference displacement)		 Adds displacement value to the x or y coordinates of both endpoints of an object that models segment indicated by the orientation_2d.
template <Segment, Point>
Segment& convolve(Segment& segment, const Point& point)		 Convolves both endpoints of an object that models segment with an object that models a point.
template <Segment, Point>
Segment& deconvolve(Segment& segment, const Point& point)		 Deconvolves both endpoints of an object that models segment with an object that models a point.
template
bool abuts(const Segment1& segment1,
    const Segment2& segment2, direction_1d dir)		 Returns true if two objects that model segment abut, depending on the direction_1d value.
template
bool abuts(const Segment1& segment1,
           const Segment2& segment2)		 Returns true if two objects that model segment abut: either the first one to the second one or vice versa.
template
bool intersects(const Segment1& segment1,
                const Segment2& segment2,
                bool consider_touch)
 Returns true if two objects that model segment intersect, else false.
template Segment, typename Point>
distance_type euclidean_distance(
    const Segment& segment, const Point& point) 		Returns distance from an object that models segment to an object that models point.
template Segment2>
distance_type euclidean_distance(
    const Segment1& segment1, const Segment2& segment2) 		Returns distance between two objects that model segment.

Segment Data

The library provides a model of the segment concept declared template segment_data, where T is the coordinate type.

This data type is used internally when a segment is needed and is available to the library user, who finds it convenient to use a library segment data type instead of providing their own.  The data type is implemented to be convenient to use with the library traits.

Members

geometry_type segment_concept
coordinate_type T
point_type point_data
segment_data() Default constructor.
segment_data(const point_type& low,
             const point_type& high)		 Constructs a segment from the given endpoints.
segment_data(const segment_data& that) Copy constructor.
segment_data& operator=(const segment_data& that) Assignment operator.
template
segment_data& operator=(const Segment& that) const		 Assign from an object that is a model of segment.
bool operator==(const segment_data& that) const Equality operator overload.
bool operator!=(const segment_data& that) const Inequality operator overload.
bool operator<(const segment_data& that) const Less operator overload. Compares low endpoints then high endpoints to break ties.
bool operator<=(const segment_data& that) const Less or equal operator overload. Compares low endpoints then high endpoints to break ties.
bool operator>(const segment_data& that) const Greater operator overload. Compares low endpoints then high endpoints to break ties.
bool operator>=(const segment_data& that) const Greater or equal operator overload. Compares low endpoints then high endpoints to break ties.
point_type get(direction_1d dir) const Retrieves the low/high endpoint considering direction value.
point_type low() const Retrieves the low endpoint.
point_type high() const Retrieves the high endpoint.
void set(direction_1d dir, const point_type& point) Sets the endpoint in the given direction.
segment_data& low(const point_type& point) Sets the low endpoint.
segment_data& high(const point_type& point) Sets the high endpoint.

Segment Utils

The library provides several algorithms for the manipulation of sets of segment data. In particular, the generalize line segment intersection algorithm used for polygon set operations is exposed through several interfaces to allow it to be used with any collection or sequence of objects that model the segment_concept.

Functions

template <typename SegmentContainer,
          typename SegmentIterator>
void intersect_segments(
    SegmentContainer* result,
    SegmentIterator first,
    SegmentIterator last) 		Accumulates the result of splitting the segments in the iterator range at their intersection points into the result container. Preconditions: segment type used by all the input structures should model segment concept.Postconditions: no segments intersect except at their end points. Useful to satisfy the precondition of voronoi diagram construction. Expected n log n runtime, worst case quadratic runtime wrt. vertices + intersections.
template <typename Segment,
          typename SegmentIterator>
void intersect_segments(
    vector* result,
    SegmentIterator first,
    SegmentIterator last)		 Accumulates the result of splitting the segments in the iterator range at their intersection points into the result container. Preconditions: segment type used by all the input structures should model segment concept. Postconditions: no segments intersect except at their end points. The index of the input segment is paired with each resultant segment that was split to produce it to associate the result segments with the inputs segments. Expected n log n runtime, worst case quadratic runtime wrt. vertices + intersections.
template <typename Rectangle,
          typename SegmentIterator>
void envelope_segments(
    Rectangle* rect,
    SegmentIterator first,
    SegmentIterator last) 		Computes the bounding rectangle of the iterator range of line segments. Preconditions: segment type and rectangle type used by the input structures should model segment concept and rectangle concept respectively. Linear runtime.
 
Copyright: Copyright © Intel Corporation 2008-2010.
License: Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)