GPC（General Polygon Clipper）多边形布尔运算库

概述

• 它最初由 Alan Murta 在曼彻斯特大学开发。
• 官方主页：Alan Murta’s GPC page

Key operations supported:

Difference (A-B) Intersection (A∩B) Exclusive-or (A⊕B) Union (A∪B)

算法特点

扫描线算法（Sweep Line）：

1. 预处理阶段 Inital Validation：
   • 检查简单的空结果情况
   • 使用边界框测试优化（minimax_test）识别潜在的轮廓
2. 构建局部最小值表（LMT）：
   • 为主体（subject）和裁剪（clip）多边形构建LMT
   • 对于差集操作，反转裁剪多边形的奇偶性
3. 扫描线处理：
   • 从下到上处理每个扫描线
   • 在活动边表（AET）中添加和删除边
   • 处理边的交点
   • 根据操作类型确定边的贡献状态
4. 结果生成： 从处理过程中生成的多边形节点创建结果多边形

扫描线算法的典型时间复杂度是：

[ O((n + k) \log n) ]

其中：

• ( n )：原始输入的边数（多边形顶点数级别）
• ( k )：最终产生的交点数量

数据结构 Data Structure

Structure	Description	Fields
gpc_vertex	表示多边形顶点的x和y坐标	x, y coordinates as doubles
gpc_vertex_list	顶点列表，包含顶点数量和顶点数组指针	num_vertices, vertex array pointer
gpc_polygon	多边形集合，包含轮廓数量、孔洞标志和轮廓数组指针	num_contours, hole flags, contour array pointer
gpc_tristrip	三角形带集合，用于输出结果	num_strips, strip array pointer