第1章：Clipper1 概述与入门

1.1 引言

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

Clipper1（也称为 ClipperLib）是由澳大利亚程序员 Angus Johnson 开发的一个成熟、稳定的开源多边形裁剪库。本教程将深入解读其 C# 源代码实现，帮助读者理解核心算法原理和代码设计。

1.2 源代码文件结构

Clipper1 的 C# 实现位于单个源文件 clipper.cs 中，整个库约 4800 行代码。文件结构如下：

C#/clipper_library/
├── clipper.cs           # 核心源代码文件
├── clipper_library.csproj  # 项目文件
└── Properties/
    └── AssemblyInfo.cs  # 程序集信息

1.3 源代码头部声明

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

从声明中可以看出：

版本信息：当前版本为 6.4.2，发布于 2017 年 2 月 27 日
开源许可：采用 Boost Software License，允许商业和非商业使用
算法基础：基于 Bala Vatti 的多边形裁剪算法（1992 年发表于 ACM Communications）

1.4 预处理器指令

源代码开头定义了几个重要的预处理器指令：

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

1.4.1 use_int32

#if use_int32
  using cInt = Int32;
#else
  using cInt = Int64;
#endif

默认关闭：使用 64 位整数（Int64）
启用后：使用 32 位整数（Int32），提高性能但限制坐标范围为 ±46340
实现方式：通过 using 别名定义 cInt 类型

坐标范围计算：32 位有符号整数最大值约为 2.1×10⁹，但由于中间计算可能产生溢出，实际安全范围被限制在 √(2³¹-1) ≈ 46340。

1.4.2 use_xyz

#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

默认关闭：IntPoint 只包含 X、Y 坐标
启用后：IntPoint 增加 Z 坐标成员
用途：支持 3D 坐标或存储额外属性信息

1.4.3 use_lines

#define use_lines

默认开启：启用开放路径（线段）的裁剪支持
关闭后：只支持闭合多边形的裁剪
性能影响：轻微

1.5 命名空间与类型别名

using System;
using System.Collections.Generic;

namespace ClipperLib
{
  using Path = List<IntPoint>;
  using Paths = List<List<IntPoint>>;
  
  // ... 类定义 ...
}

1.5.1 命名空间

所有 Clipper 相关的类型都定义在 ClipperLib 命名空间中，避免与其他库的命名冲突。

1.5.2 类型别名

源代码使用 using 指令创建了两个重要的类型别名：

Path：List<IntPoint>，表示一条路径（多边形轮廓或开放线段）
Paths：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();

1.6 核心类概览

Clipper1 的 C# 实现包含以下核心类和结构：

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

类型	说明
`IntPoint`	整数坐标点结构
`DoublePoint`	双精度浮点坐标点结构
`IntRect`	整数矩形边界结构
`PolyNode`	多边形树节点类
`PolyTree`	多边形树类，继承自 PolyNode
`Clipper`	多边形裁剪操作类
`ClipperOffset`	多边形偏移操作类

1.6.2 枚举类型

枚举	说明
`ClipType`	裁剪操作类型（交、并、差、异或）
`PolyType`	多边形类型（主体、裁剪）
`PolyFillType`	填充规则（奇偶、非零、正向、负向）
`JoinType`	连接类型（方形、圆形、斜接）
`EndType`	端点类型（闭合多边形、闭合线、开放端点等）

1.6.3 内部类型

类型	说明
`Int128`	128 位整数结构，用于高精度中间计算
`TEdge`	边缘数据结构
`LocalMinima`	局部极小值结构
`Scanbeam`	扫描线结构
`OutRec`	输出多边形记录
`OutPt`	输出点结构
`Join`	连接点结构
`ClipperBase`	Clipper 的基类

1.7 Vatti 算法简介

Clipper1 基于 Bala Vatti 在 1992 年发表的多边形裁剪算法。该算法的核心思想是：

1.7.1 扫描线方法

算法使用自下而上的扫描线方法处理多边形：

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

1.7.2 关键概念

局部极小值（Local Minima）：

多边形轮廓中 Y 坐标最低的点
算法从这些点开始向上扫描

活动边表（AEL）：

存储当前扫描线穿过的所有边
按 X 坐标排序

扫描线（Scanbeam）：

Y 坐标值，表示当前处理的水平线位置
在事件点（边的起点、终点、交点）处更新

1.7.3 算法流程示意

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

1.8 整数坐标的设计哲学

Clipper1 使用整数坐标而非浮点数，这是一个关键的设计决策：

1.8.1 浮点数的问题

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

1.8.2 整数坐标的优势

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

1.8.3 坐标转换策略

使用 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);
}

1.9 坐标范围限制

源代码定义了坐标范围常量：

#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

1.9.1 范围说明

模式	loRange	hiRange	说明
32位	32,767	32,767	约 ±3.2×10⁴
64位	1,073,741,823	4,611,686,018,427,387,903	约 ±10⁹

1.9.2 范围检查

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 位中间计算。

1.10 异常处理

Clipper 定义了自己的异常类型：

public class ClipperException : Exception
{
    public ClipperException(string description) : base(description) { }
}

常见的异常情况：

坐标超出范围："Coordinate outside allowed range"
无效的裁剪操作："AddPath: Open paths must be subject."
处理错误："ProcessIntersections error"

1.11 快速使用示例

以下是一个简单的多边形裁剪示例：

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})");
            }
        }
    }
}

1.12 本章小结

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

文件结构：单一源文件 clipper.cs，约 4800 行代码
预处理器指令：use_int32、use_xyz、use_lines 控制编译选项
类型系统：使用整数坐标确保数值稳定性
算法基础：基于 Vatti 的扫描线多边形裁剪算法
核心类：Clipper（裁剪）、ClipperOffset（偏移）、PolyTree（结果组织）

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

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