### Contents

- Boost.Polygon Main Page
- Design Overview
- Isotropy
- Coordinate Concept
- Interval Concept
- Point Concept
- Segment Concept
- Rectangle Concept
- Polygon 90 Concept
- Polygon 90 With Holes Concept
- Polygon 45 Concept
- Polygon 45 With Holes Concept
- Polygon Concept
- Polygon With Holes Concept
- Polygon 90 Set Concept
- Polygon 45 Set Concept
- Polygon Set Concept
- Connectivity Extraction 90
- Connectivity Extraction 45
- Connectivity Extraction
- Property Merge 90
- Property Merge 45
- Property Merge
- Voronoi Main Page
- Voronoi Benchmark
- Voronoi Builder
- Voronoi Diagram
- Voronoi Predicates
- Voronoi Robust FPT

### Other Resources

- GTL Boostcon 2009 Paper
- GTL Boostcon 2009 Presentation
- Performance Analysis
- Layout Versus Schematic Tutorial
- Minkowski Sum Tutorial
- Voronoi Basic Tutorial
- Voronoi Advanced Tutorial

### 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<Point, Point>, boost::tuple<Point, Point> or boost::array<Point, 2> 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 <typename Segment>
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 <typename Segment>
struct segment_mutable_traits {
typedef typename segment_traits<Segment>::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 <typename Segment> 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 <typename 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 <typename Segment, typename Point1, typename Point2> 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 <typename Segment1, typename Segment2> Segment1 copy_construct(const Segment2& segment) | Copy constructs an object that models segment given another segment.
template <typename 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 <typename 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 <typename Segment, typename Point> 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 <typename Segment1, typename Segment2>
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 <typename 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 <typename Segment1, typename Segment2> 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 <typename Segment> point_type low(const Segment& segment) | Returns the low endpoint of an object that models segment.
template <typename Segment> point_type high(const Segment& segment) | Returns the high endpoint of an object that models segment.
template <typename Segment> point_type center(const Segment& segment) | Returns the central point of an object that models segment.
template <typename Segment, typename Point> void low(Segment& segment, const Point& point) | Sets the low endpoint of an object that models segment.
template <typename Segment, typename Point> void high(Segment& segment, const Point& point) | Sets the high endpoint of an object that models of segment.
template <typename Segment> distance_type length(const Segment& segment) | Returns length of an object that models segment.
template <typename 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 <typename 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 <typename 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 <typename 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 <typename 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 <typename Segment1, typename Segment2> 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 <typename Segment1, typename Segment2> 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 <typename Segment1, typename Segment2> bool intersects(const Segment1& segment1, const Segment2& segment2, bool consider_touch) | Returns true if two objects that model segment intersect, else false.
template <typename 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 <typename Segment1, typename 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<typename T> 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<T>
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 <typename Segment> 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<pair<size_t, Segment>* 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)