第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                           *
*******************************************************************************/

从声明中可以看出：

开源许可：采用 Boost Software License，允许商业和非商业使用
持续维护：项目从 2010 年开始，持续更新至今
社区贡献：感谢多位开发者对 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 扫描线方法

预处理阶段：将多边形的边按 Y 坐标排序，识别所有局部极小值点
扫描阶段：维护一个活动边表（Active Edge List, AEL），记录当前扫描线穿过的边
事件处理：在每个关键 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.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# 源代码的整体结构和设计理念：

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

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

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