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

# Polygon Concept

The polygon concept tag is polygon_concept

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

template <>
struct geometry_concept<CPolygon> { typedef polygon_concept type; };

The semantic of a polygon is that it can provide iterators over the points that represent its vertices. It is acceptable to have the last edge explict with the first and last point equal to each other or implied by this segement that would connect the first and last point. A mutable polygon must also be able to set its geometry based on an interator range over such points. A std::vector<point_data<int> > or std::list<point_data<int> > could be made models of polygon_concept by simply providing access to their iterators through traits. Library functions that create polygon objects require that those objects provide a default constructor.

Below is shown the default polygon traits. Specialization of these traits is required for types that don't conform to the default behavior. Note that these same traits are also used by several other polygon concepts through SFINE enable template parameter. The SFINE enable parameter also allows the library to provide default specialization that work for any object that models the 90 degree polygon concepts.

template <typename T, typename enable = gtl_yes>
struct polygon_traits {};
template <typename T>
struct polygon_traits<T,
typename gtl_or_4<
typename gtl_same_type<typename geometry_concept<T>::type, polygon_concept>::type,
typename gtl_same_type<typename geometry_concept<T>::type, polygon_concept>::type,
typename gtl_same_type<typename geometry_concept<T>::type, polygon_with_holes_concept>::type,
typename gtl_same_type<typename geometry_concept<T>::type, polygon_with_holes_concept>::type
>::type> {
typedef typename T::coordinate_type coordinate_type;
typedef typename T::iterator_type iterator_type;
typedef typename T::point_type point_type;
static inline iterator_type begin_points(const T& t) {
return t.begin();
}
static inline iterator_type end_points(const T& t) {
return t.end();
}
static inline unsigned int size(const T& t) {
return t.size();
}
static inline winding_direction winding(const T& t) {
return unknown_winding;
}
};

template <typename T, typename enable = void>
struct polygon_mutable_traits {
template <typename iT>
static inline T& set_points(T& t, iT input_begin, iT input_end) {
t.set(input_begin, input_end);
return t;
}
};

Example code custom_polygon.cpp demonstrates mapping a user defined polygon class to the library polygon_concept

An object that is a model of polygon_concept can be viewed as a model of any of its refinements if it is determined at runtime to conform to the restriction of those concepts. This concept casting is accomplished through the view_as<>() function.

view_as<rectangle_concept>(polygon_object)
view_as<polygon_90_concept>(polygon_object)
view_as<polygon_45_concept>(polygon_object)

The return value of view_as<>() can be passed into any interface that expects an object of the conceptual type specified in its template parameter.

## Functions

template <typename T> point_iterator_type begin_points(const T& polygon) | Expects a model of polygon. Returns the begin iterator over the range of points that correspond to vertices of the polygon.
template <typename T> point_iterator_type end_points(const T& polygon) | Expects a model of polygon. Returns the end iterator over the range of points that correspond to vertices of the polygon.
template <typename T, typename iterator> void set_points(T& polygon, iterator b, iterator e) | Expects a model of polygon. Sets the polygon to the point data range [b,e) that corresponds to vertices of a manhattan polygon.
template <typename T> unsigned int size(const T& polygon) | Returns the number of edges in the polygon.
template <typename T1, typename T2> T1& assign(T1& left, const T2& right) | Copies data from right object that models polygon into left object that models polygon.
template <typename T, typename point_type> bool contains(const T&, const point_type& point, bool consider_touch=true) | Given an object that models polygon and an object that models point, returns true if the polygon contains the point. If the consider_touch flag is true will return true if the point lies along the boundary of the polygon. Linear wrt. vertices.
// get the center coordinate template <typename T, typename point_type> void center(point_type& p, const T& polygon) | Sets object that models point to the center point of the bounding box of an object that models polygon. Linear wrt. vertices.
template <typename T, typename rectangle_type> bool extents(rectangle_type& bbox, const T& polygon) | Sets object that models rectangle to the bounding box of an object that models polygon and returns true. Returns false and leaves bbox unchanged if polygon is empty. Linear wrt. vertices.
template <typename T> area_type area(const T& polygon) | Returns the area of an object that models polygon. Linear wrt. vertices.
template <typename T> direction_1d winding(const T& polygon) | Returns the winding direction of an object that models polygon, LOW == CLOCKWISE, HIGH = COUNTERCLOCKWISE. Complexity depends upon winding trait.
template <typename T> coordinate_distance perimeter(const T& polygon) | Returns the perimeter length of an object that models polygon. Linear wrt. vertices.
template <typename T, typename transform_type> T& transform(T& polygon, const transform_type&) | Applies transform() on the vertices of polygon and sets the polygon to that described by the result of transforming its vertices. Linear wrt. vertices.
template <typename T> T& scale_up(T& polygon, unsigned_area_type factor) | Scales up coordinate of an object that models polygon by unsigned factor. Linear wrt. vertices.
template <typename T> T& scale_down(T& polygon, unsigned_area_type factor) | Scales down coordinates of an object that models polygon by unsigned factor. Linear wrt. vertices.
template <typename T, scaling_type> T& scale(T& rectangle, double scaling) | Scales coordinates of an object that models polygon by floating point factor. Linear wrt. vertices.
template <typename T> T& move(T& polygon, orientation_2d, coordinate_difference displacement) | Adds displacement value to coordinate indicated by orientation_2d of vertices of an object that models polygon . Linear wrt. vertices.
template <typename polygon_type, typename point_type> polygon_type& convolve(polygon_type& polygon, const point_type& point) | Convolves coordinate values of point with vertices of an object that models polygon. Linear wrt. vertices.

# Polygon Data

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

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

Example code polygon_usage.cpp demonstrates using the library provided polygon data types and functions

## Members

geometry_type | polygon_concept
coordinate_type | T
iterator_type | Iterator over vertices point_data<T> vertices of polygon
polygon_data() | Default constructs the polygon.
polygon_data(const polygon_data& that) | Copy construct
polygon_data& operator=(const polygon_data& that) | Assignment operator.
template <typename T2> polygon_data& operator=(const T2& that) const | Assign from an object that is a model of polygon.
iterator_type begin() const | Get the begin iterator over vertices of the polygon.
iterator_type end() const | Get the end iterator over vertices of the polygon.
std::size_t size() const | Get the number of elements in the sequence stored to the polygon, usually equal to the number of edges of the polygon.
template <typename iT> void set(iT begin_points, iT end_points) | Sets the polygon to the iterator range of points.

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)