Polygon Sponsor

Polygon 45 Set Concept
The polygon_45_set concept tag is
polygon_45_set_concept
The semantic of a
polygon_45_set is zero or more geometry regions which have angles at
the vertices that are multiples of 45degrees relative to the
coordinate axis. A Polygon 45 Set Concept makes no sense in
floating point, but currently does not provide a static assert to
prevent it from being used with floating point coordinates. The
result of such use is undefined. When the intersection of two 45
degree edges results in a vertex that is off the integer grid that case
is handled by inserting a unit length edge between the two 45 degree
edges near the off grid intersection point. In the case that data
represented contains no 45degree angles and is Manhattan a runtime
check will default to the Manhattan algorithm. The results of
which are identical to what the 45degree algorithm would do, but
obtained more efficiently.
The motivation for providing
the polygon_45_set is to extend the special case of Manhattan geometry
capability of the library to encompass the slightly less common, but
still important special case of geometry that is described by angles
that are multiples of 45degress with respect to the coordinate
axis. This simplifies the implementation of geometry algorithms
and affords many opportunities for optimization. 45degree
algorithms can be 50X faster than arbitrary angle algorithms and are
required to provide a complete feature set that meets the performance
requirements of application domains in which Manhattan and 45degree
geometry are a common special case.
Users are recommended to use std::vector and std::list of user
defined polygons or library provided
polygon_45_set_data<coordinate_type> objects. Lists and
vectors of models of polygon_45_concept or
polygon_45_with_holes_concept are automatically models of
polygon_45_set_concept.
An object that is a model of
polygon_45_set_concept can be viewed as a model of
polygon_90_set_concept if it is determined at runtime to conform
to the restriction that all edges are axisparallel. This concept
casting is accomplished through the view_as<>()
function.
view_as<polygon_90_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_45_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_45_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_45_set_view operator(const T1& l, const T2& r) 
Boolean OR operation (polygon set union). Accepts
two objects that model polygon_45_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().
O( n log n) runtime complexity and O(n) memory wrt vertices +
intersections. 
template
<typename T1, typename T2>
polygon_45_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. O( n log n) runtime
complexity and O(n) memory wrt vertices + intersections. 
template
<typename T1, typename T2>
polygon_45_set_view operator&(const T1& l, const
T2& r) 
Boolean AND operation (polygon set intersection).
Accepts two objects that model polygon_45_set or one of its
refinements. O( n log n) runtime complexity and O(n) memory wrt
vertices + intersections. 
template
<typename T1, typename T2>
polygon_45_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. O(
n log n) runtime complexity and O(n) memory wrt vertices +
intersections. 
template
<typename T1, typename T2>
polygon_45_set_view operator^(const T1& l, const T2& r) 
Boolean XOR operation (polygon set
disjointunion). Accepts two objects that model polygon_45_set or
one of its refinements. O( n log n) runtime complexity and O(n)
memory wrt vertices + intersections. 
template
<typename T1, typename T2>
polygon_45_set_view operator(const T1& l, const T2& r) 
Boolean SUBTRACT operation (polygon set
difference). Accepts two objects that model polygon_45_set or one
of its refinements. O( n log n) runtime complexity and O(n)
memory 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_45_set and not one of it's
refinements. O( n log n) runtime complexity and O(n) memory 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_45_set and not one of it's
refinements. O( n log n) runtime complexity and O(n) memory 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_45_set and not one of it's
refinements. O( n log n) runtime complexity and O(n) memory 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_45_set and not one of it's
refinements. O( n log n) runtime complexity and O(n) memory 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_45_set and not one of it's
refinements. O( n log n) runtime complexity and O(n) memory 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_45_set and not one of it's
refinements. O( n log n) runtime complexity and O(n) memory 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. O( n log n) runtime
complexity and O(n) memory 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. O( n log n) runtime
complexity and O(n) memory 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. O( n log n)
runtime complexity and O(n) memory 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. O( n log n)
runtime complexity and O(n) memory 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_45_set or any of its refinements into an
object that models polygon_45_set. O( n log n) runtime complexity
and O(n) memory wrt vertices + intersections. 
template
<typename T1, typename T2>
bool equivalence(const T1& lvalue, const T2& rvalue) 
Returns true if an object that models polygon_45_set or
one of its refinements covers the exact same geometric regions as
another object that models polygon_45_set or one of its
refinements. For example: two of polygon_45 objects. O( n
log n) runtime complexity and O(n) memory 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_45_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_45,
polygon_45_with_holes, polygon or polygon_with_holes. O( n
log n) runtime complexity and O(n) memory wrt vertices. 
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_45_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_45,
polygon_45_with_holes, polygon or polygon_with_holes. O( n
log n) runtime complexity and O(n) memory wrt vertices. 
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. O( n log n) runtime complexity and O(n)
memory wrt vertices. 
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_45_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. O( n log n) runtime complexity and O(n) memory wrt
vertices. 
template
<typename T>
area_type area(const T& polygon_set) 
Computes the area covered by geometry in an object that
models polygon_45_set. O( n log n) runtime complexity and
O(n) memory wrt vertices. 
template
<typename T1, typename T2>
T1& interact(T1& a, const T2& b) 
Given an object that models polygon_45_set and an
object that models polygon_45_set or one of its refinements, modifies a
to retain only regions that overlap or touch regions in b.
O( n log n) runtime complexity and O(n) memory wrt vertices plus
intersections. 
template
<typename T>
T& self_intersect(T& polygon_set) 
Given an object that models polygon_45_set that has
self overlapping regions, modifies the argument to contain only the
regions of overlap. O( n log n) runtime complexity and O(n)
memory wrt vertices + intersections. 
template
<typename T>
T& self_xor(T& polygon_set) 
Given an object that models polygon_45_set that has
self overlapping regions, modifies the argument to contain only the
regions that do not overlap. O( n log n) runtime complexity and
O(n) memory 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. O( n log n) runtime complexity and O(n) memory
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. O( n log
n) runtime complexity and O(n) memory wrt vertices + intersections. 
template
<typename T, typename coord_type>
T& resize(T& polygon_set, coord_type resizing,
RoundingOption
rounding = CLOSEST,
CornerOption
corner = INTERSECTION) 
Same as bloat if resizing is positive, same as shrink
if resizing is negative. RoundingOption is an enum that controls
snapping of noninteger results of resizing 45 degree edges.
CornerOption is an enum that controls how corner filling is
performed. polygon_45_set_data.hpp defines these enums. O(
n log n) runtime complexity and O(n) memory wrt vertices +
intersections. 
template
<typename T>
T& grow_and(T& polygon_set, unsigned_area_type bloating) 
Same as bloating nonoverlapping regions and then
applying self intersect to retain only the overlaps introduced by the
bloat. O( n log n) runtime complexity and O(n) memory wrt
vertices + intersections. 
template
<typename T>
T& scale_up(T& polygon_set, unsigned_area_type factor) 
Scales geometry up by unsigned factor. O( n log
n) runtime complexity and O(n) memory wrt vertices. 
template
<typename T>
T& scale_down(T& polygon_set, unsigned_area_type factor) 
Scales geometry down by unsigned factor. Snaps 45
degree edges back to 45 degrees after division truncation leads to
small changes in angle. O( n log n) runtime complexity and O(n)
memory wrt vertices. 
template
<typename T, typename scaling_type>
T& scale(polygon_set_type& polygon_set, double scaling) 
Scales geometry by multiplying by floating point
factor. Snaps 45 degree edges back to 45 degrees after
truncation of fractional results of multiply leads to small changes in
angle. O( n log n) runtime complexity and O(n) memory wrt
vertices. 
template
<typename T, typename transformation_type>
T& transform(T& polygon_set,
const transformation_type& transformation) 
Applies transformation.transform() on all
vertices. O( n log n) runtime complexity and O(n) memory wrt
vertices. 
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. O( n log n) runtime complexity and O(n) memory
wrt vertices. 
Polygon 45 Set Data Object
The polygon 45 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 45 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 45 Set Data is the following:
template <typename T>
class polygon_45_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.
Member Functions
polygon_45_set_data() 
Default constructor. 
template
<typename iT>
polygon_45_set_data(iT input_begin, iT input_end) 
Construct from an iterator range of insertable objects. 
polygon_45_set_data(const
polygon_45_set_data& that) 
Copy construct. 
template
<typename l, typename r, typename op>
polygon_45_set_data(const
polygon_45_set_view<l,r,op>& t) 
Copy construct from a Boolean operator template. 
polygon_45_set_data&
operator=(const polygon_45_set_data& that) 
Assignment from another polygon set, may change
scanning orientation. 
template
<typename l, typename r, typename op>
polygon_45_set_data&
operator=(const polygon_45_set_view<l, r,
op>& that) 
Assignment from a Boolean operator template. 
template
<typename geometry_object>
polygon_45_set_data& operator=(const geometry_object&
geo) 
Assignment from an insertable object. 
template <typename iT>
void insert(iT input_begin, iT input_end,
bool
is_hole = false) 
Insert objects of an iterator range. If is_hole
is true inserts subtractive regions. Linear wrt the number of
vertices added. 
void insert(const polygon_45_set_data& polygon_set,
bool
is_hole = false) 
Insert a polygon set. Linear wrt the number of
vertices added. 
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
the number of vertices added. 
template
<typename output_container>
void get(output_container& output) const 
Expects a standard container of geometry objects.
Will scan and eliminate overlaps. Converts polygon set geometry
to objects of that 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 not the duplicate of the first, and the number of
points is equal to the number of edges. O(n log n) runtime and
O(n) memory wrt. vertices + intersections. 
template
<typename output_container>
void get_polygons(output_container& output) const 
Expects a standard container of polygon objects.
Will scan and eliminate overlaps. Converts polygon set geometry
to polygons and appends them to the container. Polygons will have
holes fractured out to the outer boundary along the positive y
direction. O(n log n) runtime and O(n) memory wrt. vertices +
intersections. 
template
<typename output_container>
void get_polygons_with_holes(output_container& o) const 
Expects a standard container of polygon with holes
objects. Will scan and eliminate overlaps. Converts polygon
set geometry to polygons and appends them to the container. O(n
log n) runtime and O(n) memory 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. O(n log
n) runtime and O(n) memory 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. O(n log n) runtime and O(n) memory wrt. vertices +
intersections. 
bool operator==(const polygon_45_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. O(n log n) runtime and O(n) memory wrt. vertices +
intersections the first time and linear runtime and constant memory
subsequently. 
bool operator!=(const
polygon_45_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. O(n log n) runtime and
O(n) memory wrt. vertices + intersections the first time and linear
runtime and constant memory subsequently. 
bool is_manhattan()
const 
Returns in constant time the information about whether
the geometry contains only Manhattan (axisparallel rectilinear)
edges. Constant time. 
void clean()
const 
Scan and eliminate overlaps. O(n log n) runtime
and O(n) memory wrt. vertices + intersections the first time and linear
runtime and constant memory 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. O(n log n) runtime and O(n) memory wrt.
vertices the first time and linear runtime and constant memory
subsequently. 
polygon_45_set_data&
resize(coord_type resizing,
RoundingOption rounding = CLOSEST,
CornerOption corner = INTERSECTION) 
Same as bloat if resizing is positive, same as shrink
if resizing is negative. RoundingOption is an enum that controls
snapping of noninteger results of resizing 45 degree edges.
CornerOption is an enum that controls how corner filling is
performed. polygon_45_set_data.hpp defines these enums. O(n
log n) runtime and O(n) memory wrt. vertices + intersections. 
template
<typename transformation_type>
polygon_45_set_data&
transform(const transformation_type&
transformation) 
Applies transformation.transform() on vertices stored
within the polygon set. O(n log n) runtime and O(n) memory wrt.
vertices + intersections. 
polygon_45_set_data&
scale_up(unsigned_area_type factor) 
Scales vertices stored within the polygon set up by
factor. Linear wrt vertices. 
polygon_45_set_data&
scale_down(unsigned_area_type factor) 
Scales vertices stored within the polygon set down by
factor. Linear wrt vertices. 
polygon_45_set_data&
scale(double factor) 
Scales vertices stored within the polygon set by
floating point factor. Linear wrt vertices. 
polygon_45_set_data&
self_xor() 
Retain only nonoverlapping regions of geometry within
polygon set. O(n log n) runtime and O(n) memory wrt. vertices +
intersections. 
polygon_45_set_data&
self_intersect() 
Retain only overlapping regions of geometry within a
polygon set. O(n log n) runtime and O(n) memory wrt. vertices +
intersections. 
bool has_error_data()
const 
Returns true if noninteger intersections resulted in
small artifacts in the output of a boolean. Constant time. 
std::size_t error_count()
const 
Returns the number of artifacts that may potentially be
present in the output due to noninteger intersections. Constant
time. 
void get_error_data(polygon_45_set_data&
p) const 
Populates the input polygon set with 1x1 unit squares
that bound the error that may be present in the output due to
noninteger intersections. Linear wrt. vertices of error data. 
polygon_45_set_data&
self_intersect() 
Retain only overlapping regions of geometry within a
polygon set. O(n log n) runtime and O(n) memory wrt. vertices +
intersections. 
