目录

其他资源

多边形赞助商

多边形 45 集概念

polygon_45_set 概念标签是polygon_45_set_concept

polygon_45_set 的语义是零个或多个几何区域，其顶点的角度相对于坐标轴是 45 度的倍数。多边形 45 集概念在浮点数中没有意义，但目前没有提供静态断言来阻止它与浮点坐标一起使用。这种使用的结果是未定义的。当两个 45 度边的交点导致一个偏离整数网格的顶点时，这种情况通过在偏离网格交点附近插入一个单位长度的边来处理。如果表示的数据不包含 45 度角且是曼哈顿距离，则运行时检查将默认为曼哈顿算法。其结果与 45 度算法相同，但效率更高。

提供 polygon_45_set 的动机是将库的曼哈顿几何能力的特殊情况扩展到包含稍微不常见但仍然重要的几何特殊情况，该情况由相对于坐标轴为 45 度倍数的角度描述。这简化了几何算法的实现，并为优化提供了许多机会。45 度算法的速度可以比任意角度算法快 50 倍，并且需要提供满足曼哈顿和 45 度几何是常见特殊情况的应用领域的性能要求的完整功能集。

建议用户使用用户定义的多边形或库提供的 polygon_45_set_data 对象的 std::vector 和 std::list。polygon_45_concept 或 polygon_45_with_holes_concept 模型的列表和向量自动成为 polygon_45_set_concept 的模型。

一个模型的对象polygon_45_set_concept可以被视为模型polygon_90_set_concept如果在运行时确定它符合所有边都平行于坐标轴的限制。这种概念转换是通过view_as<>()函数实现的。

view_as<polygon_90_set_concept>(polygon_set_object)

的返回值view_as<>()可以传递到任何期望其模板参数中指定的概念类型对象的接口中。多边形集不能被视为单个多边形或矩形，因为通常无法知道多边形集是否只包含单个多边形，而不将其转换为多边形。

运算符

一些运算符的返回类型是polygon_45_set_view运算符模板类型。此类型本身是多边形 90 集概念的模型，而且还可以用作polygon_45_set_data构造函数和赋值运算符的参数。运算符模板的存在是为了在布尔运算符链接在一起时消除中间结果的临时副本。

运算符声明在命名空间内boost::polygon::operators.

template <typename T1, typename T2>
polygon_45_set_view operator|(const T1& l, const T2& r)		 布尔 OR 运算（多边形集并集）。接受两个多边形 45 集模型对象或其细化的对象。返回一个运算符模板，该模板在链接或嵌套在库函数调用（例如 assign()）中时按需执行操作。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
polygon_45_set_view operator+(const T1& l, const T2& r)		 与 operator| 相同。加号也用于布尔逻辑表达式中的 OR 运算。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
polygon_45_set_view operator&(const T1& l, const T2& r)		 布尔 AND 运算（多边形集交集）。接受两个多边形 45 集模型对象或其细化的对象。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
polygon_45_set_view operator*(const T1& l, const T2& r)		 与 operator& 相同。乘法符号也用于布尔逻辑表达式中的 AND 运算。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
polygon_45_set_view operator^(const T1& l, const T2& r)		 布尔 XOR 运算（多边形集不相交并集）。接受两个多边形 45 集模型对象或其细化的对象。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
polygon_45_set_view operator-(const T1& l, const T2& r)		 布尔 SUBTRACT 运算（多边形集差集）。接受两个多边形 45 集模型对象或其细化的对象。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
T1& operator|=(const T1& l, const T2& r)		 与 operator| 相同，但具有自赋值功能，左操作数必须是 polygon_45_set 模型，而不是其细化。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
T1& operator+=(T1& l, const T2& r)		 与 operator+ 相同，但具有自赋值功能，左操作数必须是 polygon_45_set 模型，而不是其细化。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
T1& operator&=(const T1& l, const T2& r)		 与 operator& 相同，但具有自赋值功能，左操作数必须是 polygon_45_set 模型，而不是其细化。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
T1& operator*=(T1& l, const T2& r)		 与 operator* 相同，但具有自赋值功能，左操作数必须是 polygon_45_set 模型，而不是其细化。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
T1& operator^=(const T1& l, const T2& r)		 与 operator^ 相同，但具有自赋值功能，左操作数必须是 polygon_45_set 模型，而不是其细化。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
T1& operator-=(T1& l, const T2& r)		 与 operator- 相同，但具有自赋值功能，左操作数必须是 polygon_45_set 模型，而不是其细化。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1>
T1 operator+(const T1&, coordinate_type bloating)		 执行调整大小操作，按 bloating 量膨胀。如果为负数，则结果是收缩而不是膨胀。注意：按值返回结果。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
T1 operator-(const T1&, coordinate_type shrinking)		 执行调整大小操作，按 bloating 量收缩。如果为负数，则结果是膨胀而不是收缩。注意：按值返回结果。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
T1& operator+=(const T1&, coordinate_type bloating)		 执行调整大小操作，按 bloating 量膨胀。如果为负数，则结果是收缩而不是膨胀。返回对修改后的参数的引用。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
T1& operator-=(const T1&, coordinate_type shrinking)		 执行调整大小操作，按 bloating 量收缩。如果为负数，则结果是膨胀而不是收缩。返回对修改后的参数的引用。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。

函数

template <typename T1, typename T2>
T1& assign(T1& lvalue, const T2& rvalue)		 消除几何体中的重叠，并将多边形 45 集模型对象或其任何细化中的对象复制到多边形 45 集模型对象中。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename T1, typename T2>
bool equivalence(const T1& lvalue, const T2& rvalue)		 如果多边形 45 集模型对象或其细化覆盖与另一个多边形 45 集模型对象或其细化完全相同的几何区域，则返回 true。例如：两个 polygon_45 对象。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点和交点）。
template <typename output_container_type, typename T>
void get_trapezoids(output_container_type& output,
                    const T& polygon_set)		 输出容器应为标准容器。将多边形 45 集模型对象或其细化的几何体沿垂直切片方向切成不相交的梯形，并将它们附加到输出中，输出必须具有 polygon_45、polygon_45_with_holes、polygon 或 polygon_with_holes 模型的值类型。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点）。
template <typename output_container_type, typename T>
void get_trapezoids(output_container_type& output,
                    const T& polygon_set,
                    orientation_2d orient)		 输出容器应为标准容器。将多边形 45 集模型对象或其细化的几何体沿指定的切片方向切成不相交的梯形，并将它们附加到输出中，输出必须具有 polygon_45、polygon_45_with_holes、polygon 或 polygon_with_holes 模型的值类型。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点）。
template <typename polygon_set_type>
void clear(polygon_set_type& polygon_set)		 使对象为空几何体。
template <typename polygon_set_type>
bool empty(const polygon_set_type& polygon_set)		 检查对象是否为空几何体。完全被孔覆盖的多边形将导致 empty 返回 true。时间复杂度为 O(n log n)，内存复杂度为 O(n)（关于顶点）。
template <typename T, typename rectangle_type>
bool extents(rectangle_type& extents_rectangle,
             const T& polygon_set)		 计算模拟 polygon_45_set 的对象的边界框，并将其存储到模拟 rectangle 的对象中。如果 polygon 集为空，则返回 false。如果孔洞位于壳的外部，则它们不会影响 polygon 集的范围。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数。
模板 <typename T>
area_type area(const T& polygon_set)		 计算模拟 polygon_45_set 的几何对象所覆盖的面积。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数。
template <typename T1, typename T2>
T1& interact(T1& a, const T2& b)		 给定一个模拟 polygon_45_set 的对象和一个模拟 polygon_45_set 或其细化版本的对象，修改 a 以仅保留与 b 中区域重叠或接触的区域。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数。
模板 <typename T>
T& self_intersect(T& polygon_set)		 给定一个模拟 polygon_45_set 的对象，该对象具有自重叠区域，修改参数以仅包含重叠区域。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数。
模板 <typename T>
T& self_xor(T& polygon_set)		 给定一个模拟 polygon_45_set 的对象，该对象具有自重叠区域，修改参数以仅包含不重叠的区域。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数。
模板 <typename T>
T& bloat(T& polygon_set, unsigned_area_type bloating)		 与获取所有多边形、膨胀它们然后放回相同。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数。
模板 <typename T>
T& shrink(T& polygon_set, unsigned_area_type shrinking)		 与获取所有多边形、收缩它们并用生成的区域覆盖 polygon 集相同。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数。
模板 <typename T, typename coord_type>
T& resize(T& polygon_set, coord_type resizing,
          RoundingOption rounding = CLOSEST,
          CornerOption corner = INTERSECTION)		 如果 resizing 为正，则与 bloat 相同；如果 resizing 为负，则与 shrink 相同。RoundingOption 是一个枚举，用于控制 45 度边的调整大小的非整数结果的捕捉。CornerOption 是一个枚举，用于控制角填充是如何执行的。polygon_45_set_data.hpp 定义了这些枚举。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数。
模板 <typename T>
T& grow_and(T& polygon_set, unsigned_area_type bloating)		 与膨胀非重叠区域，然后应用自相交以仅保留膨胀引入的重叠区域相同。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数。
模板 <typename T>
T& scale_up(T& polygon_set, unsigned_area_type factor)		 将几何图形按无符号因子放大。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数。
模板 <typename T>
T& scale_down(T& polygon_set, unsigned_area_type factor)		 将几何图形按无符号因子缩小。在除法截断导致角度发生细微变化后，将 45 度边捕捉回 45 度。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数。
模板 <typename T, typename scaling_type>
T& scale(polygon_set_type& polygon_set, double scaling)		 通过乘以浮点因子来缩放几何图形。在乘法的分数结果截断导致角度发生细微变化后，将 45 度边捕捉回 45 度。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数。
模板 <typename T, typename transformation_type>
T& transform(T& polygon_set,
             const transformation_type& transformation)		 对所有顶点应用 transformation.transform()。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数。
模板 <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)		 仅保留满足参数列表中最小/最大条件的区域。注意：对于剔除太小的多边形以进行可视化很有用。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数。

Polygon 45 集数据对象

polygon 45 集数据类型封装了内部数据格式，该格式用作实现多边形裁剪布尔运算的扫描线算法的输入。它还在内部跟踪数据是否已排序或扫描，并保持不变式：当其标志指示数据已排序或扫描时，数据未被更改以违反该假设。直接使用 Polygon 45 集数据类型可能比在上述函数中使用多边形列表和向量更有效，因为其可以强制执行的不变式提供了保持数据排序形式的机会，而不是一直走到多边形，然后为后续操作重新排序这些顶点。

Polygon 45 集数据的声明如下

模板 <typename T>
class polygon_45_set_data;

该类以坐标数据类型为参数。受益于类强制执行的不变式的知识的算法实现为成员函数，以向它们提供有关这些不变式的信息。

成员函数

polygon_45_set_data() 默认构造函数。
模板 <typename iT>
polygon_45_set_data(iT input_begin, iT input_end)		 从可插入对象的迭代器范围构造。
polygon_45_set_data(const polygon_45_set_data& that) 复制构造。
模板 <typename l, typename r, typename op>
polygon_45_set_data(const polygon_45_set_view<l,r,op>& t)		 从布尔运算符模板复制构造。
polygon_45_set_data&
operator=(const polygon_45_set_data& that)		 从另一个 polygon 集赋值，可能会更改扫描方向。
模板 <typename l, typename r, typename op>
polygon_45_set_data&
operator=(const polygon_45_set_view<l, r, op>& that)		 从布尔运算符模板赋值。
模板 <typename geometry_object>
polygon_45_set_data& operator=(const geometry_object& geo)		 从可插入对象赋值。
模板 <typename iT>
void insert(iT input_begin, iT input_end,
            bool is_hole = false)		 插入迭代器范围的对象。如果 is_hole 为 true，则插入减法区域。线性与添加的顶点数成正比。
void insert(const polygon_45_set_data& polygon_set,
            bool is_hole = false)		 插入一个 polygon 集。线性与添加的顶点数成正比。
模板 <typename geometry_type>
void insert(const geometry_type& geometry_object,
            bool is_hole = false)		 插入一个几何对象，如果 is_hole 为 true，则插入的区域是减法区域而不是加法区域。线性与添加的顶点数成正比。
模板 <typename output_container>
void get(output_container& output) const		 需要一个标准的几何对象容器。将扫描并消除重叠。将 polygon 集几何图形转换为该类型的对象，并将它们附加到容器中。多边形将以逆时针方向输出，孔多边形将以顺时针方向输出。输出多边形的最后一个顶点不是第一个顶点的副本，点数等于边数。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数。
模板 <typename output_container>
void get_polygons(output_container& output) const		 需要一个标准的多边形对象容器。将扫描并消除重叠。将 polygon 集几何图形转换为多边形，并将它们附加到容器中。多边形的孔洞将沿正 y 方向断裂到外边界。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数。
模板 <typename output_container>
void get_polygons_with_holes(output_container& o) const		 需要一个包含孔的多边形对象的标准容器。将扫描并消除重叠。将 polygon 集几何图形转换为多边形，并将它们附加到容器中。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数。
模板 <typename output_container>
void get_trapezoids(output_container& output) const		 需要一个标准的多边形对象容器。将扫描并消除重叠。将 polygon 集几何图形垂直切片成梯形，并将它们附加到容器中。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数。
模板 <typename output_container>
void get_trapezoids(output_container& output,
  orientation_2d slicing_orientation) const 		需要一个标准的多边形对象容器。将扫描并消除重叠。沿给定方向将 polygon 集几何图形切片成梯形，并将它们附加到容器中。时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数。
bool operator==(const polygon_45_set_data& p) const 扫描后，polygon 集中几何图形的数据表示形式将采用数学规范形式。因此，两个集合之间的比较在它们处于扫描状态后是一个线性时间操作。将扫描并消除两个 polygon 集中的重叠。第一次的时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数；之后的时间复杂度为线性，空间复杂度为常数。
bool operator!=(const polygon_45_set_data& p) const 等价运算符的逆逻辑。
void clear() 使 polygon 集为空。注意：不会释放内存。使用 shrink 以适应习惯用法，并分配默认构造的 polygon 集以释放内存。
bool empty() const 检查 polygon 集是否不包含几何图形。将扫描并消除重叠，因为减法区域可能会使 polygon 集为空。第一次的时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数；之后的时间复杂度为线性，空间复杂度为常数。
bool is_manhattan() const 以常数时间返回有关几何图形是否仅包含曼哈顿（轴平行直角）边线的信息。常数时间。
void clean() const 扫描并消除重叠。第一次的时间复杂度为 O(n log n)，空间复杂度为 O(n)，其中 n 为顶点数加上交点数；之后的时间复杂度为线性，空间复杂度为常数。
模板 <typename input_iterator_type>
void set(input_iterator_type input_begin,
         input_iterator_type input_end) 		用迭代器范围中的可插入对象覆盖 polygon 集中的几何图形。
模板 <typename rectangle_type>
bool extents(rectangle_type& extents_rectangle) const		 给定一个表示矩形的对象，扫描并消除多边形集合中的重叠部分（因为减法区域可能会改变其范围），然后计算边界框并将其赋给extents_rectangle。第一次运行时间为O(n log n)，内存为O(n)（相对于顶点数），后续运行时间为线性时间，内存为常数。
polygon_45_set_data&
resize(coord_type resizing,
       RoundingOption rounding = CLOSEST,
       CornerOption corner = INTERSECTION)		 如果resizing为正，则与bloat相同；如果resizing为负，则与shrink相同。RoundingOption是一个枚举，控制对45度边缩放结果的非整数部分进行捕捉。CornerOption是一个枚举，控制如何执行角填充。polygon_45_set_data.hpp定义了这些枚举。运行时间为O(n log n)，内存为O(n)（相对于顶点数和交点数）。
template <typename transformation_type>
polygon_45_set_data&
transform(const transformation_type& transformation) 		将transformation.transform()应用于多边形集合中存储的顶点。运行时间为O(n log n)，内存为O(n)（相对于顶点数和交点数）。
polygon_45_set_data& scale_up(unsigned_area_type factor) 将多边形集合中存储的顶点按factor向上缩放。线性时间复杂度（相对于顶点数）。
polygon_45_set_data& scale_down(unsigned_area_type factor)  将多边形集合中存储的顶点按factor向下缩放。线性时间复杂度（相对于顶点数）。
polygon_45_set_data& scale(double factor) 将多边形集合中存储的顶点按浮点型factor缩放。线性时间复杂度（相对于顶点数）。
polygon_45_set_data& self_xor() 仅保留多边形集合中几何图形的非重叠区域。运行时间为O(n log n)，内存为O(n)（相对于顶点数和交点数）。
polygon_45_set_data& self_intersect() 仅保留多边形集合中几何图形的重叠区域。运行时间为O(n log n)，内存为O(n)（相对于顶点数和交点数）。
bool has_error_data() const 如果非整数交点导致布尔运算输出中出现小的伪影，则返回true。常数时间。
std::size_t error_count() const 返回由于非整数交点可能存在于输出中的伪影数量。常数时间。
void get_error_data(polygon_45_set_data& p) const 使用1x1单位正方形填充输入多边形集合，以限制由于非整数交点可能存在于输出中的误差。线性时间复杂度（相对于误差数据的顶点数）。
polygon_45_set_data& self_intersect() 仅保留多边形集合中几何图形的重叠区域。运行时间为O(n log n)，内存为O(n)（相对于顶点数和交点数）。
 
版权 版权所有 © 英特尔公司 2008-2010。
许可证 根据Boost软件许可证版本1.0分发。（参见随附文件 LICENSE_1_0.txt或复制自 https://boost.ac.cn/LICENSE_1_0.txt)