Polygon Sponsor

Polygon Set Concept
The polygon_set concept tag is
polygon_set_concept
The semantic of a polygon_set is zero or more
geometry regions. A Polygon Set Concept may be defined with floating point
coordinates, but a snap rounding distance of one integer unit will still be
applied, furthermore, geometry outside the domain where one integer unit is
sufficient to provide robustness may lead to undefined behavior in algorithms.
It is recommended to use integer coordinates for robust operations. In the
case that data represented contains only Manhattan geometry a runtime check will
default to the Manhattan algorithm. The results of which are identical to
what the general algorithm would do, but obtained more efficiently. In the
case that the data represented contains only Manhattan and 45degree geometry a
runtime check will default to the faster 45degree algorithm. The results
of which may differ slight from what the general algorithm would do because
noninteger intersections will be handled differently. Users are recommended to use std::vector and std::list of user defined polygons
or library provided polygon_set_data<coordinate_type> objects. Lists
and vectors of models of polygon_concept or polygon_with_holes_concept are automatically models of polygon_set_concept.
Example code custom_polygon_set.cpp
demonstrates mapping a user defined class to the library polygon_set_concept
An object that is a model of
polygon_set_concept can be viewed as a model of
polygon_90_set_concept or
polygon_45_set_concept if it is determined at runtime to conform to the
restrictions of those concepts. This concept casting is accomplished
through the view_as<>() function.
view_as<polygon_90_set_concept>(polygon_set_object)
view_as<polygon_45_set_concept>(polygon_set_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. Polygon sets cannot be viewed as single polygons
or rectangles since it generally cannot be known whether a polygon set contains
only a single polygon without converting to polygons.
Operators
The return type of some operators is the polygon_set_view
operator template type. This type is itself a model of the polygon 90 set
concept, but furthermore can be used as an argument to the polygon_set_data
constructor and assignment operator. The operator template exists to
eliminate temp copies of intermediate results when Boolean operators are chained
together.
Operators are declared inside the namespace boost::polygon::operators.
template <typename T1, typename
T2>
polygon_set_view operator(const T1& l, const T2& r) 
Boolean OR operation (polygon set union). Accepts two objects
that model polygon_set or one of its refinements. Returns an
operator template that performs the operation on demand when chained or
or nested in a library function call such as assign(). Expected n
log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
template <typename T1, typename
T2>
polygon_set_view operator+(const T1& l, const T2& r) 
Same as operator. The plus sign is also used for OR
operations in Boolean logic expressions. Expected n log n runtime,
worst case quadratic runtime wrt. vertices + intersections. 
template <typename T1, typename
T2>
polygon_set_view operator&(const T1& l, const T2& r) 
Boolean AND operation (polygon set intersection). Accepts two
objects that model polygon_set or one of its refinements. Expected
n log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
template <typename T1, typename
T2>
polygon_set_view operator*(const T1& l, const T2& r) 
Same as operator&. The multiplication symbol is also used for
AND operations in Boolean logic expressions. Expected n log n
runtime, worst case quadratic runtime wrt. vertices + intersections. 
template <typename T1, typename
T2>
polygon_set_view operator^(const T1& l, const T2& r) 
Boolean XOR operation (polygon set disjointunion). Accepts
two objects that model polygon_set or one of its refinements.
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
template <typename T1, typename
T2>
polygon_set_view operator(const T1& l, const T2& r) 
Boolean SUBTRACT operation (polygon set difference). Accepts
two objects that model polygon_set or one of its refinements.
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
template <typename T1, typename
T2>
T1& operator=(const T1& l, const T2& r) 
Same as operator, but with self assignment, left operand must model
polygon_set and not one of it's refinements. Expected n log n
runtime, worst case quadratic runtime wrt. vertices + intersections. 
template <typename T1, typename
T2>
T1& operator+=(T1& l, const T2& r) 
Same as operator+, but with self assignment, left operand must model
polygon_set and not one of it's refinements. Expected n log n
runtime, worst case quadratic runtime wrt. vertices + intersections. 
template <typename T1, typename
T2>
T1& operator&=(const T1& l, const T2& r) 
Same as operator&, but with self assignment, left operand must model
polygon_set and not one of it's refinements. Expected n log n
runtime, worst case quadratic runtime wrt. vertices + intersections. 
template <typename T1, typename
T2>
T1& operator*=(T1& l, const T2& r) 
Same as operator*, but with self assignment, left operand must model
polygon_set and not one of it's refinements. Expected n log n
runtime, worst case quadratic runtime wrt. vertices + intersections. 
template <typename T1, typename
T2>
T1& operator^=(const T1& l, const T2& r) 
Same as operator^, but with self assignment, left operand must model
polygon_set and not one of it's refinements. Expected n log n
runtime, worst case quadratic runtime wrt. vertices + intersections. 
template <typename T1, typename
T2>
T1& operator=(T1& l, const T2& r) 
Same as operator, but with self assignment, left operand must model
polygon_set and not one of it's refinements. Expected n log n
runtime, worst case quadratic runtime wrt. vertices + intersections. 
template <typename T1>
T1 operator+(const T1&, coordinate_type bloating) 
Performs resize operation, inflating by bloating ammount. If
negative the result is a shrink instead of bloat. Note: returns
result by value. Expected n log n runtime, worst case quadratic
runtime wrt. vertices + intersections. 
template <typename T1, typename
T2>
T1 operator(const T1&, coordinate_type shrinking) 
Performs resize operation, deflating by bloating ammount. If
negative the result is a bloat instead of shrink. Note: returns
result by value. Expected n log n runtime, worst case quadratic
runtime wrt. vertices + intersections. 
template <typename T1, typename
T2>
T1& operator+=(const T1&, coordinate_type bloating) 
Performs resize operation, inflating by bloating ammount. If
negative the result is a shrink instead of bloat. Returns
reference to modified argument. Expected n log n runtime, worst
case quadratic runtime wrt. vertices + intersections. 
template <typename T1, typename
T2>
T1& operator=(const T1&, coordinate_type shrinking) 
Performs resize operation, deflating by bloating ammount. If
negative the result is a bloat instead of shrink. Returns
reference to modified argument. Expected n log n runtime, worst
case quadratic runtime wrt. vertices + intersections. 
Functions
template <typename T1, typename
T2>
T1& assign(T1& lvalue, const T2& rvalue) 
Eliminates overlaps in geometry and copies from an object that
models polygon_set or any of its refinements into an object that
models polygon_set. Expected n log n runtime, worst case quadratic
runtime wrt. vertices + intersections. 
template <typename T1, typename
T2>
bool equivalence(const T1& lvalue, const T2& rvalue) 
Returns true if an object that models polygon_set or one of its
refinements covers the exact same geometric regions as another object
that models polygon_set or one of its refinements. For example:
two of polygon objects. Expected n log n runtime, worst case
quadratic runtime wrt. vertices + intersections. 
template <typename
output_container_type, typename T>
void get_trapezoids(output_container_type& output,
const T& polygon_set) 
Output container is expected to be a standard container.
Slices geometry of an object that models polygon_set or one of its
refinements into non overlapping trapezoids along a vertical slicing
orientation and appends them to the
output, which must have a value type that models polygon or polygon_with_holes.
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
template <typename
output_container_type, typename T>
void get_trapezoids(output_container_type& output,
const T& polygon_set,
orientation_2d orient) 
Output container is expected to be a standard container.
Slices geometry of an object that models polygon_set or one of its
refinements into non overlapping trapezoids along a the specified slicing
orientation and appends them to the
output, which must have a value type that models polygon or polygon_with_holes.
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
template <typename
polygon_set_type>
void clear(polygon_set_type& polygon_set) 
Makes the object empty of geometry. 
template <typename
polygon_set_type>
bool empty(const polygon_set_type& polygon_set) 
Checks whether the object is empty of geometry. Polygons that
are completely covered by holes will result in empty returning true.
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
template <typename T, typename
rectangle_type>
bool extents(rectangle_type& extents_rectangle,
const
T& polygon_set) 
Computes bounding box of an object that models polygon_set and
stores it in an object that models rectangle. If the polygon set
is empty returns false. If there are holes outside of shells they
do not contribute to the extents of the polygon set. Expected n
log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
template <typename T>
area_type area(const T& polygon_set) 
Computes the area covered by geometry in an object that models
polygon_set. Expected n log n runtime, worst case quadratic
runtime wrt. vertices + intersections. 
template <typename T>
T& bloat(T& polygon_set, unsigned_area_type bloating) 
Same as getting all the polygons, bloating them and putting them
back. Expected n log n runtime, worst case quadratic runtime wrt.
vertices + intersections. 
template <typename T>
T& shrink(T& polygon_set, unsigned_area_type shrinking) 
Same as getting all the polygons, shrinking them and overwriting
the polygon set with the resulting regions. Expected n log n
runtime, worst case quadratic runtime wrt. vertices + intersections. 
template <typename T, typename
coord_type>
T& resize(T& polygon_set, coord_type resizing,
bool corner_fill_arc = false,
unsigned int num_circle_segments = 0) 
Same as bloat if resizing is positive, same as shrink if resizing is
negative. Original topology at acute angle vertices is preserved
by default, segmented circular arcs are inserted if corner_fill_arc is
true. num_circle_segments specifies number of segments to
introduce on a full circle when filling acute angle corners with
circular arcs. Expected n log n runtime, worst case quadratic
runtime wrt. vertices + intersections. 
template <typename T>
T& scale_up(T& polygon_set, unsigned_area_type factor) 
Scales geometry up by unsigned factor. Expected n log n
runtime, worst case quadratic runtime wrt. vertices + intersections. 
template <typename T>
T& scale_down(T& polygon_set, unsigned_area_type factor) 
Scales geometry down by unsigned factor. Expected n log n
runtime, worst case quadratic runtime wrt. vertices + intersections. 
template <typename T, typename transformation_type>
T& transform(T& polygon_set,
const
transformation_type& transformation) 
Applies transformation.transform() on all vertices. Expected n
log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
template <typename T>
T& keep(T& polygon_set,
unsigned_area_type min_area,
unsigned_area_type max_area,
unsigned_area_type min_width,
unsigned_area_type max_width,
unsigned_area_type min_height,
unsigned_area_type max_height) 
Retains only regions that satisfy the min/max criteria in the
argument list. Note: useful for visualization to cull too small
polygons. Expected n log n runtime, worst case quadratic runtime
wrt. vertices + intersections. 
Polygon Set Data Object
The polygon set data type encapsulates the internal data format that
serves as the input to the sweepline algorithm that implements polygonclipping
Boolean operations. It also internally keeps track of whether that data
has been sorted or scanned and maintains the invariant that when its flags
indicate that the data is sorted or scanned the data has not been changed to
violate that assumption. Using the Polygon Set Data type directly can
be more efficient than using lists and vectors of polygons in the functions
above because of the invariants it can enforce which provide the opportunity to
maintain the data is sorted form rather than going all the way out to polygons
then resorting those vertices for a subsequent operation.
The declaration of Polygon Set Data is the following:
template <typename T>
class polygon_set_data;
The class is parameterized on the coordinate data type. Algorithms that
benefit from knowledge of the invariants enforced by the class are implemented
as member functions to provide them access to information about those
invariants.
Example code polygon_set_usage.cpp
demonstrates using
the library provided polygon set data types and functions
Member Functions
polygon_set_data() 
Default constructor. 
template <typename iT>
polygon_set_data(iT input_begin, iT
input_end) 
Construct with scanning orientation from an iterator range of
insertable objects. 
polygon_set_data(const polygon_set_data& that) 
Copy construct. 
template <typename l, typename r, typename op>
polygon_set_data(const polygon_set_view<l,r,op>&
t) 
Copy construct from a Boolean operator template. 
polygon_set_data& operator=(const polygon_set_data& that) 
Assignment from another polygon set, may change scanning
orientation. 
template <typename l, typename r, typename op>
polygon_set_data& operator=(const polygon_set_view<l, r,
op>& that) 
Assignment from a Boolean operator template. 
template <typename geometry_object>
polygon_set_data& operator=(const geometry_object& geo) 
Assignment from an insertable object. 
template <typename iT>
void insert(iT input_begin, iT input_end) 
Insert objects of an iterator range. Linear wrt vertices
inserted. 
void insert(const polygon_set_data& polygon_set) 
Insert a polygon set. Linear wrt vertices inserted. 
template <typename geometry_type>
void insert(const geometry_type& geometry_object, bool is_hole
= false) 
Insert a geometry object, if is_hole is true then the inserted
region is subtractive rather than additive. Linear wrt vertices
inserted. 
template <typename output_container>
void get(output_container& output) const 
Expects a standard container of polygons objects. Will scan
and eliminate overlaps. Converts polygon set geometry to objects
of the polygon type and appends them to the container. Polygons
will be output with counterclockwise winding, hole polygons will be
output with clockwise winding. The last vertex of an output
polygon is the duplicate of the first, and the number of points is equal
to the number of edges plus 1. If required by the output data
type, polygons will have holes fractured out to the outer boundary along
the positive y direction and off grid intersections on the outer
boundary introduced by this fracture will be truncated downward.
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
template <typename output_container>
void get_trapezoids(output_container& output) const 
Expects a standard container of polygon objects. Will scan
and eliminate overlaps. Slices polygon set geometry to trapezoids
vertically and appends them to the container. Expected n log n
runtime, worst case quadratic runtime wrt. vertices + intersections. 
template <typename output_container>
void get_trapezoids(output_container& output, orientation_2d
slicing_orientation) const

Expects a standard container of polygon objects. Will scan
and eliminate overlaps. Slices polygon set geometry to trapezoids
along the given orientation and appends them to the container.
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
bool operator==(const polygon_set_data& p) const 
Once scanned the data representation of geometry within a polygon
set is in a mathematically canonical form. Comparison between two
sets is therefore a linear time operation once they are in the scanned
state. Will scan and eliminate overlaps in both polygon sets.
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
bool operator!=(const polygon_set_data& p) const 
Inverse logic of equivalence operator. 
void clear() 
Make the polygon set empty. Note: does not deallocate memory.
Use shrink to fit idiom and assign default constructed polygon set to
deallocate. 
bool empty() const

Check whether the polygon set contains no geometry. Will scan
and eliminate overlaps because subtractive regions might make the
polygon set empty. Expected n log n runtime, worst case quadratic
runtime wrt. vertices + intersections. 
void clean() const 
Scan and eliminate overlaps. Expected n log n runtime, worst
case quadratic runtime wrt. vertices + intersections the first time,
constant time subsequently. 
template <typename input_iterator_type>
void set(input_iterator_type input_begin, input_iterator_type input_end)

Overwrite geometry in polygon set with insertable objects in the
iterator range. 
template <typename rectangle_type>
bool extents(rectangle_type& extents_rectangle) const 
Given an object that models rectangle, scans and eliminates overlaps
in the polygon set because subtractive regions may alter its extents
then computes the bounding box and assigns it to extents_rectangle.
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
intersections the first time, linear subsequently. 
polygon_set_data&
resize(coord_type resizing,
bool corner_fill_arc = false,
unsigned int num_circle_segments = 0) 
Inflates if resizing is positive, deflates if resizing is
negative. Original topology at acute angle vertices is preserved
by default, segmented circular arcs are inserted if corner_fill_arc is
true. num_circle_segments specifies number of segments to
introduce on a full circle when filling acute angle corners with
circular arcs. Specifying zero for num_circle_segments results in
only a single segment being inserted at acute corners. Expected n
log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
template <typename transformation_type>
polygon_set_data& transform(const transformation_type& transformation)

Applies transformation.transform() on vertices stored within the
polygon set. Expected n log n runtime, worst case quadratic
runtime wrt. vertices + intersections. 
polygon_set_data& scale_up(unsigned_area_type factor) 
Scales vertices stored within the polygon set up by factor.
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
polygon_set_data& scale_down(unsigned_area_type
factor) 
Scales vertices stored within the polygon set down by factor.
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
template <typename scaling_type>
polygon_set_data& scale(const scaling_type&
f) 
Scales vertices stored within the polygon set by applying f.scale().
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
intersections. 
