相关章节: 循环迭代器
4.1 多边形表示
理论基础
多边形表示方法
在计算几何中，多边形是最基本的几何形状之一。CGAL提供了多种多边形表示方式以适应不同的应用需求。
简单多边形 (Simple Polygon)：
- 由一系列顶点按顺序连接形成的闭合链
- 边之间仅在顶点处相交
- 无自相交
带孔多边形 (Polygon with Holes)：
- 一个外边界（outer boundary）
- 零个或多个内边界（holes）
- 内边界完全包含在外边界内，且互不重叠
数学表示：
- 简单多边形：，其中 是顶点
- 边：
多边形方向与定向
顶点顺序：
- 逆时针（CCW）：外边界通常使用逆时针方向
- 顺时针（CW）：内边界（孔）通常使用顺时针方向
方向判定：使用有符号面积计算
- ：逆时针方向
- ：顺时针方向
多边形性质
简单性测试：
- 检查所有非相邻边是否相交
- 时间复杂度：（朴素算法）或 （扫描线算法）
凸性测试：
- 所有内角
- 所有顶点的转向一致
- 时间复杂度：
架构分析
类层次结构
Polygon_2<Kernel>
├── 顶点容器（std::vector<Point_2>）
├── 边迭代器
└── 面积/方向计算
Polygon_with_holes_2<Kernel>
├── outer_boundary_: Polygon_2
└── holes_: std::vector<Polygon_2>
头文件位置：CGAL/Polygon_2.h, CGAL/Polygon_with_holes_2.h
Polygon_2 实现
#include <CGAL/Polygon_2.h>
// Polygon_2 的简化定义
template <class Kernel_>
class Polygon_2 {
public:
typedef Kernel_ Kernel;
typedef typename Kernel::Point_2 Point_2;
typedef typename Kernel::Segment_2 Segment_2;
// 容器类型
typedef std::vector<Point_2> Container;
typedef typename Container::iterator iterator;
typedef typename Container::const_iterator const_iterator;
typedef typename Container::size_type size_type;
// 边迭代器
typedef Polygon_edge_iterator<Polygon_2> Edge_const_iterator;
private:
Container d_container; // 存储顶点的容器
public:
// 构造函数
Polygon_2() {}
template <class InputIterator>
Polygon_2(InputIterator first, InputIterator last)
: d_container(first, last) {}
// 顶点访问
const Point_2& vertex(size_type i) const {
return d_container[i];
}
Point_2& vertex(size_type i) {
return d_container[i];
}
const Point_2& operator[](size_type i) const {
return d_container[i];
}
// 容器接口
iterator begin() { return d_container.begin(); }
iterator end() { return d_container.end(); }
const_iterator begin() const { return d_container.begin(); }
const_iterator end() const { return d_container.end(); }
size_type size() const { return d_container.size(); }
bool is_empty() const { return d_container.empty(); }
// 修改操作
void push_back(const Point_2& p) { d_container.push_back(p); }
void pop_back() { d_container.pop_back(); }
void clear() { d_container.clear(); }
void reverse_orientation() { std::reverse(d_container.begin(), d_container.end()); }
// 边迭代
Edge_const_iterator edges_begin() const {
return Edge_const_iterator(d_container.begin(), d_container.end());
}
Edge_const_iterator edges_end() const {
return Edge_const_iterator(d_container.end(), d_container.end());
}
// 几何查询
Orientation orientation() const;
bool is_simple() const;
bool is_convex() const;
typename Kernel::FT area() const;
Bbox_2 bbox() const;
// 点包含测试
Bounded_side bounded_side(const Point_2& p) const;
bool has_on_boundary(const Point_2& p) const;
bool has_on_bounded_side(const Point_2& p) const;
bool has_on_unbounded_side(const Point_2& p) const;
};Polygon_with_holes_2 实现
#include <CGAL/Polygon_with_holes_2.h>
// Polygon_with_holes_2 的简化定义
template <class Kernel_>
class Polygon_with_holes_2 {
public:
typedef Kernel_ Kernel;
typedef Polygon_2<Kernel> Polygon_2;
typedef typename Polygon_2::Point_2 Point_2;
// 孔容器类型
typedef std::vector<Polygon_2> Hole_container;
typedef typename Hole_container::iterator Hole_iterator;
typedef typename Hole_container::const_iterator Hole_const_iterator;
private:
Polygon_2 outer_boundary_; // 外边界
Hole_container holes_; // 孔集合
public:
// 构造函数
Polygon_with_holes_2() {}
explicit Polygon_with_holes_2(const Polygon_2& outer)
: outer_boundary_(outer) {}
Polygon_with_holes_2(const Polygon_2& outer,
const Hole_container& holes)
: outer_boundary_(outer), holes_(holes) {}
// 外边界访问
const Polygon_2& outer_boundary() const { return outer_boundary_; }
Polygon_2& outer_boundary() { return outer_boundary_; }
void set_outer_boundary(const Polygon_2& outer) { outer_boundary_ = outer; }
// 孔操作
Hole_iterator holes_begin() { return holes_.begin(); }
Hole_iterator holes_end() { return holes_.end(); }
Hole_const_iterator holes_begin() const { return holes_.begin(); }
Hole_const_iterator holes_end() const { return holes_.end(); }
size_t number_of_holes() const { return holes_.size(); }
bool is_unbounded() const { return outer_boundary_.is_empty(); }
void add_hole(const Polygon_2& hole) { holes_.push_back(hole); }
void erase_hole(Hole_iterator it) { holes_.erase(it); }
void clear_holes() { holes_.clear(); }
// 几何查询
bool is_simple() const;
typename Kernel::FT area() const;
// 点包含测试
Bounded_side bounded_side(const Point_2& p) const;
};边迭代器实现
// Polygon_edge_iterator 的简化定义
template <class Polygon_>
class Polygon_edge_iterator {
public:
typedef typename Polygon_::Point_2 Point_2;
typedef typename Polygon_::Segment_2 Segment_2;
typedef typename Polygon_::Container Container;
typedef typename Container::const_iterator Vertex_iterator;
private:
Vertex_iterator first_; // 起始顶点
Vertex_iterator current_; // 当前顶点
Vertex_iterator last_; // 结束顶点
public:
Polygon_edge_iterator(Vertex_iterator first, Vertex_iterator last)
: first_(first), current_(first), last_(last) {}
// 解引用：返回当前边对应的线段
Segment_2 operator*() const {
Vertex_iterator next = current_;
++next;
if (next == last_) {
next = first_; // 闭合多边形
}
return Segment_2(*current_, *next);
}
// 迭代器操作
Polygon_edge_iterator& operator++() {
++current_;
return *this;
}
bool operator==(const Polygon_edge_iterator& other) const {
return current_ == other.current_;
}
bool operator!=(const Polygon_edge_iterator& other) const {
return !(*this == other);
}
};实现细节
方向与面积计算
// 多边形方向计算
template <class Kernel_>
Orientation Polygon_2<Kernel_>::orientation() const {
CGAL_precondition(size() >= 3);
// 找到最左下角的点
const_iterator leftmost = d_container.begin();
for (const_iterator it = d_container.begin(); it != d_container.end(); ++it) {
if (it->x() < leftmost->x() ||
(it->x() == leftmost->x() && it->y() < leftmost->y())) {
leftmost = it;
}
}
// 获取相邻顶点
const_iterator prev = (leftmost == d_container.begin())
? d_container.end() - 1
: leftmost - 1;
const_iterator next = (leftmost + 1 == d_container.end())
? d_container.begin()
: leftmost + 1;
return CGAL::orientation(*prev, *leftmost, *next);
}
// 多边形面积计算（有符号）
template <class Kernel_>
typename Kernel_::FT Polygon_2<Kernel_>::area() const {
typedef typename Kernel_::FT FT;
if (size() < 3) return FT(0);
FT area = FT(0);
const_iterator it = d_container.begin();
Point_2 first = *it++;
Point_2 prev = first;
for (; it != d_container.end(); ++it) {
// 叉积贡献：x1*y2 - x2*y1
area += prev.x() * it->y() - it->x() * prev.y();
prev = *it;
}
// 闭合边
area += prev.x() * first.y() - first.x() * prev.y();
return area / FT(2);
}简单性测试
// 简单性测试（朴素O(n^2)算法）
template <class Kernel_>
bool Polygon_2<Kernel_>::is_simple() const {
size_type n = size();
if (n < 4) return true; // 三角形及以下总是简单的
// 检查所有非相邻边对
for (size_type i = 0; i < n; ++i) {
Segment_2 s1(vertex(i), vertex((i + 1) % n));
for (size_type j = i + 2; j < n; ++j) {
// 跳过相邻边
if (j == (i + n - 1) % n) continue;
Segment_2 s2(vertex(j), vertex((j + 1) % n));
// 检查边相交
if (CGAL::do_intersect(s1, s2)) {
// 检查是否是共享顶点
auto inter = CGAL::intersection(s1, s2);
if (inter) {
if (const Point_2* p = boost::get<Point_2>(&*inter)) {
// 如果是端点，检查是否是共享顶点
if ((*p == s1.source() || *p == s1.target()) &&
(*p == s2.source() || *p == s2.target())) {
continue; // 共享顶点，允许
}
}
return false; // 非共享顶点的相交
}
}
}
}
return true;
}点包含测试
// 绕数算法（Winding Number）
template <class Kernel_>
Bounded_side Polygon_2<Kernel_>::bounded_side(const Point_2& p) const {
CGAL_precondition(size() >= 3);
int winding_number = 0;
for (Edge_const_iterator it = edges_begin(); it != edges_end(); ++it) {
Segment_2 seg = *it;
// 检查点是否在边上
if (seg.has_on(p)) {
return ON_BOUNDARY;
}
// 计算边的绕数贡献
const Point_2& a = seg.source();
const Point_2& b = seg.target();
// 射线向上（正y方向）
if (a.y() <= p.y()) {
if (b.y() > p.y()) { // 向上穿过
if (CGAL::orientation(a, b, p) == LEFT_TURN) {
++winding_number;
}
}
} else {
if (b.y() <= p.y()) { // 向下穿过
if (CGAL::orientation(a, b, p) == RIGHT_TURN) {
--winding_number;
}
}
}
}
return (winding_number == 0) ? ON_UNBOUNDED_SIDE : ON_BOUNDED_SIDE;
}凸性测试
// 凸性测试
template <class Kernel_>
bool Polygon_2<Kernel_>::is_convex() const {
size_type n = size();
if (n < 4) return true; // 三角形及以下总是凸的
// 获取多边形方向
Orientation poly_orient = orientation();
// 检查每个顶点的转向是否一致
for (size_type i = 0; i < n; ++i) {
const Point_2& prev = vertex((i + n - 1) % n);
const Point_2& curr = vertex(i);
const Point_2& next = vertex((i + 1) % n);
Orientation turn = CGAL::orientation(prev, curr, next);
if (turn != COLLINEAR && turn != poly_orient) {
return false; // 发现不一致的转向
}
}
return true;
}使用示例
示例1：基本多边形操作
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef CGAL::Polygon_2<K> Polygon_2;
int main() {
// 创建多边形
Polygon_2 polygon;
polygon.push_back(Point_2(0, 0));
polygon.push_back(Point_2(5, 0));
polygon.push_back(Point_2(5, 5));
polygon.push_back(Point_2(0, 5));
std::cout << "Polygon has " << polygon.size() << " vertices" << std::endl;
// 遍历顶点
std::cout << "Vertices:" << std::endl;
for (Polygon_2::Vertex_iterator vit = polygon.vertices_begin();
vit != polygon.vertices_end(); ++vit) {
std::cout << " (" << vit->x() << ", " << vit->y() << ")" << std::endl;
}
// 遍历边
std::cout << "Edges:" << std::endl;
for (Polygon_2::Edge_const_iterator eit = polygon.edges_begin();
eit != polygon.edges_end(); ++eit) {
std::cout << " " << eit->source() << " -> " << eit->target() << std::endl;
}
// 几何查询
std::cout << "\nProperties:" << std::endl;
std::cout << " Area: " << polygon.area() << std::endl;
std::cout << " Is simple: " << polygon.is_simple() << std::endl;
std::cout << " Is convex: " << polygon.is_convex() << std::endl;
std::cout << " Orientation: " << polygon.orientation() << std::endl;
// 点包含测试
Point_2 test_point(2, 2);
std::cout << "\nPoint (2,2) is inside: "
<< (polygon.bounded_side(test_point) == CGAL::ON_BOUNDED_SIDE)
<< std::endl;
return 0;
}示例2：带孔多边形
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef CGAL::Polygon_with_holes_2<K> Polygon_with_holes_2;
int main() {
// 创建外边界（逆时针）
Polygon_2 outer;
outer.push_back(Point_2(0, 0));
outer.push_back(Point_2(10, 0));
outer.push_back(Point_2(10, 10));
outer.push_back(Point_2(0, 10));
// 创建孔（顺时针）
Polygon_2 hole1;
hole1.push_back(Point_2(2, 2));
hole1.push_back(Point_2(2, 4));
hole1.push_back(Point_2(4, 4));
hole1.push_back(Point_2(4, 2));
Polygon_2 hole2;
hole2.push_back(Point_2(6, 6));
hole2.push_back(Point_2(8, 6));
hole2.push_back(Point_2(8, 8));
hole2.push_back(Point_2(6, 8));
// 创建带孔多边形
Polygon_with_holes_2 pwh(outer);
pwh.add_hole(hole1);
pwh.add_hole(hole2);
std::cout << "Polygon with holes:" << std::endl;
std::cout << " Outer boundary vertices: " << pwh.outer_boundary().size() << std::endl;
std::cout << " Number of holes: " << pwh.number_of_holes() << std::endl;
std::cout << " Total area: " << pwh.area() << std::endl;
// 点包含测试
Point_2 p1(5, 5); // 在内部，不在孔中
Point_2 p2(3, 3); // 在孔1中
Point_2 p3(15, 5); // 在外部
std::cout << "\nPoint containment tests:" << std::endl;
std::cout << " (5,5) is inside: "
<< (pwh.bounded_side(p1) == CGAL::ON_BOUNDED_SIDE) << std::endl;
std::cout << " (3,3) is inside: "
<< (pwh.bounded_side(p2) == CGAL::ON_BOUNDED_SIDE) << std::endl;
std::cout << " (15,5) is inside: "
<< (pwh.bounded_side(p3) == CGAL::ON_BOUNDED_SIDE) << std::endl;
return 0;
}示例3：多边形修改与布尔运算准备
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <algorithm>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef CGAL::Polygon_2<K> Polygon_2;
// 创建凸包多边形
Polygon_2 create_convex_hull(const std::vector<Point_2>& points) {
std::vector<Point_2> hull_points = points;
// 按角度排序（简化版本，实际应使用凸包算法）
Point_2 centroid(0, 0);
for (const auto& p : points) {
centroid = Point_2(centroid.x() + p.x(), centroid.y() + p.y());
}
centroid = Point_2(centroid.x() / points.size(), centroid.y() / points.size());
std::sort(hull_points.begin(), hull_points.end(),
[¢roid](const Point_2& a, const Point_2& b) {
double angle_a = atan2(a.y() - centroid.y(), a.x() - centroid.x());
double angle_b = atan2(b.y() - centroid.y(), b.x() - centroid.x());
return angle_a < angle_b;
});
return Polygon_2(hull_points.begin(), hull_points.end());
}
int main() {
// 创建多边形
Polygon_2 polygon;
polygon.push_back(Point_2(0, 0));
polygon.push_back(Point_2(4, 0));
polygon.push_back(Point_2(4, 4));
polygon.push_back(Point_2(2, 2)); // 凹点
polygon.push_back(Point_2(0, 4));
std::cout << "Original polygon:" << std::endl;
std::cout << " Is convex: " << polygon.is_convex() << std::endl;
std::cout << " Area: " << polygon.area() << std::endl;
// 反转方向
polygon.reverse_orientation();
std::cout << "\nAfter reversing orientation: " << polygon.orientation() << std::endl;
// 清除并重建
polygon.clear();
polygon.push_back(Point_2(0, 0));
polygon.push_back(Point_2(5, 0));
polygon.push_back(Point_2(5, 5));
polygon.push_back(Point_2(0, 5));
std::cout << "\nNew convex polygon:" << std::endl;
std::cout << " Is convex: " << polygon.is_convex() << std::endl;
std::cout << " Area: " << polygon.area() << std::endl;
return 0;
}复杂度分析
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| push_back | O(1) 均摊 | 动态数组 |
| vertex访问 | O(1) | 随机访问 |
| 边迭代 | O(1) 每边 | 遍历所有边 |
| area() | O(n) | 遍历所有顶点 |
| orientation() | O(n) | 找最左点 + 方向测试 |
| is_simple() | O(n²) | 朴素算法 |
| is_convex() | O(n) | 遍历所有顶点 |
| bounded_side() | O(n) | 绕数算法 |
空间复杂度
| 表示 | 空间复杂度 | 说明 |
|---|---|---|
| Polygon_2 | O(n) | n个顶点 |
| Polygon_with_holes_2 | O(n + h×m) | n个外边界顶点，h个孔，每个孔m个顶点 |
| 边迭代器 | O(1) | 仅存储迭代器 |
性能优化建议
- 批量构造：使用迭代器范围构造，避免多次push_back
- 预分配：如果已知顶点数，先reserve再添加
- 简单性测试：对于大量多边形，考虑使用空间索引加速
- 点包含测试：对于大量查询，考虑使用三角剖分预处理
关键文件位置
| 文件路径 | 说明 |
|---|---|
CGAL/Polygon_2.h | Polygon_2 主头文件 |
CGAL/Polygon_with_holes_2.h | Polygon_with_holes_2 主头文件 |
CGAL/Polygon_2/Polygon_2_vertex_circulator.h | 顶点循环迭代器 |
CGAL/Polygon_2/Polygon_2_edge_iterator.h | 边迭代器 |
CGAL/Polygon_2/Polygon_2_algorithms.h | 多边形算法 |
CGAL/Polygon_2/Polygon_2_simplicity.h | 简单性测试 |
CGAL/Polygon_2/Polygon_2_traits.h | 多边形特征 |