在计算机图形学、地理信息系统（GIS）、计算机辅助设计（CAD）以及游戏开发等领域，多边形的几何运算是一个基础且至关重要的功能。无论是地图数据的处理、建筑设计中的布尔运算、游戏中的碰撞检测，还是工业制造中的刀具路径规划，都需要对多边形进行精确的裁剪、合并、求交、偏移等操作。
Clipper1（也称为 ClipperLib）是由澳大利亚程序员 Angus Johnson 开发的一个成熟、稳定的开源多边形裁剪库。本教程将深入解读其 C# 源代码实现，帮助读者理解核心算法原理和代码设计。
Clipper1 的 C# 实现位于单个源文件 clipper.cs 中，整个库约 4800 行代码。文件结构如下：
C#/clipper_library/
├── clipper.cs # 核心源代码文件
├── clipper_library.csproj # 项目文件
└── Properties/
└── AssemblyInfo.cs # 程序集信息
源代码以版权声明和算法来源说明开始：
/*******************************************************************************
* *
* Author : Angus Johnson *
* Version : 6.4.2 *
* Date : 27 February 2017 *
* Website : http://www.angusj.com *
* Copyright : Angus Johnson 2010-2017 *
* *
* License: *
* Use, modification & distribution is subject to Boost Software License Ver 1.*
* http://www.boost.org/LICENSE_1_0.txt *
* *
* Attributions: *
* The code in this library is an extension of Bala Vatti's clipping algorithm:*
* "A generic solution to polygon clipping" *
* Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. *
* http://portal.acm.org/citation.cfm?id=129906 *
* *
*******************************************************************************/
从声明中可以看出：
源代码开头定义了几个重要的预处理器指令：
//use_int32: When enabled 32bit ints are used instead of 64bit ints. This
//improve performance but coordinate values are limited to the range +/- 46340
//#define use_int32
//use_xyz: adds a Z member to IntPoint. Adds a minor cost to performance.
//#define use_xyz
//use_lines: Enables open path clipping. Adds a very minor cost to performance.
#define use_lines
#if use_int32
using cInt = Int32;
#else
using cInt = Int64;
#endif
Int64）Int32），提高性能但限制坐标范围为 ±46340using 别名定义 cInt 类型坐标范围计算：32 位有符号整数最大值约为 2.1×10⁹，但由于中间计算可能产生溢出，实际安全范围被限制在 √(2³¹-1) ≈ 46340。
#if use_xyz
public cInt Z;
public IntPoint(cInt x, cInt y, cInt z = 0)
{
this.X = x; this.Y = y; this.Z = z;
}
#endif
#define use_lines
using System;
using System.Collections.Generic;
namespace ClipperLib
{
using Path = List<IntPoint>;
using Paths = List<List<IntPoint>>;
// ... 类定义 ...
}
所有 Clipper 相关的类型都定义在 ClipperLib 命名空间中，避免与其他库的命名冲突。
源代码使用 using 指令创建了两个重要的类型别名：
List<IntPoint>，表示一条路径（多边形轮廓或开放线段）List<List<IntPoint>>，表示多条路径的集合这种设计使得代码更加简洁易读：
// 使用别名前
List<IntPoint> polygon = new List<IntPoint>();
List<List<IntPoint>> polygons = new List<List<IntPoint>>();
// 使用别名后
Path polygon = new Path();
Paths polygons = new Paths();
Clipper1 的 C# 实现包含以下核心类和结构：
| 类型 | 说明 |
|---|---|
IntPoint |
整数坐标点结构 |
DoublePoint |
双精度浮点坐标点结构 |
IntRect |
整数矩形边界结构 |
PolyNode |
多边形树节点类 |
PolyTree |
多边形树类，继承自 PolyNode |
Clipper |
多边形裁剪操作类 |
ClipperOffset |
多边形偏移操作类 |
| 枚举 | 说明 |
|---|---|
ClipType |
裁剪操作类型（交、并、差、异或） |
PolyType |
多边形类型（主体、裁剪） |
PolyFillType |
填充规则（奇偶、非零、正向、负向） |
JoinType |
连接类型（方形、圆形、斜接） |
EndType |
端点类型（闭合多边形、闭合线、开放端点等） |
| 类型 | 说明 |
|---|---|
Int128 |
128 位整数结构，用于高精度中间计算 |
TEdge |
边缘数据结构 |
LocalMinima |
局部极小值结构 |
Scanbeam |
扫描线结构 |
OutRec |
输出多边形记录 |
OutPt |
输出点结构 |
Join |
连接点结构 |
ClipperBase |
Clipper 的基类 |
Clipper1 基于 Bala Vatti 在 1992 年发表的多边形裁剪算法。该算法的核心思想是：
算法使用自下而上的扫描线方法处理多边形：
局部极小值（Local Minima）：
活动边表（AEL）：
扫描线（Scanbeam）：
扫描方向 ↑
Y=5 ━━━━━━━━━━━ 扫描线 5
╱╲ ╱╲
Y=4 ╱ ╲━━━━━━╱ ╲ 扫描线 4
╱ ╲ ╱ ╲
Y=3╱ ╲╱ ╲ 扫描线 3 (交点处理)
╲ ╱╲ ╱
Y=2 ╲ ╱ ╲ ╱ 扫描线 2
╲ ╱ ╲ ╱
Y=1 ╲╱ ╲╱ 扫描线 1 (局部极小值)
Clipper1 使用整数坐标而非浮点数，这是一个关键的设计决策：
// 浮点数精度问题示例
double a = 0.1 + 0.2; // 结果可能是 0.30000000000000004
bool equal = (0.1 + 0.2 == 0.3); // 可能为 false
使用 Clipper 时，通常需要将浮点坐标转换为整数：
// 坐标转换示例
const double scale = 1000.0; // 比例因子
// 输入转换：浮点 -> 整数
IntPoint ToIntPoint(double x, double y)
{
return new IntPoint((cInt)(x * scale), (cInt)(y * scale));
}
// 输出转换：整数 -> 浮点
DoublePoint ToDoublePoint(IntPoint pt)
{
return new DoublePoint(pt.X / scale, pt.Y / scale);
}
源代码定义了坐标范围常量：
#if use_int32
public const cInt loRange = 0x7FFF;
public const cInt hiRange = 0x7FFF;
#else
public const cInt loRange = 0x3FFFFFFF;
public const cInt hiRange = 0x3FFFFFFFFFFFFFFFL;
#endif
| 模式 | loRange | hiRange | 说明 |
|---|---|---|---|
| 32位 | 32,767 | 32,767 | 约 ±3.2×10⁴ |
| 64位 | 1,073,741,823 | 4,611,686,018,427,387,903 | 约 ±10⁹ |
void RangeTest(IntPoint Pt, ref bool useFullRange)
{
if (useFullRange)
{
if (Pt.X > hiRange || Pt.Y > hiRange || -Pt.X > hiRange || -Pt.Y > hiRange)
throw new ClipperException("Coordinate outside allowed range");
}
else if (Pt.X > loRange || Pt.Y > loRange || -Pt.X > loRange || -Pt.Y > loRange)
{
useFullRange = true;
RangeTest(Pt, ref useFullRange);
}
}
自动范围扩展：当坐标超出 loRange 但未超出 hiRange 时，自动切换到完整范围模式，启用 128 位中间计算。
Clipper 定义了自己的异常类型：
public class ClipperException : Exception
{
public ClipperException(string description) : base(description) { }
}
常见的异常情况：
"Coordinate outside allowed range""AddPath: Open paths must be subject.""ProcessIntersections error"以下是一个简单的多边形裁剪示例：
using ClipperLib;
class Example
{
static void Main()
{
// 创建主体多边形（正方形）
Path subject = new Path();
subject.Add(new IntPoint(0, 0));
subject.Add(new IntPoint(100, 0));
subject.Add(new IntPoint(100, 100));
subject.Add(new IntPoint(0, 100));
// 创建裁剪多边形（另一个正方形，部分重叠）
Path clip = new Path();
clip.Add(new IntPoint(50, 50));
clip.Add(new IntPoint(150, 50));
clip.Add(new IntPoint(150, 150));
clip.Add(new IntPoint(50, 150));
// 创建 Clipper 实例并添加多边形
Clipper clipper = new Clipper();
clipper.AddPath(subject, PolyType.ptSubject, true);
clipper.AddPath(clip, PolyType.ptClip, true);
// 执行交集运算
Paths solution = new Paths();
clipper.Execute(ClipType.ctIntersection, solution);
// 输出结果
Console.WriteLine($"结果多边形数量: {solution.Count}");
foreach (var path in solution)
{
Console.WriteLine($"多边形顶点数: {path.Count}");
foreach (var pt in path)
{
Console.WriteLine($" ({pt.X}, {pt.Y})");
}
}
}
}
本章介绍了 Clipper1 C# 源代码的整体结构和设计理念：
clipper.cs，约 4800 行代码use_int32、use_xyz、use_lines 控制编译选项Clipper（裁剪）、ClipperOffset（偏移）、PolyTree（结果组织）在后续章节中，我们将深入分析每个核心数据结构和算法实现的细节。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。