第1章：Clipper2 概述与入门

1.1 引言

在计算机图形学、地理信息系统（GIS）、计算机辅助设计（CAD）以及游戏开发等领域，多边形的几何运算是一个基础且至关重要的功能。无论是地图数据的处理、建筑设计中的布尔运算、游戏中的碰撞检测，还是工业制造中的刀具路径规划，都需要对多边形进行精确的裁剪、合并、求交、偏移等操作。

Clipper2 是由澳大利亚程序员 Angus Johnson 开发的 Clipper1 库的全面升级版本。它不仅继承了 Clipper1 的所有功能，还在算法效率、代码结构、API 设计等方面进行了大量改进。本教程将深入解读其 C# 源代码实现，帮助读者理解核心算法原理和代码设计。

1.2 Clipper2 vs Clipper1

1.2.1 主要改进

特性	Clipper1	Clipper2
坐标类型	仅整数（Int64/Int32）	整数 + 浮点双精度
命名空间	ClipperLib	Clipper2Lib / Clipper2ZLib
类型别名	Path = List	Path64 类、PathD 类
Z坐标支持	条件编译	条件编译（USINGZ）
矩形裁剪	无专门优化	RectClip64 高速算法
三角剖分	无	内置 Delaunay 三角剖分
对象池	无	内置对象池减少 GC
API 风格	较繁琐	更简洁的静态方法

1.2.2 代码结构对比

Clipper1：所有代码在单个 clipper.cs 文件中，约 4800 行。

Clipper2：模块化设计，分为多个源文件：

CSharp/Clipper2Lib/
├── Clipper.cs           # 静态工具方法
├── Clipper.Core.cs      # 核心数据结构
├── Clipper.Engine.cs    # 裁剪引擎核心
├── Clipper.Offset.cs    # 路径偏移功能
├── Clipper.RectClip.cs  # 矩形裁剪优化
├── Clipper.Minkowski.cs # Minkowski 和/差
└── Clipper.Extras.cs    # 扩展功能（三角剖分等）

1.3 源代码头部声明

每个源文件都以标准的版权声明开始：

/*******************************************************************************
* Author    :  Angus Johnson                                                   *
* Date      :  21 February 2026                                                *
* Website   :  https://www.angusj.com                                          *
* Copyright :  Angus Johnson 2010-2026                                         *
* Purpose   :  This is the main polygon clipping module                        *
* Thanks    :  Special thanks to Thong Nguyen, Guus Kuiper, Phil Stopford,     *
*           :  and Daniel Gosnell for their invaluable assistance with C#.     *
* License   :  https://www.boost.org/LICENSE_1_0.txt                           *
*******************************************************************************/

从声明中可以看出：

1. 开源许可：采用 Boost Software License，允许商业和非商业使用
2. 持续维护：项目从 2010 年开始，持续更新至今
3. 社区贡献：感谢多位开发者对 C# 版本的贡献

1.4 预处理器指令

Clipper2 使用预处理器指令控制编译选项：

#nullable enable
using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;

#if USINGZ
namespace Clipper2ZLib
#else
namespace Clipper2Lib
#endif

1.4.1 nullable enable

#nullable enable

这是 C# 8.0 引入的可空引用类型特性。启用后：

• 引用类型默认不可为 null
• 可空引用类型需显式声明为 Type?
• 编译器会在可能的空引用处发出警告

这有助于在编译期发现潜在的空引用异常，提高代码质量。

1.4.2 USINGZ 条件编译

#if USINGZ
namespace Clipper2ZLib
#else
namespace Clipper2Lib
#endif

• 默认（未定义 USINGZ）：使用 Clipper2Lib 命名空间，坐标只有 X、Y
• 定义 USINGZ：使用 Clipper2ZLib 命名空间，坐标增加 Z 分量

启用 Z 坐标后，点结构变为：

public struct Point64
{
    public long X;
    public long Y;
#if USINGZ
    public long Z;
#endif
}

1.4.3 性能优化特性

源代码大量使用 MethodImplOptions.AggressiveInlining：

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static bool IsPositive(Path64 poly)
{
    return Area(poly) >= 0;
}

这告诉 JIT 编译器尽可能将方法内联，减少方法调用开销，对于频繁调用的小方法特别有效。

1.5 核心类型概览

1.5.1 公共类型（用户直接使用）

类型	说明
Point64	64位整数坐标点结构
PointD	双精度浮点坐标点结构
Path64	整数路径类（继承 List<Point64>）
PathD	浮点路径类（继承 List<PointD>）
Paths64	整数路径集合类（继承 List<Path64>）
PathsD	浮点路径集合类（继承 List<PathD>）
Rect64	64位整数矩形结构
RectD	双精度浮点矩形结构
Clipper64	整数坐标裁剪类
ClipperD	浮点坐标裁剪类
ClipperOffset	路径偏移类
PolyTree64	整数多边形树
PolyTreeD	浮点多边形树

1.5.2 枚举类型

枚举	说明
ClipType	裁剪操作类型（交、并、差、异或）
PathType	路径类型（主体、裁剪）
FillRule	填充规则（奇偶、非零、正向、负向）
JoinType	连接类型（斜接、方形、斜角、圆形）
EndType	端点类型（多边形、连接、平头、方形、圆形）

1.5.3 内部类型

类型	说明
InternalClipper	内部工具方法类
Vertex	顶点数据结构
LocalMinima	局部极小值结构
Active	活动边数据结构
OutRec	输出多边形记录
OutPt	输出点结构
ClipperBase	裁剪器基类

1.6 Vatti 算法简介

Clipper2 仍然基于 Bala Vatti 在 1992 年发表的多边形裁剪算法。该算法的核心思想是使用扫描线方法处理多边形：

1.6.1 扫描线方法

1. 预处理阶段：将多边形的边按 Y 坐标排序，识别所有局部极小值点
2. 扫描阶段：维护一个活动边表（Active Edge List, AEL），记录当前扫描线穿过的边
3. 事件处理：在每个关键 Y 坐标处理边的插入、删除和交点

1.6.2 关键概念

局部极小值（Local Minima）：

• 多边形轮廓中 Y 坐标最低的点（在 Y 轴向下的坐标系中）
• 算法从这些点开始向上扫描

活动边表（AEL）：

• 存储当前扫描线穿过的所有边
• 按 X 坐标排序
• 在 Clipper2 中由 Active 结构表示

顶点标志（VertexFlags）：

[Flags]
internal enum VertexFlags
{
    None = 0,
    OpenStart = 1,   // 开放路径起点
    OpenEnd = 2,     // 开放路径终点
    LocalMax = 4,    // 局部最大值
    LocalMin = 8     // 局部最小值
}

1.6.3 算法流程示意

扫描方向 ↑
          
Y=5  ━━━━━━━━━━━ 扫描线 5 (局部最大值)
     ╱╲        ╱╲
Y=4 ╱  ╲━━━━━━╱  ╲ 扫描线 4
   ╱    ╲    ╱    ╲
Y=3╱      ╲╱       ╲ 扫描线 3 (交点处理)
   ╲      ╱╲      ╱
Y=2 ╲    ╱  ╲    ╱ 扫描线 2
     ╲  ╱    ╲  ╱
Y=1   ╲╱      ╲╱   扫描线 1 (局部极小值)

1.7 整数坐标的设计哲学

Clipper2 的核心裁剪引擎仍然使用整数坐标，这是一个关键的设计决策：

1.7.1 浮点数的问题

// 浮点数精度问题示例
double a = 0.1 + 0.2;  // 结果可能是 0.30000000000000004
bool equal = (0.1 + 0.2 == 0.3);  // 可能为 false

1.7.2 整数坐标的优势

1. 精确比较：整数比较是精确的，不存在舍入误差
2. 确定性结果：相同输入在任何平台上产生相同输出
3. 数值稳定性：避免了浮点数累积误差

1.7.3 浮点支持的实现

Clipper2 通过 ClipperD 类提供浮点支持，其原理是：

public class ClipperD : ClipperBase
{
    private readonly double _scale;
    private readonly double _invScale;

    public ClipperD(int roundingDecimalPrecision = 2)
    {
        // 将精度转换为缩放因子
        _scale = Math.Pow(10, roundingDecimalPrecision);
        _invScale = 1 / _scale;
    }
}

浮点坐标在内部被缩放为整数处理，结果再缩放回浮点数。

1.8 坐标范围与精度

1.8.1 坐标范围常量

internal const long MaxInt64 = 9223372036854775807;
internal const long MaxCoord = MaxInt64 / 4;
internal const double max_coord = MaxCoord;
internal const double min_coord = -MaxCoord;

MaxCoord 约为 2.3×10¹⁸，这个限制是为了防止中间计算溢出。

1.8.2 精度检查

internal static void CheckPrecision(int precision)
{
    if (precision < -8 || precision > 8)
        throw new Exception("Error: Precision is out of range.");
}

浮点精度范围为 -8 到 8，表示小数点后的位数（或前的位数）。

1.9 快速使用示例

1.9.1 使用静态方法（推荐）

Clipper2 提供了便捷的静态方法：

using Clipper2Lib;

class Example
{
    static void Main()
    {
        // 创建主体多边形（正方形）
        Path64 subject = Clipper.MakePath(new long[] {
            0, 0, 100, 0, 100, 100, 0, 100
        });

        // 创建裁剪多边形
        Path64 clip = Clipper.MakePath(new long[] {
            50, 50, 150, 50, 150, 150, 50, 150
        });

        // 执行交集运算
        Paths64 solution = Clipper.Intersect(
            new Paths64 { subject },
            new Paths64 { clip },
            FillRule.NonZero
        );

        // 输出结果
        Console.WriteLine($"结果多边形数量: {solution.Count}");
        foreach (var path in solution)
        {
            Console.WriteLine($"多边形: {path}");
        }
    }
}

1.9.2 使用 Clipper64 类

using Clipper2Lib;

class Example
{
    static void Main()
    {
        Path64 subject = new Path64 {
            new Point64(0, 0),
            new Point64(100, 0),
            new Point64(100, 100),
            new Point64(0, 100)
        };

        Path64 clip = new Path64 {
            new Point64(50, 50),
            new Point64(150, 50),
            new Point64(150, 150),
            new Point64(50, 150)
        };

        Clipper64 clipper = new Clipper64();
        clipper.AddSubject(subject);
        clipper.AddClip(clip);

        Paths64 solution = new Paths64();
        clipper.Execute(ClipType.Intersection, FillRule.NonZero, solution);

        Console.WriteLine($"结果多边形数量: {solution.Count}");
    }
}

1.9.3 使用浮点坐标

using Clipper2Lib;

class Example
{
    static void Main()
    {
        PathD subject = Clipper.MakePath(new double[] {
            0.0, 0.0, 100.5, 0.0, 100.5, 100.5, 0.0, 100.5
        });

        PathD clip = Clipper.MakePath(new double[] {
            50.25, 50.25, 150.75, 50.25, 150.75, 150.75, 50.25, 150.75
        });

        // 使用 precision = 2 表示保留2位小数
        PathsD solution = Clipper.Intersect(
            new PathsD { subject },
            new PathsD { clip },
            FillRule.NonZero,
            precision: 2
        );

        Console.WriteLine($"结果: {solution}");
    }
}

1.10 四种布尔运算

Clipper2 支持四种布尔运算：

1.10.1 交集（Intersection）

返回两个多边形的公共区域：

Paths64 result = Clipper.Intersect(subject, clip, FillRule.NonZero);

1.10.2 并集（Union）

返回两个多边形的合并区域：

Paths64 result = Clipper.Union(subject, clip, FillRule.NonZero);
// 或单个多边形组的自并
Paths64 result = Clipper.Union(subject, FillRule.NonZero);

1.10.3 差集（Difference）

返回主体多边形减去裁剪多边形的区域：

Paths64 result = Clipper.Difference(subject, clip, FillRule.NonZero);

1.10.4 异或（Xor）

返回两个多边形的非公共区域：

Paths64 result = Clipper.Xor(subject, clip, FillRule.NonZero);

1.11 项目配置

1.11.1 NuGet 包

<PackageReference Include="Clipper2" Version="1.4.0" />

1.11.2 启用 Z 坐标

在项目文件中添加：

<PropertyGroup>
    <DefineConstants>USINGZ</DefineConstants>
</PropertyGroup>

1.11.3 .NET 版本要求

Clipper2 需要 .NET Standard 2.0 或更高版本，支持：

• .NET Framework 4.6.1+
• .NET Core 2.0+
• .NET 5/6/7/8+

1.12 本章小结

本章介绍了 Clipper2 C# 源代码的整体结构和设计理念：

1. 模块化设计：多个源文件分工明确
2. 双精度支持：整数核心 + 浮点封装
3. 现代 C# 特性：可空引用、内联优化
4. 算法基础：仍基于经典的 Vatti 扫描线算法
5. 简洁 API：静态方法 + 类实例两种风格

在后续章节中，我们将深入分析每个核心数据结构和算法实现的细节。

---

返回目录 | 下一章：核心数据结构