### 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

# Interval Concept

The interval concept tag is interval_concept

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

template <>
struct geometry_concept<CInterval> { typedef interval_concept type; };

The semantic of an interval is that it has a low and high coordinate and there is an invariant that low is less than or equal to high. This invariant is enforced by the generic library functions that operate on intervals, and is not expected of the data type itself or the concept mapping of that data type to the interval concept through its traits. In this way a std::pair<int, int>, boost::tuple<int, int> or boost::array<int, 2> could all be made models of interval by simply providing indirect access to their elements through traits.

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

template <typename T>
struct interval_traits {
typedef typename T::coordinate_type coordinate_type;
static inline coordinate_type get(const T& interval, direction_1d dir) {
return interval.get(dir);
}
};
template <typename T>
struct interval_mutable_traits {
static inline void set(T& interval, direction_1d dir,
typename interval_traits<T>::coordinate_type value) {
interval.set(dir, value);
}
static inline T construct(typename interval_traits<T>::coordinate_type low_value,
typename interval_traits<T>::coordinate_type high_value) {
return T(low_value, high_value);
}
};

## Functions

template <typename T> coordinate_type get(const T& interval, direction_1d) | Expects a model of interval. Returns the low or high coordinate of the interval, depending on the direction_1d value.
template <typename T, typename coordinate_type> void set(T& interval, direction_1d, coordinate_type) | Expects a model of interval. Sets the low or high coordinate of the interval to the coordinate, depending on the direction_1d value. If low would be greater than high after this change then both are set to the input coordinate value.
template <typename T> T construct(coordinate_type low, coordinate_type high) | Construct an object that is a model of interval given low and high coordinate values.
template <typename T1, typename T2> T1& assign(T1& left, const T2& right) | Copies data from right object that models interval into left object that models interval.
template <typename T, typename T2> bool equivalence(const T& interval1, const T2& interval2) | Given two objects that model interval, compares and returns true if their low and high values are respectively equal to each other.
template <typename T> bool contains(const T&, coordinate_type, bool consider_touch=true) | Given an object that models interval and a coordinate, returns true if the interval contains the coordinate. If the consider_touch flag is true will return true if the coordinate is equal to one of the interval ends.
template <typename T1, typename T2> bool contains(const T1& a, const T2& b, bool consider_touch = true) | Returns true if model of interval a contains both ends of model of interval b. If the consider_touch flag is true will consider the end of b contained within a even if it is equal to an end of a.
template <typename interval_type> coordinate_type low(const interval_type& interval) | Returns the low end of an object that models interval.
template <typename interval_type> coordinate_type high(const interval_type& interval) | Returns the high end of an object that models interval.
// get the center coordinate template <typename interval_type> coordinate_type center(const interval_type& interval) | Returns the center coordinate of an object that models interval.
template <typename interval_type> void low(interval_type& interval, coordinate_type ) | Sets the low end of the object that models interval to the coordinate value. If the low end would be set to larger than high end then both are set to the coordinate value.
template <typename interval_type> void high(interval_type& interval, coordinate_type ) | Sets the high end of the object that models interval to the coordinate value. If the high end would be set to less than low end then both are set to the coordinate value.
template <typename interval_type> coordinate_difference delta(const interval_type& interval) | Returns the distance from low to high end of an object that models interval.
template <typename interval_type> interval_type& flip(interval_type& interval, coordinate_type axis = 0) | Flips an object that models interval about the axis coordinate. If no axis is provided the interval is flipped across the the origin.
template <typename interval_type> interval_type& scale_up(interval_type& interval, unsigned_area_type factor) | Multiplies low and high ends of an object that models interval by unsigned factor.
template <typename interval_type> interval_type& scale_down(interval_type& interval, unsigned_area_type factor) | Divides low and high ends of an object that models interval by unsigned factor.
template <typename interval_type> interval_type& scale(interval_type& interval, double factor) | Multiplies low and high ends of an object that models interval by floating point value.
template <typename interval_type> interval_type& move(interval_type& interval, coordinate_difference displacement) | Adds displacement value to low and high ends of an object that models interval.
template <typename interval_type> interval_type& convolve(interval_type& interval, coordinate_type b) | Adds coordinate value to low and high ends of an object that models interval.
template <typename interval_type> interval_type& deconvolve(interval_type& interval, coordinate_type b) | Subtracts coordinate value from low and high ends of an object that models interval.
template <typename T1, typename T2> T1& convolve(T1& a, const T2& b) | Adds low end of b to low end of a and adds high end of b to high end of a.
template <typename T1, typename T2> T1& deconvolve(T1& a, const T2& b) | Subtracts low end of b from low end of a and subtracts high end of b from high end of a.
template <typename T1, typename T2> T1& reflected_convolve(T1& a, const T2& b) | Adds high end of b to low end of a and adds low end of b to high end of a.
template <typename T1, typename T2> T1& reflected_deconvolve(T1& a, const T2& b) | Subtracts high end of b from low end of a and subtracts low end of b from high end of a.
template <typename T> coordinate_difference euclidean_distance(const T&, coordinate_type) | Returns the distance from an object that models interval to a coordinate. Returns zero if the coordinate is equal to an end of the interval or contained within the interval.
template <typename T1, typename T2> bool intersects(const T1& interval, const T2& b, bool consider_touch = true) | Returns true if two objects that model interval overlap. If the consider_touch flag is true touching at the endpoints is considered overlap.
template <typename T1, typename T2> bool boundaries_intersect(const T1& interval, const T2& b, bool consider_touch = true) | Returns true is two objects that model interval partially overlap such that one end point of each is contained within the other. If the consider_touch flag is true a coordinate is considered contained even if it is equal to an end.
template <typename T1, typename T2> bool abuts(const T1& a, const T2& b, direction_1d dir) | Returns true if interval b abuts but down not overlap interval a on the end of interval a specified by dir.
template <typename T1, typename T2> bool abuts(const T1& a, const T2& b) | Returns true if interval b abuts but down not overlap interval a.
template <typename T1, typename T2> bool intersect(T1& a, const T2& b, bool consider_touch = true) | Sets interval a to the intersection of interval a and interval b and return true. If the two intervals do not intersect interval a is unchanged and the function returns false. If the flag consider_touch is true intervals that abut are considered to intersect.
template <typename T1, typename T2> T& generalized_intersect(T1& a, const T2& b) | Same as intersect, but if they do not intersect set a to the interval between a and b.
template <typename T> T& bloat(T& interval, coordinate_type) | Adds the coordinate value to high end of interval and subtracts it from low end of interval.
template <typename T> T& bloat(T& interval, direction_1d, coordinate_type) | Adds the coordinate value to high end of interval or subtracts it from low end of interval depending on the direction_1d.
template <typename T> T& shrink(T& interval, coordinate_type) | Subtracts the coordinate value from high end of interval and adds it to low end of interval.
template <typename T> T& shrink(T& interval, direction_1d, coordinate_type) | Subtracts the coordinate value from high end of interval or adds it to low end of interval depending on the direction_1d.
template <typename T1, typename T2> bool encompass(T1& a, const T2& b) | Sets low of a to min of low of a and low of b and sets high of a to max of high of a and high of b. Returns true if b was not contained within a to begin with.
template <typename T> bool encompass(T& a, coordinate_type) | Sets low of a to min of low of a and coordinate value and sets high of a to max of high of a and coordinate value. Returns true if coordinate value was not contained within a to begin with.

# Interval Data

The library provides a model of interval concept declared template<typename T> interval_data where T is the coordinate type.

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

## Members

geometry_type | interval_concept
coordinate_type | T
interval_data() | Default constructs the two coordinate values of the interval.
interval_data(T low, T high) | Constructs an interval with two coordinates.
interval_data(const interval_data& that) | Copy construct
interval_data& operator=(const interval_data& that) | Assignment operator.
template <typename T2> interval_data& operator=(const T2& that) const | Assign from an object that is a model of interval.
template <typename T2> bool operator==(const T2& that) const | Compare equality to an object that is a model of interval.
template <typename T2> bool operator!=(const T2& that) const | Compare inequality to an object that is a model of interval.
template <typename T2> bool operator<(const T2& that) const | Compares low coordinates then high coordinates to break ties.
template <typename T2> bool operator<=(const T2& that) const | Compares low coordinates then high coordinates to break ties.
template <typename T2> bool operator>(const T2& that) const | Compares low coordinates then high coordinates to break ties.
template <typename T2> bool operator>=(const T2& that) const | Compares low coordinates then high coordinates to break ties.
T get(direction_1d dir) const | Get the coordinate in the given direction.
void set(direction_1d dir, T value) | Sets the coordinate in the given direction to the value.

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)