Polygon Sponsor

Polygon 90 Set Concept
The polygon_90_set concept tag is
polygon_90_set_concept
The semantic of a polygon_90_set is zero or more
Manhattan geometry regions.
The motivation for providing the
polygon_90_set_concept is that it is a very common special case of planar
geometry which afford the implementation of a variety of optimizations on the
general planar geometry algorithms. Manhattan geometry processing by the
polygon_90_set_concept can be 100X faster than arbitrary angle polygon
manipulation. Because the performance benefits are so large and the
special case is important enough, the library provides these performance
benefits for those application domains that require them. Users are recommended to use std::vector and std::list of user defined polygons
or library provided polygon_90_set_data<coordinate_type> objects. Lists
and vectors of models of polygon_90_concept or polygon_90_with_holes_concept or
rectangle_concept are automatically models of polygon_90_set_concept.
Operators
The return type of some operators is the polygon_90_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_90_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_90_set_view operator(const T1& l, const T2& r) 
Boolean OR operation (polygon set union). Accepts two objects
that model polygon_90_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_90_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_90_set_view operator&(const T1& l, const T2& r) 
Boolean AND operation (polygon set intersection). Accepts two
objects that model polygon_90_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_90_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_90_set_view operator^(const T1& l, const T2& r) 
Boolean XOR operation (polygon set disjointunion). Accepts
two objects that model polygon_90_set or one of its refinements.
O( n log n) runtime complexity and O(n) memory wrt vertices +
intersections. O( n log n) runtime complexity and O(n) memory wrt
vertices + intersections. 
template <typename T1, typename
T2>
polygon_90_set_view operator(const T1& l, const T2& r) 
Boolean SUBTRACT operation (polygon set difference). Accepts
two objects that model polygon_90_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_90_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_90_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_90_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_90_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_90_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_90_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_90_set or any of its refinements into an object that
models polygon_90_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_90_set or one of its
refinements covers the exact same geometric regions as another object
that models polygon_90_set or one of its refinements. For example:
two of polygon_90 objects. O( n log n) runtime complexity and O(n)
memory wrt vertices + intersections. 
template <typename
output_container_type, typename T>
void get_rectangles(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_90_set or one of its
refinements into non overlapping rectangles and appends them to the
output. O( n log n) runtime complexity and O(n) memory wrt
vertices + intersections. 
template <typename
output_container_type, typename T>
void get_max_rectangles(output_container_type& output,
const T& polygon_set) 
Output container is expected to be a standard container. Given
an object that models polygon_90_set or one of its refinements finds all
overlapping rectangles that are maximal in area and appends them to the
output. Expected n log n runtime, worst case quadratic rutnime. 
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 +
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_90_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 + intersections. 
template <typename T>
manhattan_area_type area(const T& polygon_set) 
Computes the area covered by geometry in an object that models
polygon_90_set. O( n log n) runtime complexity and O(n) memory wrt
vertices + intersections. 
template <typename T1, typename
T2>
T1& interact(T1& a, const T2& b) 
Given an object that models polygon_90_set and an object that models
polygon_90_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 + intersections. 
template <typename T>
T& self_intersect(T& polygon_set) 
Given an object that models polygon_90_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_90_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 rectangles, bloating them and putting them
back. O( n log n) runtime complexity and O(n) memory wrt vertices
+ intersections. 
template <typename T>
T& bloat(T& polygon_set, orientation_2d orient,
unsigned_area_type bloating) 
Same as getting all the rectangles, bloating them and putting them
back. O( n log n) runtime complexity and O(n) memory wrt vertices
+ intersections. 
template <typename T>
T& bloat(T& polygon_set, orientation_2d orient,
unsigned_area_type low_bloating,
unsigned_area_type
high_bloating) 
Same as getting all the rectangles, bloating them and putting them
back. O( n log n) runtime complexity and O(n) memory wrt vertices
+ intersections. 
template <typename T>
T& bloat(T& polygon_set, direction_2d dir,
unsigned_area_type bloating) 
Same as getting all the rectangles, bloating them and putting them
back. O( n log n) runtime complexity and O(n) memory wrt vertices
+ intersections. 
template <typename T>
T& bloat(T& polygon_set,
unsigned_area_type
west_bloating,
unsigned_area_type
east_bloating,
unsigned_area_type
south_bloating,
unsigned_area_type
north_bloating) 
Same as getting all the rectangles, 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 rectangles of the inverse, bloating them and overwriting
the polygon set with the resulting regions then negating. O( n log
n) runtime complexity and O(n) memory wrt vertices + intersections. 
template <typename T>
T& shrink(T& polygon_set, orientation_2d orient,
unsigned_area_type
shrinking) 
Same as getting all the rectangles of the inverse, bloating them and overwriting
the polygon set with the resulting regions then negating. O( n log
n) runtime complexity and O(n) memory wrt vertices + intersections. 
template <typename T>
T& shrink(T& polygon_set, orientation_2d orient,
unsigned_area_type
low_shrinking,
unsigned_area_type
high_shrinking) 
Same as getting all the rectangles of the inverse, bloating them and overwriting
the polygon set with the resulting regions then negating. O( n log
n) runtime complexity and O(n) memory wrt vertices + intersections. 
template <typename T>
T& shrink(T& polygon_set, direction_2d dir,
unsigned_area_type
shrinking) 
Same as getting all the rectangles of the inverse, bloating them and overwriting
the polygon set with the resulting regions then negating. O( n log
n) runtime complexity and O(n) memory wrt vertices + intersections. 
template <typename T>
T& shrink(T& polygon_set,
unsigned_area_type
west_shrinking,
unsigned_area_type
east_shrinking,
unsigned_area_type
south_shrinking,
unsigned_area_type
north_shrinking) 
Same as getting all the rectangles of the inverse, bloating them and overwriting
the polygon set with the resulting regions then negating. 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) 
Same as bloat if resizing is positive, same as shrink if resizing is
negative. 
template <typename T, typename
coord_type>
T& resize(polygon_set_type& polygon_set,
coord_type west, coord_type east,
coord_type south, coord_type north) 
Same as bloat if resizing is positive, same as shrink if resizing is
negative. 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& grow_and(T& polygon_set, orientation_2d orient,
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& grow_and(T& polygon_set, orientation_2d orient,
unsigned_area_type low_bloating,
unsigned_area_type high_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& grow_and(T& polygon_set, direction_2d dir,
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& grow_and(T& polygon_set,
unsigned_area_type west_bloating,
unsigned_area_type east_bloating,
unsigned_area_type south_bloating,
unsigned_area_type north_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 + intersections. 
template <typename T>
T& scale_down(T& polygon_set, unsigned_area_type factor) 
Scales geometry down by unsigned factor. O( n log n) runtime
complexity and O(n) memory wrt vertices + intersections. 
template <typename T, typename scaling_type>
T& scale(polygon_set_type& polygon_set,
const scaling_type& scaling) 
Scales geometry by applying scaling.scale() on all vertices.
O( n log n) runtime complexity and O(n) memory wrt vertices +
intersections. 
template <typename T, typename coord_type>
T& move(T& polygon_set,
orientation_2d orient, coord_type
displacement) 
Moves geometry by displacement amount in the orientation.
O( n log n) runtime complexity and O(n) memory wrt vertices +
intersections. 
template <typename T, typename coord_type>
T& move(T& polygon_set, coord_type x_displacement,
coord_type y_displacement) 
Moves the geometry by x_dispacement in x and y_displacement in y.
Note: for consistency should be convolve(polygon_set, point). O( n
log n) runtime complexity and O(n) memory wrt vertices + intersections. 
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 + 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. O( n log n) runtime complexity and O(n) memory wrt
vertices + intersections. 
Polygon 90 Set Data Object
The polygon 90 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 90 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 90 Set Data is the following:
template <typename T>
class polygon_90_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_90_set_data() 
Default constructor. Scanning orientation defaults to
HORIZONTAL 
polygon_90_set_data(orientation_2d
orient) 
Construct with scanning orientation. 
template <typename iT>
polygon_90_set_data(orientation_2d orient,
iT input_begin, iT input_end) 
Construct with scanning orientation from an iterator range of
insertable objects. 
polygon_90_set_data(const polygon_90_set_data& that) 
Copy construct. 
template <typename l, typename r, typename op>
polygon_90_set_data(const polygon_90_set_view<l,r,op>&
t) 
Copy construct from a Boolean operator template. 
polygon_90_set_data(orientation_2d orient,
const polygon_90_set_data& that) 
Construct with scanning orientation and copy from another polygon
set. 
polygon_90_set_data& operator=(const polygon_90_set_data& that) 
Assignment from another polygon set, may change scanning
orientation. 
template <typename l, typename r, typename op>
polygon_90_set_data& operator=(const polygon_90_set_view<l, r,
op>& that) 
Assignment from a Boolean operator template. 
template <typename geometry_object>
polygon_90_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. inserted
vertices. 
void insert(const polygon_90_set_data& polygon_set) 
Insert a polygon set. Linear wrt. inserted vertices. 
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. inserted
vertices. 
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 complexity 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 direction of the scanline
orientation of the polygon set. O( n log n) runtime complexity and
O(n) memory wrt vertices + intersections. 
template <typename output_container>
void get_rectangles(output_container& output) const 
Expects a standard container of rectangle objects. Will scan
and eliminate overlaps. Slices polygon set geometry to rectangles
along the scanning orientation and appends them to the container.
O( n log n) runtime complexity and O(n) memory wrt vertices +
intersections. 
template <typename output_container>
void get_rectangles(output_container& output, orientation_2d
slicing_orientation) const

Expects a standard container of rectangle objects. Will scan
and eliminate overlaps. Slices polygon set geometry to rectangles
along the given orientation and appends them to the container. O(
n log n) runtime complexity and O(n) memory wrt vertices +
intersections. 
bool operator==(const polygon_90_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 complexity and O(n) memory wrt vertices + intersections
the first time, linear subsequently. 
bool operator!=(const polygon_90_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 complexity and O(n) memory
wrt vertices + intersections the first time, linear subsequently. 
orientation_2d orient() const 
Get the scanning orientation. Depending on the data it is
sometimes more efficient to scan in a specific orientation. This
is particularly true of Manhattan geometry data. Constant time. 
void clean() const 
Scan and eliminate overlaps. O( n log n) runtime complexity
and O(n) memory 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,
orientation_2d orient)

Overwrite geometry in polygon set with insertable objects in the
iterator range. Also sets the scanning orientation to that
specified. 
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 complexity and O(n) memory wrt vertices +
intersections the first time, linear subsequently. 
polygon_90_set_data&
bloat(unsigned_area_type west_bloating,
unsigned_area_type east_bloating,
unsigned_area_type south_bloating,
unsigned_area_type north_bloating) 
Scans to eliminate overlaps and subtractive regions. Inserts
rectangles of width specified by bloating values to the indicated side
of geometry within the polygon set and fills corners with rectangles of
the length and width specified for the adjacent sides. O( n log n)
runtime complexity and O(n) memory wrt vertices + intersections. 
polygon_90_set_data&
shrink(unsigned_area_type west_shrinking,
unsigned_area_type east_shrinking,
unsigned_area_type south_shrinking,
unsigned_area_type north_shrinking) 
Scans to eliminate overlaps and subtractive regions. Inserts
subtractiive rectangles of width specified by bloating values to the
indicated side of geometry within the polygon set and subtractive
rectangle at convex corners of the length and width specified for the
adjacent sides. Scans to eliminate overlapping subtractive
regions. O( n log n) runtime complexity and O(n) memory wrt
vertices + intersections. 
polygon_90_set_data&
resize(coordinate_type west, coordinate_type east, coordinate_type south, coordinate_type north) 
Call bloat or shrink or shrink then bloat depending on whether the
resizing values are positive or negative. O( n log n) runtime
complexity and O(n) memory wrt vertices + intersections. 
polygon_90_set_data& move(coordinate_type x_delta,
coordinate_type y_delta)

Add x_delta to x values and y_delta to y values of vertices stored
within the polygon set. Linear wrt. vertices. 
template <typename transformation_type>
polygon_90_set_data& transform(const transformation_type& transformation)

Applies transformation.transform() on vertices stored within the
polygon set. Linear wrt. vertices. 
polygon_90_set_data& scale_up(unsigned_area_type factor) 
Scales vertices stored within the polygon set up by factor.
Linear wrt. vertices. 
polygon_90_set_data& scale_down(unsigned_area_type
factor) 
Scales vertices stored within the polygon set down by factor.
Linear wrt. vertices. 
template <typename scaling_type>
polygon_90_set_data& scale(const anisotropic_scale_factor<scaling_type>&
f) 
Scales vertices stored within the polygon set by applying f.scale().
Linear wrt. vertices. 
polygon_90_set_data& scale(double factor) 
Scales vertices stored within the polygon set by floating point
factor. Linear wrt. vertices. 
polygon_90_set_data& self_xor() 
Retain only nonoverlapping regions of geometry within polygon set.
O( n log n) runtime complexity and O(n) memory wrt vertices +
intersections. 
polygon_90_set_data& self_intersect() 
Retain only overlapping regions of geometry within a polygon set.
O( n log n) runtime complexity and O(n) memory wrt vertices +
intersections. 
polygon_90_set_data& interact(const polygon_90_set_data& that) 
Retain only regions that touch or overlap regions in argument.
O( n log n) runtime complexity and O(n) memory wrt vertices +
intersections. 
