多边形裁剪这个词听着像图形学的教科书名词但真到了工程里它出现的地方比想象中多得多排版软件里两个色块叠加要算公共区域CAD 里把零件轮廓和加工窗口求交地图渲染时把行政区边界和可视窗口做一次裁切甚至 3D 切片软件每一层的轮廓合并底层都是同一件事——把两个或多个多边形按规则算出新的多边形。我最早接触 Clipper 系列是因为一个排版模块要在预览阶段实时显示两个形状叠在一起剩下什么自研算法在自交轮廓上崩了好几次最后换成了 Clipper2。这篇就聊 Clipper2 在多语言环境下的落地C 怎么接、C# 怎么用、Delphi 怎么封装以及跨平台时那些不看文档根本想不到的细节。适合已经知道布尔运算是什么、正准备把它塞进自己项目里的开发者也适合被浮点误差折磨过、想找一个稳定方案的人。1. 先把问题说清楚多边形裁剪的坑在哪1.1 业务里那些求交集的真实场景先说清楚这类库到底解决什么问题。给定两组多边形一组叫主体subject一组叫裁剪clip按指定规则算出结果交集是两边都覆盖的部分并集是合并后的外轮廓差集是主体减掉裁剪异或是两边不重叠的部分。听起来是四个简单操作难点全在多边形这三个字上。现实里的多边形不会老老实实是一个凸的、不自交的、顶点按顺序排好的环。它可能是凹的、可能自交成8字、可能有内孔、可能两个环共边、可能有三个顶点共线、可能面积小到小数点后六位。我见过一个路网数据相邻地块边界共享同一条线段两个形状求并集的时候如果实现里对共线边处理不严谨结果里就会冒出一堆长度为零的碎边下游渲染直接出锯齿。还有一个容易被忽略的点结果不只是一堆轮廓它是有层级的。一个外环里面套一个内环内环里再套一个外环这种嵌套关系决定了下游怎么填充。用 EvenOdd 填充规则时嵌套层次靠奇偶判断用 NonZero 时靠方向判断。如果你的库只返回一堆平铺的环不告诉你谁是谁的孔那你在下游还得自己重新做一遍点在多边形内的判定性能直接打对折。这是我选型时最先看的一个能力。1.2 自研扫描线的诱惑与代价刚遇到这类需求很多人的第一反应是自己写。逻辑确实不复杂把所有边的端点按 Y 排序扫描线从上往下走维护一个当前活跃边的集合遇到交点就翻转内外状态。教科书上的扫描线填充算法一两百行能跑起来。但真正上线之后问题会一个接一个冒出来。第一是退化情况两条边完全重合怎么办顶点正好落在扫描线上怎么办交点在端点怎么办。每一种都需要单独的特判分支而这些分支之间还会互相干扰。第二是精度浮点坐标下理论上相等的两个交点算出来差 1e-16排序之后顺序变了内外状态就翻错结果就是一个本不该出现的细长碎片。第三是性能朴素实现是 O(n²) 的两两求交一个带几千个顶点的轮廓在实时预览里就是卡顿。我当初自研的版本在测试集上跑了两个月没出问题上线第一周就遇到一个客户数据两条边夹角极小交点算出来落在边的延长线上整个结果偏移了几毫米。那次之后我彻底放弃了自研路线。不是自研不可能做对而是要做对需要投入的调试成本远超引入一个成熟库的成本。1.3 选型对比为什么最后落在 Clipper2 上当时横向比较了几种方案把关键维度列出来方案坐标模型抗退化能力多语言支持偏移功能接入成本自研扫描线浮点需要大量特判无需另写前期低后期极高通用几何模板库浮点为主较强仅 C有但接口复杂编译慢模板报错难读某脚本语言几何库浮点中等主要绑定脚本语言有跨语言调用有开销Clipper264 位整数强官方专门处理退化C、C#、Delphi 同源内置且成熟引入源码即可决定性因素是整数坐标。Clipper2 的所有几何运算都在 64 位整数上做坐标先放大成整数再算加法和比较都是精确的不存在理论上相等但实际差一点的情况。浮点误差这个最恶心的问题从根上被绕开了。代价是你得自己管缩放后面会专门讲怎么定这个比例。第二个因素是三种语言的实现是同一个人维护的同一套算法C、C#、Delphi 的版本行为一致。这对我们这种服务端 C#、客户端 C、还有一套老 Delphi 工具链的环境太重要了——同一份图形数据三个端算出来的结果必须一模一样否则联调时会怀疑人生。第三个因素是偏移offset/inflate是内置的。很多库的布尔运算做得不错但一提到把轮廓向外扩 2 毫米就得自己沿每条边做法线、处理尖角、处理自交工作量不比布尔运算小。Clipper2 把这块一起给了而且支持圆角、斜角、方角三种连接方式和多种端点处理省了很多事。2. Clipper2 的核心模型路径、填充规则与精度2.1 Path、Paths、PolyTree 三层结构用 Clipper2 之前先把它的三个数据层次理清楚不然后面看代码会一直懵。最底层是单条路径也就是一个点序列表示一个闭合环或者一条开放折线。整数版本的点是 64 位整数对浮点版本的点是双精度对。一条路径就是一个动态数组注意它是有序的点的顺序决定了环的方向而方向在 NonZero 填充规则下是有语义的。中间层是路径集合就是一个路径的数组。一次裁剪的输入输出都是这个层次主体是一组路径裁剪是一组路径结果也是一组路径。这里有个关键认知——路径集合里的每条路径是独立的环环与环之间的关系谁在谁里面在这个层次上是丢失的。最上层是树形结构它会告诉你层级关系最外层是若干顶级外环每个外环下面挂着它的直接内孔每个内孔下面又可能挂着岛屿。如果你的下游需要知道这个孔属于哪个外轮廓就必须用树形输出而不是平铺的路径集合。我踩过一次坑一开始图省事只用平铺结果然后在渲染时用点在多边形内逐个判断层级。数据量小的时候没问题一旦单帧有几百个环嵌套判断就是 O(n²)帧率直接掉到个位数。换成树形输出之后遍历一次就拿到了完整层级性能问题当场消失。提示如果你的场景只是把结果显示成一张图平铺结果够用只要涉及孔洞归属多层嵌套按层着色一开始就用树形输出别等到性能出问题再改。2.2 裁剪类型与填充规则的组合逻辑裁剪类型好理解就是交集、并集、差集、异或四种。真正需要花时间理解的是填充规则它决定了什么样的区域算在图形内部。一条自交的路径在数学上围出的区域不止一块。填充规则就是判定标准奇偶规则认为从无穷远射一条线过来穿过奇数条边就算内部非零规则认为看穿越方向正向加一负向减一结果不为零才算内部正方向和负方向规则更直接只看某一个方向的环绕是否为正。这两个维度是正交的组合起来才有完整语义。举个实际例子你有一个回字形的轮廓外环正向、内环反向用非零规则求并集结果是一个带孔的图形如果用奇偶规则结果一样但如果内环方向不小心搞反了非零规则下这个孔就会被填实奇偶规则下依然是孔。这就是为什么很多人换了数据源之后结果突然变了——不是库的问题是数据的方向约定变了。我的经验是数据来源可控、方向规范统一时用非零规则它对方向敏感能表达挖孔的意图数据来源杂乱、方向不可信时用奇偶规则它只看几何位置不看方向容错性更好。至于两个方向规则一般用于处理只保留某一侧的特殊场景日常用得少。还有一个细节Clipper2 内部判定方向是靠计算有符号面积。当你的坐标系 Y 轴朝下屏幕坐标常见时视觉上的顺时针和数学上的正向是反的。这个不影响结果正确性但会影响你对正方向的直觉判断调试时容易看错。2.3 整数坐标与缩放因子的取值方法这是整个库用起来最需要动脑子的地方。所有输入坐标必须是整数如果你的原始数据是浮点毫米、米、经纬度都算必须先乘一个比例因子转成整数算完再除回去。比例因子怎么定两条约束。往大了取精度高但可能溢出往小了取安全但会丢精度。64 位有符号整数的范围是约 ±9.22×10¹⁸。但你不能贴着上限用因为内部运算会出现坐标相减、偏移量相加、以及为了判定交点做的乘法实际可用范围要留出至少两个数量级的余量。我一般的算法是这样先估出原始坐标的绝对值上限记作 M再定出需要保留的小数位数 d。比例因子就是 10^d。转换后的坐标上限是 M × 10^d。这个值控制在 10¹⁵ 以内基本可以认为绝对安全。举个例子。地图数据经纬度范围在 ±180 和 ±90需要保留到小数点后 7 位大约 1 厘米级别。M 取 200d 取 7缩放后上限是 2×10⁹离 10¹⁵ 差得远非常安全。再比如 CAD 数据单位是毫米零件尺寸在 ±1000 毫米需要保留到 0.001 毫米。M 取 1000d 取 3缩放后上限是 10⁶同样安全。真正需要注意的是偏移量。做向外扩 2 毫米这种操作时偏移量也要乘同一个比例因子。如果你的偏移量是 0.5 微米缩放因子是 1000也就是精度到 0.001 毫米那偏移量换算成整数就是 0.5会被截断成 0 或者 1误差百分之百。这种情况必须把比例因子提到 10⁶ 以上。注意缩放因子一旦定下来整条流水线必须统一。主体、裁剪、偏移量、容差参数全部用同一个因子。混用是结果错乱最常见的原因而且错得很隐蔽——图形看着差不多但边界对不齐。3. C 接入实操编译、最小示例与偏移3.1 三种接入方式与 CMake 配置C 版本的源码是纯头文件加少量实现文件接入方式有三种按项目规模选。第一种把库的源码目录整个拷进你的工程加进编译列表。这种方式最粗暴也最省心适合小项目或者需要改库源码的场景。缺点是升级时不好替换。第二种用 CMake 的add_subdirectory把库当成子工程。这是我最推荐的方式库的构建配置它自己管你只需要链接目标。写法大致是这样add_subdirectory(third_party/clipper2) target_link_libraries(your_target PRIVATE Clipper2::Clipper2)目标名字在不同版本里有差异可能是Clipper2::Clipper2也可能只是一个普通库名。别猜打开库目录下的CMakeLists.txt看一眼add_library那行就知道了。第三种先单独编译成静态库再链接。适合你有很多子工程、不想每个都编译一遍库源码的情况。头文件引用路径一般是库名加子目录的形式#include clipper2/clipper.h如果你只用到基础的布尔运算其实可以只引更细的头文件核心类型、引擎、偏移各一个编译能快一点。但工程里为了省事我通常就引总入口让编译器自己处理。编译选项上有两点值得说。一是这个库大量使用模板和内联开-O2之后性能差异非常明显我实测过同一个数据在-O0下要 40 毫秒-O2下 4 毫秒差一个数量级。二是如果你要开浮点相关的激进优化比如快速数学注意它虽然主要用整数但偏移计算和容差里还是有浮点参与的激进优化可能带来微小偏差。3.2 第一个可跑通的裁剪程序下面这段是我平时用来验证环境是否正常的模板两个方块求交集#include clipper2/clipper.h #include iostream using namespace Clipper2Lib; int main() { // 主体左上角 100x100 的方块整数坐标已放大 Path64 subjectPath MakePath({0, 0, 100, 0, 100, 100, 0, 100}); // 裁剪偏移 50 的方块 Path64 clipPath MakePath({50, 50, 150, 50, 150, 150, 50, 150}); Paths64 subjects {subjectPath}; Paths64 clips {clipPath}; Paths64 solution Intersect(subjects, clips, FillRule::NonZero); std::cout result contours: solution.size() std::endl; for (const auto path : solution) { std::cout points: path.size() area: Area(path) std::endl; } return 0; }跑通的话你应该看到一条轮廓、四个点、面积 2500。这个数字能对上说明坐标、填充规则、面积计算全部正常。别小看这个自检我在三台不同机器上遇到过因为字符集或者int64定义不一致导致的编译问题跑一遍这个模板五分钟就能定位。需要树形结果的时候换成引擎式的写法Clipper64 clipper; clipper.AddSubject(subjects); clipper.AddClip(clips); PolyTree64 tree; clipper.Execute(ClipType::Intersection, FillRule::NonZero, tree); // 遍历层级tree 是根节点它的子节点是顶级外环 for (const auto topNode : tree) { std::cout outer ring, child count: topNode-Count() std::endl; }用引擎对象的时候有个必须记住的点同一个对象重复用之前要清理。不清的话上一批的输入还留在里面结果会莫名其妙地多出一堆东西。我在一个批处理循环里忘了这茬跑出来的结果集大小是预期的三倍查了两个小时才发现是没清空。3.3 偏移Inflate与开放路径处理偏移是 Clipper2 相对其他库的一个明显优势一行调用就能把轮廓按指定距离外扩或内缩double delta 10.0; // 放大 10 个单位负值表示内缩 double miterLimit 2.0; // 斜接时的最大延伸倍数 double arcTolerance 0.25; // 圆角近似的容差 Paths64 inflated InflatePaths( subjects, delta, JoinType::Round, EndType::Polygon, miterLimit, arcTolerance);四个参数各有讲究。连接方式决定尖角怎么处理斜接会顺着两条边的方向延长到交点上尖角会很好看但角度极小的时候延伸会失控圆角把尖角替换成圆弧视觉最平滑代价是点数变多方角把尖角切平介于两者之间。端点方式只在开放路径时起作用闭合轮廓用闭合那种就行。斜接限制是给斜接兜底的当两条边的夹角小到一定程度按几何算出来的尖角长度会趋于无穷这个参数就是最多允许延伸到边长的几倍超过就改成方角。默认 2.0 对大多数场景够用如果你的图形有很多锐角又想保留尖角可以调到 5 甚至 10但要接受极端情况下出现很长的尖刺。圆角容差决定圆弧被近似到什么精度数值越小点越密。这里有个容易搞错的地方这个容差是绝对单位跟你的坐标在同一量纲里。如果你的坐标缩放到 10⁶ 级别给 0.25 意味着极其精细点数会爆炸这时候应该给几百甚至几千。我的习惯是先算一下视觉上能接受的误差换算成缩放后的单位然后再填。开放路径是另一个容易忽略的能力。折线不是闭合环不能算内部但它可以参与裁剪也可以做偏移变成一条有宽度的带子。用法上要注意输入时要明确标记哪些是开放的输出时也要分开接收闭合结果和开放结果。如果混在一起传库会按闭合环去处理得到的结果看着像一团乱麻。顺带提一个性能技巧如果你的裁剪区域是一个轴对齐的矩形比如视口裁剪、图幅裁剪不要用通用的布尔运算用专门针对矩形的接口。它的原理简单得多只做边界比较速度能快好几倍。我做过一次视口裁剪通用接口处理一帧要 18 毫秒换成矩形专用接口之后是 2 毫秒出头。4. C# 与 Delphi 绑定同一套算法的不同写法4.1 C#日常用法与容易踩的命名坑C# 版本是同一套算法的托管实现用起来最省事。工程里加引用之后命名空间叫Clipper2Lib主要类型和 C 版本一一对应整数点、整数路径、整数路径集合加一层封装类提供静态方法。using Clipper2Lib; Paths64 subjects new Paths64(); subjects.Add(Clipper.MakePath(new int[] { 0, 0, 100, 0, 100, 100, 0, 100 })); Paths64 clips new Paths64(); clips.Add(Clipper.MakePath(new int[] { 50, 50, 150, 50, 150, 150, 50, 150 })); Paths64 solution Clipper.Intersect(subjects, clips, FillRule.NonZero); foreach (Path64 path in solution) { Console.WriteLine($points{path.Count}, area{Clipper.Area(path)}); }第一个坑是命名。C 那边是自由函数C# 这边全都收进了静态类里所以调用时前面必须带类名。搜文档看到别人写Intersect(...)直接调你的代码编译不过就是这个原因。第二个坑是浮点与整数两套类型并存。库同时提供了整数版本和浮点版本的路径类型名字只差一个字母。用混了不会编译报错因为重载存在但精度行为完全不同。整数版本是精确的浮点版本内部还是会把坐标放大转整数放大倍数由默认参数决定可能不是你想要的。我的建议是除非你完全确定数据量级否则统一用整数版本自己管缩放。第三个坑是数组与列表的转换。库的路径类型本质是一个点列表你从上层传下来的一般是数组或者自定义结构需要手动转换。批量数据时别在循环里反复创建对象一次性转好再调库否则 GC 压力会很明显——我见过一个场景光对象分配就占了总耗时的四成。第四个坑是返回值可能是空集合而不是 null。写判空的时候要注意空集合和 null 的语义不同用错会漏掉没算出来这种情况导致下游拿着一堆空数据继续跑。4.2 Delphi源码单元接入与数组管理Delphi 版本是源码单元形式直接加进工程就能用没有外部依赖。这一版对习惯现代泛型容器的人来说会有点别扭因为它的路径集合类型是自定义的动态数组包装不是标准的泛型列表。uses Clipper2; var Subject, Clip, Solution: TPaths64; P: TPath64; begin P : MakePath([0, 0, 100, 0, 100, 100, 0, 100]); Subject : TPaths64.Create(P); P : MakePath([50, 50, 150, 50, 150, 150, 50, 150]); Clip : TPaths64.Create(P); Solution : Intersect(Subject, Clip, frNonZero); WriteLn(contours: , Solution.Count); end;单元名和类型前缀在不同版本里可能略有出入我的建议是先把源码目录里的单元文件列出来看一眼别照抄网上的代码。前缀也有规律裁剪类型一般是ct开头填充规则fr开头连接方式jt开头端点方式et开头这些在源码里都能对上。Delphi 版有几个特别注意的地方。第一是内存管理路径集合是对象封装的动态数组用完要释放尤其是在循环里反复创建的场景不释放会一路涨内存。第二是坐标类型的位宽一定要确认你用的版本用的是 64 位整数坐标早期有些封装用的是 32 位坐标稍大就溢出而且溢出之后图形会翻到另一边症状特别诡异。第三是浮点偏移参数Delphi 的默认浮点类型和 C 的双精度在精度上是一致的但如果你在工程里改过浮点相关的编译选项结果可能会有微小差异。还有一点Delphi 版本对开放路径的支持和 C 版是对齐的但接口名字不太好猜。我当时的做法是先在 C 里把逻辑跑通再对着头文件找对应的 Pascal 声明比直接读 Pascal 源码快得多。4.3 三语言 API 对照与结果一致性验证跨语言项目最怕的就是同一份数据三个端算出来不一样。我把常用的调用做了个对照表方便迁移时对照能力C 写法C# 写法Delphi 写法构造单点序列MakePath({...})Clipper.MakePath(int[])MakePath([...])整数路径类型Path64Path64TPath64路径集合Paths64Paths64TPaths64求交集Intersect(a,b,rule)Clipper.Intersect(a,b,rule)Intersect(a,b,rule)填充规则枚举FillRule::NonZeroFillRule.NonZerofrNonZero偏移InflatePaths(...)Clipper.InflatePaths(...)InflatePaths(...)面积Area(path)Clipper.Area(path)Area(path)验证一致性有套简单办法准备一组边界数据自交的、带孔的、共边的、极小面积的在三个端各跑一遍把结果的**轮廓数量、每个轮廓的点数、每个轮廓的面积保留到小数点后三位**导出来做逐行比对。三个数字全对上基本可以认为行为一致。我当初就是靠这个方法发现 Delphi 端用的坐标位宽不对——其他都对只有坐标绝对值大的那几条数据面积差了一截。提示比对时不要直接比点序列的原始顺序。不同语言的排序稳定性、内部哈希顺序可能导致输出顶点的起点不同即使几何上完全一致。比较面积和点数必要时把点序列旋转到同一个起点再比。5. 性能调优与精度控制5.1 缩放因子的量化计算前面提了缩放因子的原则这里给一套可执行的计算流程照着套就行。第一步确定业务精度需求。比如边界误差不超过 0.01 毫米那小数位数就是 2 位比例因子至少 100。但我一般会在这个基础上再乘 10 到 100留出余量因为偏移运算和圆角近似会引入额外的舍入。第二步算出原始坐标的绝对值上限 M。把数据集里所有坐标过一遍取最大值别靠估。第三步检查是否溢出M × 比例因子 10¹⁵。超了就降精度或者分块处理。第四步反过来验算误差1 / 比例因子 就是坐标的量化步长。如果这个步长大于业务精度需求说明比例因子定小了。举个具体的一个零件图坐标范围 ±500 毫米要求误差不超过 0.005 毫米。比例因子取 1000量化步长 0.001 毫米满足要求缩放后坐标上限 5×10⁵远低于安全线。取 10000 也可以步长 0.0001更精细坐标上限 5×10⁶ 依然安全。这种量级下我会直接取 10000多点余量不吃亏。反例卫星影像的经纬度范围 ±180要求误差不超过 1 米约 1e-5 度。比例因子取 10⁷步长 1e-7 度够了缩放后坐标上限 1.8×10⁹安全。但如果有人为了更精确取 10¹²缩放后坐标就是 1.8×10¹⁴接近安全线再做偏移运算就可能溢出。这时候必须停手。5.2 批量处理时的对象复用单次裁剪的性能其实不太需要操心库内部的算法复杂度已经到了 O(n log n) 这个级别。真正影响体验的是批量场景一帧里几百个图形两两求交或者一次导入几万个地块做合并。第一个优化是复用引擎对象。反复创建销毁的开销不小尤其是对象内部会预分配缓冲区。做法是在循环外创建一个每次用之前清空用完保留。注意清空这个动作不能省前面说过。第二个优化是减少输入规模。裁剪之前先用包围盒做一次粗筛两个包围盒都不相交的图形直接跳过别送进库。这一步能砍掉大部分无效计算实现成本极低收益很高。我做过一个对比一万个地块两两求并集加包围盒预筛之后耗时从 3.2 秒降到 0.4 秒。第三个优化是控制输出点数。布尔运算本身不会产生太多点但偏移运算会产生大量用于近似圆弧的点。如果你的下游只是渲染容差可以给大一点如果下游要做进一步的几何运算才需要精细。我一般会给两套参数预览用粗的导出用细的。第四个优化是注意共线点的处理策略。库对是否保留共线点有开关保留会让点数变多但形状描述更完整不保留会让结果更精简。这个开关对性能的影响不算大但对下游影响不小——如果下游要做顶点索引精简过的结果更友好。5.3 结果后处理面积校验与去退化布尔运算的结果不保证是干净的。可能出现面积为零的退化环一条来回走的线、可能出现点数小于 3 的无效环、可能出现极细的碎片因为两个图形的边界只差零点几个单位。这些在下游都可能引发问题。我的标准后处理流程是这样先遍历结果算每条路径的有符号面积绝对值小于阈值的直接丢掉阈值取 1 到 2 个量化单位别取太大会误删真实的细长图形再检查点数少于 3 的丢掉最后如果下游需要做一次层级重建。面积校验还有个副产品它可以当作正确性检查。布尔运算有个数学性质并集的面积加上交集的面积等于两个输入面积之和。在一批数据上随机抽几个跑一下这个等式对不上就说明哪里出问题了。我用这个方法抓到过一次输入数据里混了未闭合路径的问题——单个图形看着正常加起来面积就是不对。还有一个容易忽略的点结果的坐标要转回原始量纲。除以缩放因子的时候用浮点除法别用整数除法否则会整体向内偏移多个相邻图形之间会出现肉眼可见的缝隙。6. 常见问题与排查实录6.1 结果为空或面积突变的排查表这类问题占了我在实际项目里遇到的八成以上整理成表方便对着查症状最可能的原因排查方法结果完全为空主体和裁剪的坐标量级不一致比如一个放大了 1000 倍另一个没放打印两边坐标的绝对值范围对比结果为空但图形明显相交填充规则用错自交轮廓在非零规则下被判成外部换成奇偶规则再跑一次结果是输入的完整拷贝裁剪区域根本没覆盖到主体或者裁剪路径方向导致被判为空把裁剪区域换成一个大包围盒验证面积只有预期的一小块裁剪路径的顶点顺序反了在非零规则下被当成孔检查裁剪路径的有符号面积符号面积比预期大很多主体本身自交非零规则下重叠部分被计了两次先用奇偶规则把主体规范化一遍结果里出现大量碎片输入有两个几乎重合但不完全重合的边界先对输入做一次小容差的简化排查的核心思路是二分定位先用两个最简单的方块验证环境再换成你的真实数据先用一个图形验证再上批量先用奇偶规则验证再换非零规则。每次只改一个变量很快就能锁定。6.2 孔洞与层级错乱的成因带孔图形的层级错乱是个高频问题症状是孔被填实了或者孔跑到外面去了。第一种成因是方向不一致。外环正着走、内环也正着走在非零规则下这两个环被当成两个独立实体交集结果里孔就没了。解决办法是在输入阶段做一次方向规范化算出每个环的有符号面积外环统一成一个方向内环统一成相反方向。库里有现成的判断函数几行代码的事。第二种成因是孔和外环不相交但被判定为嵌套。这种情况出现在图形有微小重叠或者有微小缝隙时——理论上内环应该完全在外环内部实际上有一两个单位的偏移判定就出错。解决办法是先把内环向内缩一点点或者把外环向外扩一点点制造明确的包含关系。第三种成因是用了平铺结果又自己重建层级。前面说过平铺结果丢掉了层级信息自己用点包含判断重建在共边、共点的情况下会判错。这种问题最隐蔽因为大部分数据都对只有边界情况错。直接换成树形输出一次解决。6.3 我在实际项目里踩过的几个坑第一个坑负零和符号问题。偏移量传 -0.0 的时候某些编译器下会得到一个非常小的负数导致内缩变成极小的外扩结果是图形几乎没变但多了一圈退化边。现在的做法是偏移量先做一次绝对值判断小于阈值直接返回原图。第二个坑多线程共享引擎对象。引擎对象内部有状态两个线程同时用一个对象结果会互相污染症状是随机出现错误的图形。这个坑很难查因为错误不固定。解决办法很简单每个线程一个对象或者加锁。我现在的做法是线程局部存储用起来最省心。第三个坑输入路径没有闭合。闭合环的最后一个点如果和第一个点重复库会自己处理但如果你传的路径首尾不接它会被当成开放路径在布尔运算里参与方式完全不同。批量数据里混进几条这样的路径结果就是大部分对少数几个莫名其妙。加一个输入校验检查首尾点距离超过阈值就报错比事后查便宜得多。第四个坑浮点参数在不同平台的舍入差异。偏移的容差参数是浮点在 x86 和 ARM 上某些中间结果的舍入可能差一个最低位导致圆角近似的点数差一两个。这个差异传到下游如果下游对点数敏感比如做顶点缓冲区的定长分配就会出问题。解决办法是给下游留余量别做精确的定长假设。第五个坑空输入的处理。主体为空或者裁剪为空时不同操作的行为不一样——空集和任何集合求并集是那个集合求交集是空集。如果你的业务逻辑没考虑这个会出现什么都没传进来但结果是一堆图形的诡异情况。加一层前置判断输入为空直接返回省得后面绕。最后说个我自己的体会。这类几何库用久了会发现真正的难点从来不是 API 怎么调而是数据本身的规范性。自交、方向不一致、首尾不闭合、坐标量级混乱这些问题在调库之前就已经存在了库只是把它们暴露出来。我现在的习惯是接入任何几何运算之前先写一个数据体检的小工具把轮廓数、点数、面积、方向、包围盒、是否自交全打出来看一遍。这一步花十分钟能省掉后面几小时的调试。至于参数怎么定我的经验是别追求理论最优先把一套能跑通的参数固定下来用真实数据跑冒烟测试看结果和预期差多少再针对性调——比对着文档推公式快得多。
多边形裁剪这个词听着像图形学的教科书名词但真到了工程里它出现的地方比想象中多得多排版软件里两个色块叠加要算公共区域CAD 里把零件轮廓和加工窗口求交地图渲染时把行政区边界和可视窗口做一次裁切甚至 3D 切片软件每一层的轮廓合并底层都是同一件事——把两个或多个多边形按规则算出新的多边形。我最早接触 Clipper 系列是因为一个排版模块要在预览阶段实时显示两个形状叠在一起剩下什么自研算法在自交轮廓上崩了好几次最后换成了 Clipper2。这篇就聊 Clipper2 在多语言环境下的落地C 怎么接、C# 怎么用、Delphi 怎么封装以及跨平台时那些不看文档根本想不到的细节。适合已经知道布尔运算是什么、正准备把它塞进自己项目里的开发者也适合被浮点误差折磨过、想找一个稳定方案的人。1. 先把问题说清楚多边形裁剪的坑在哪1.1 业务里那些求交集的真实场景先说清楚这类库到底解决什么问题。给定两组多边形一组叫主体subject一组叫裁剪clip按指定规则算出结果交集是两边都覆盖的部分并集是合并后的外轮廓差集是主体减掉裁剪异或是两边不重叠的部分。听起来是四个简单操作难点全在多边形这三个字上。现实里的多边形不会老老实实是一个凸的、不自交的、顶点按顺序排好的环。它可能是凹的、可能自交成8字、可能有内孔、可能两个环共边、可能有三个顶点共线、可能面积小到小数点后六位。我见过一个路网数据相邻地块边界共享同一条线段两个形状求并集的时候如果实现里对共线边处理不严谨结果里就会冒出一堆长度为零的碎边下游渲染直接出锯齿。还有一个容易被忽略的点结果不只是一堆轮廓它是有层级的。一个外环里面套一个内环内环里再套一个外环这种嵌套关系决定了下游怎么填充。用 EvenOdd 填充规则时嵌套层次靠奇偶判断用 NonZero 时靠方向判断。如果你的库只返回一堆平铺的环不告诉你谁是谁的孔那你在下游还得自己重新做一遍点在多边形内的判定性能直接打对折。这是我选型时最先看的一个能力。1.2 自研扫描线的诱惑与代价刚遇到这类需求很多人的第一反应是自己写。逻辑确实不复杂把所有边的端点按 Y 排序扫描线从上往下走维护一个当前活跃边的集合遇到交点就翻转内外状态。教科书上的扫描线填充算法一两百行能跑起来。但真正上线之后问题会一个接一个冒出来。第一是退化情况两条边完全重合怎么办顶点正好落在扫描线上怎么办交点在端点怎么办。每一种都需要单独的特判分支而这些分支之间还会互相干扰。第二是精度浮点坐标下理论上相等的两个交点算出来差 1e-16排序之后顺序变了内外状态就翻错结果就是一个本不该出现的细长碎片。第三是性能朴素实现是 O(n²) 的两两求交一个带几千个顶点的轮廓在实时预览里就是卡顿。我当初自研的版本在测试集上跑了两个月没出问题上线第一周就遇到一个客户数据两条边夹角极小交点算出来落在边的延长线上整个结果偏移了几毫米。那次之后我彻底放弃了自研路线。不是自研不可能做对而是要做对需要投入的调试成本远超引入一个成熟库的成本。1.3 选型对比为什么最后落在 Clipper2 上当时横向比较了几种方案把关键维度列出来方案坐标模型抗退化能力多语言支持偏移功能接入成本自研扫描线浮点需要大量特判无需另写前期低后期极高通用几何模板库浮点为主较强仅 C有但接口复杂编译慢模板报错难读某脚本语言几何库浮点中等主要绑定脚本语言有跨语言调用有开销Clipper264 位整数强官方专门处理退化C、C#、Delphi 同源内置且成熟引入源码即可决定性因素是整数坐标。Clipper2 的所有几何运算都在 64 位整数上做坐标先放大成整数再算加法和比较都是精确的不存在理论上相等但实际差一点的情况。浮点误差这个最恶心的问题从根上被绕开了。代价是你得自己管缩放后面会专门讲怎么定这个比例。第二个因素是三种语言的实现是同一个人维护的同一套算法C、C#、Delphi 的版本行为一致。这对我们这种服务端 C#、客户端 C、还有一套老 Delphi 工具链的环境太重要了——同一份图形数据三个端算出来的结果必须一模一样否则联调时会怀疑人生。第三个因素是偏移offset/inflate是内置的。很多库的布尔运算做得不错但一提到把轮廓向外扩 2 毫米就得自己沿每条边做法线、处理尖角、处理自交工作量不比布尔运算小。Clipper2 把这块一起给了而且支持圆角、斜角、方角三种连接方式和多种端点处理省了很多事。2. Clipper2 的核心模型路径、填充规则与精度2.1 Path、Paths、PolyTree 三层结构用 Clipper2 之前先把它的三个数据层次理清楚不然后面看代码会一直懵。最底层是单条路径也就是一个点序列表示一个闭合环或者一条开放折线。整数版本的点是 64 位整数对浮点版本的点是双精度对。一条路径就是一个动态数组注意它是有序的点的顺序决定了环的方向而方向在 NonZero 填充规则下是有语义的。中间层是路径集合就是一个路径的数组。一次裁剪的输入输出都是这个层次主体是一组路径裁剪是一组路径结果也是一组路径。这里有个关键认知——路径集合里的每条路径是独立的环环与环之间的关系谁在谁里面在这个层次上是丢失的。最上层是树形结构它会告诉你层级关系最外层是若干顶级外环每个外环下面挂着它的直接内孔每个内孔下面又可能挂着岛屿。如果你的下游需要知道这个孔属于哪个外轮廓就必须用树形输出而不是平铺的路径集合。我踩过一次坑一开始图省事只用平铺结果然后在渲染时用点在多边形内逐个判断层级。数据量小的时候没问题一旦单帧有几百个环嵌套判断就是 O(n²)帧率直接掉到个位数。换成树形输出之后遍历一次就拿到了完整层级性能问题当场消失。提示如果你的场景只是把结果显示成一张图平铺结果够用只要涉及孔洞归属多层嵌套按层着色一开始就用树形输出别等到性能出问题再改。2.2 裁剪类型与填充规则的组合逻辑裁剪类型好理解就是交集、并集、差集、异或四种。真正需要花时间理解的是填充规则它决定了什么样的区域算在图形内部。一条自交的路径在数学上围出的区域不止一块。填充规则就是判定标准奇偶规则认为从无穷远射一条线过来穿过奇数条边就算内部非零规则认为看穿越方向正向加一负向减一结果不为零才算内部正方向和负方向规则更直接只看某一个方向的环绕是否为正。这两个维度是正交的组合起来才有完整语义。举个实际例子你有一个回字形的轮廓外环正向、内环反向用非零规则求并集结果是一个带孔的图形如果用奇偶规则结果一样但如果内环方向不小心搞反了非零规则下这个孔就会被填实奇偶规则下依然是孔。这就是为什么很多人换了数据源之后结果突然变了——不是库的问题是数据的方向约定变了。我的经验是数据来源可控、方向规范统一时用非零规则它对方向敏感能表达挖孔的意图数据来源杂乱、方向不可信时用奇偶规则它只看几何位置不看方向容错性更好。至于两个方向规则一般用于处理只保留某一侧的特殊场景日常用得少。还有一个细节Clipper2 内部判定方向是靠计算有符号面积。当你的坐标系 Y 轴朝下屏幕坐标常见时视觉上的顺时针和数学上的正向是反的。这个不影响结果正确性但会影响你对正方向的直觉判断调试时容易看错。2.3 整数坐标与缩放因子的取值方法这是整个库用起来最需要动脑子的地方。所有输入坐标必须是整数如果你的原始数据是浮点毫米、米、经纬度都算必须先乘一个比例因子转成整数算完再除回去。比例因子怎么定两条约束。往大了取精度高但可能溢出往小了取安全但会丢精度。64 位有符号整数的范围是约 ±9.22×10¹⁸。但你不能贴着上限用因为内部运算会出现坐标相减、偏移量相加、以及为了判定交点做的乘法实际可用范围要留出至少两个数量级的余量。我一般的算法是这样先估出原始坐标的绝对值上限记作 M再定出需要保留的小数位数 d。比例因子就是 10^d。转换后的坐标上限是 M × 10^d。这个值控制在 10¹⁵ 以内基本可以认为绝对安全。举个例子。地图数据经纬度范围在 ±180 和 ±90需要保留到小数点后 7 位大约 1 厘米级别。M 取 200d 取 7缩放后上限是 2×10⁹离 10¹⁵ 差得远非常安全。再比如 CAD 数据单位是毫米零件尺寸在 ±1000 毫米需要保留到 0.001 毫米。M 取 1000d 取 3缩放后上限是 10⁶同样安全。真正需要注意的是偏移量。做向外扩 2 毫米这种操作时偏移量也要乘同一个比例因子。如果你的偏移量是 0.5 微米缩放因子是 1000也就是精度到 0.001 毫米那偏移量换算成整数就是 0.5会被截断成 0 或者 1误差百分之百。这种情况必须把比例因子提到 10⁶ 以上。注意缩放因子一旦定下来整条流水线必须统一。主体、裁剪、偏移量、容差参数全部用同一个因子。混用是结果错乱最常见的原因而且错得很隐蔽——图形看着差不多但边界对不齐。3. C 接入实操编译、最小示例与偏移3.1 三种接入方式与 CMake 配置C 版本的源码是纯头文件加少量实现文件接入方式有三种按项目规模选。第一种把库的源码目录整个拷进你的工程加进编译列表。这种方式最粗暴也最省心适合小项目或者需要改库源码的场景。缺点是升级时不好替换。第二种用 CMake 的add_subdirectory把库当成子工程。这是我最推荐的方式库的构建配置它自己管你只需要链接目标。写法大致是这样add_subdirectory(third_party/clipper2) target_link_libraries(your_target PRIVATE Clipper2::Clipper2)目标名字在不同版本里有差异可能是Clipper2::Clipper2也可能只是一个普通库名。别猜打开库目录下的CMakeLists.txt看一眼add_library那行就知道了。第三种先单独编译成静态库再链接。适合你有很多子工程、不想每个都编译一遍库源码的情况。头文件引用路径一般是库名加子目录的形式#include clipper2/clipper.h如果你只用到基础的布尔运算其实可以只引更细的头文件核心类型、引擎、偏移各一个编译能快一点。但工程里为了省事我通常就引总入口让编译器自己处理。编译选项上有两点值得说。一是这个库大量使用模板和内联开-O2之后性能差异非常明显我实测过同一个数据在-O0下要 40 毫秒-O2下 4 毫秒差一个数量级。二是如果你要开浮点相关的激进优化比如快速数学注意它虽然主要用整数但偏移计算和容差里还是有浮点参与的激进优化可能带来微小偏差。3.2 第一个可跑通的裁剪程序下面这段是我平时用来验证环境是否正常的模板两个方块求交集#include clipper2/clipper.h #include iostream using namespace Clipper2Lib; int main() { // 主体左上角 100x100 的方块整数坐标已放大 Path64 subjectPath MakePath({0, 0, 100, 0, 100, 100, 0, 100}); // 裁剪偏移 50 的方块 Path64 clipPath MakePath({50, 50, 150, 50, 150, 150, 50, 150}); Paths64 subjects {subjectPath}; Paths64 clips {clipPath}; Paths64 solution Intersect(subjects, clips, FillRule::NonZero); std::cout result contours: solution.size() std::endl; for (const auto path : solution) { std::cout points: path.size() area: Area(path) std::endl; } return 0; }跑通的话你应该看到一条轮廓、四个点、面积 2500。这个数字能对上说明坐标、填充规则、面积计算全部正常。别小看这个自检我在三台不同机器上遇到过因为字符集或者int64定义不一致导致的编译问题跑一遍这个模板五分钟就能定位。需要树形结果的时候换成引擎式的写法Clipper64 clipper; clipper.AddSubject(subjects); clipper.AddClip(clips); PolyTree64 tree; clipper.Execute(ClipType::Intersection, FillRule::NonZero, tree); // 遍历层级tree 是根节点它的子节点是顶级外环 for (const auto topNode : tree) { std::cout outer ring, child count: topNode-Count() std::endl; }用引擎对象的时候有个必须记住的点同一个对象重复用之前要清理。不清的话上一批的输入还留在里面结果会莫名其妙地多出一堆东西。我在一个批处理循环里忘了这茬跑出来的结果集大小是预期的三倍查了两个小时才发现是没清空。3.3 偏移Inflate与开放路径处理偏移是 Clipper2 相对其他库的一个明显优势一行调用就能把轮廓按指定距离外扩或内缩double delta 10.0; // 放大 10 个单位负值表示内缩 double miterLimit 2.0; // 斜接时的最大延伸倍数 double arcTolerance 0.25; // 圆角近似的容差 Paths64 inflated InflatePaths( subjects, delta, JoinType::Round, EndType::Polygon, miterLimit, arcTolerance);四个参数各有讲究。连接方式决定尖角怎么处理斜接会顺着两条边的方向延长到交点上尖角会很好看但角度极小的时候延伸会失控圆角把尖角替换成圆弧视觉最平滑代价是点数变多方角把尖角切平介于两者之间。端点方式只在开放路径时起作用闭合轮廓用闭合那种就行。斜接限制是给斜接兜底的当两条边的夹角小到一定程度按几何算出来的尖角长度会趋于无穷这个参数就是最多允许延伸到边长的几倍超过就改成方角。默认 2.0 对大多数场景够用如果你的图形有很多锐角又想保留尖角可以调到 5 甚至 10但要接受极端情况下出现很长的尖刺。圆角容差决定圆弧被近似到什么精度数值越小点越密。这里有个容易搞错的地方这个容差是绝对单位跟你的坐标在同一量纲里。如果你的坐标缩放到 10⁶ 级别给 0.25 意味着极其精细点数会爆炸这时候应该给几百甚至几千。我的习惯是先算一下视觉上能接受的误差换算成缩放后的单位然后再填。开放路径是另一个容易忽略的能力。折线不是闭合环不能算内部但它可以参与裁剪也可以做偏移变成一条有宽度的带子。用法上要注意输入时要明确标记哪些是开放的输出时也要分开接收闭合结果和开放结果。如果混在一起传库会按闭合环去处理得到的结果看着像一团乱麻。顺带提一个性能技巧如果你的裁剪区域是一个轴对齐的矩形比如视口裁剪、图幅裁剪不要用通用的布尔运算用专门针对矩形的接口。它的原理简单得多只做边界比较速度能快好几倍。我做过一次视口裁剪通用接口处理一帧要 18 毫秒换成矩形专用接口之后是 2 毫秒出头。4. C# 与 Delphi 绑定同一套算法的不同写法4.1 C#日常用法与容易踩的命名坑C# 版本是同一套算法的托管实现用起来最省事。工程里加引用之后命名空间叫Clipper2Lib主要类型和 C 版本一一对应整数点、整数路径、整数路径集合加一层封装类提供静态方法。using Clipper2Lib; Paths64 subjects new Paths64(); subjects.Add(Clipper.MakePath(new int[] { 0, 0, 100, 0, 100, 100, 0, 100 })); Paths64 clips new Paths64(); clips.Add(Clipper.MakePath(new int[] { 50, 50, 150, 50, 150, 150, 50, 150 })); Paths64 solution Clipper.Intersect(subjects, clips, FillRule.NonZero); foreach (Path64 path in solution) { Console.WriteLine($points{path.Count}, area{Clipper.Area(path)}); }第一个坑是命名。C 那边是自由函数C# 这边全都收进了静态类里所以调用时前面必须带类名。搜文档看到别人写Intersect(...)直接调你的代码编译不过就是这个原因。第二个坑是浮点与整数两套类型并存。库同时提供了整数版本和浮点版本的路径类型名字只差一个字母。用混了不会编译报错因为重载存在但精度行为完全不同。整数版本是精确的浮点版本内部还是会把坐标放大转整数放大倍数由默认参数决定可能不是你想要的。我的建议是除非你完全确定数据量级否则统一用整数版本自己管缩放。第三个坑是数组与列表的转换。库的路径类型本质是一个点列表你从上层传下来的一般是数组或者自定义结构需要手动转换。批量数据时别在循环里反复创建对象一次性转好再调库否则 GC 压力会很明显——我见过一个场景光对象分配就占了总耗时的四成。第四个坑是返回值可能是空集合而不是 null。写判空的时候要注意空集合和 null 的语义不同用错会漏掉没算出来这种情况导致下游拿着一堆空数据继续跑。4.2 Delphi源码单元接入与数组管理Delphi 版本是源码单元形式直接加进工程就能用没有外部依赖。这一版对习惯现代泛型容器的人来说会有点别扭因为它的路径集合类型是自定义的动态数组包装不是标准的泛型列表。uses Clipper2; var Subject, Clip, Solution: TPaths64; P: TPath64; begin P : MakePath([0, 0, 100, 0, 100, 100, 0, 100]); Subject : TPaths64.Create(P); P : MakePath([50, 50, 150, 50, 150, 150, 50, 150]); Clip : TPaths64.Create(P); Solution : Intersect(Subject, Clip, frNonZero); WriteLn(contours: , Solution.Count); end;单元名和类型前缀在不同版本里可能略有出入我的建议是先把源码目录里的单元文件列出来看一眼别照抄网上的代码。前缀也有规律裁剪类型一般是ct开头填充规则fr开头连接方式jt开头端点方式et开头这些在源码里都能对上。Delphi 版有几个特别注意的地方。第一是内存管理路径集合是对象封装的动态数组用完要释放尤其是在循环里反复创建的场景不释放会一路涨内存。第二是坐标类型的位宽一定要确认你用的版本用的是 64 位整数坐标早期有些封装用的是 32 位坐标稍大就溢出而且溢出之后图形会翻到另一边症状特别诡异。第三是浮点偏移参数Delphi 的默认浮点类型和 C 的双精度在精度上是一致的但如果你在工程里改过浮点相关的编译选项结果可能会有微小差异。还有一点Delphi 版本对开放路径的支持和 C 版是对齐的但接口名字不太好猜。我当时的做法是先在 C 里把逻辑跑通再对着头文件找对应的 Pascal 声明比直接读 Pascal 源码快得多。4.3 三语言 API 对照与结果一致性验证跨语言项目最怕的就是同一份数据三个端算出来不一样。我把常用的调用做了个对照表方便迁移时对照能力C 写法C# 写法Delphi 写法构造单点序列MakePath({...})Clipper.MakePath(int[])MakePath([...])整数路径类型Path64Path64TPath64路径集合Paths64Paths64TPaths64求交集Intersect(a,b,rule)Clipper.Intersect(a,b,rule)Intersect(a,b,rule)填充规则枚举FillRule::NonZeroFillRule.NonZerofrNonZero偏移InflatePaths(...)Clipper.InflatePaths(...)InflatePaths(...)面积Area(path)Clipper.Area(path)Area(path)验证一致性有套简单办法准备一组边界数据自交的、带孔的、共边的、极小面积的在三个端各跑一遍把结果的**轮廓数量、每个轮廓的点数、每个轮廓的面积保留到小数点后三位**导出来做逐行比对。三个数字全对上基本可以认为行为一致。我当初就是靠这个方法发现 Delphi 端用的坐标位宽不对——其他都对只有坐标绝对值大的那几条数据面积差了一截。提示比对时不要直接比点序列的原始顺序。不同语言的排序稳定性、内部哈希顺序可能导致输出顶点的起点不同即使几何上完全一致。比较面积和点数必要时把点序列旋转到同一个起点再比。5. 性能调优与精度控制5.1 缩放因子的量化计算前面提了缩放因子的原则这里给一套可执行的计算流程照着套就行。第一步确定业务精度需求。比如边界误差不超过 0.01 毫米那小数位数就是 2 位比例因子至少 100。但我一般会在这个基础上再乘 10 到 100留出余量因为偏移运算和圆角近似会引入额外的舍入。第二步算出原始坐标的绝对值上限 M。把数据集里所有坐标过一遍取最大值别靠估。第三步检查是否溢出M × 比例因子 10¹⁵。超了就降精度或者分块处理。第四步反过来验算误差1 / 比例因子 就是坐标的量化步长。如果这个步长大于业务精度需求说明比例因子定小了。举个具体的一个零件图坐标范围 ±500 毫米要求误差不超过 0.005 毫米。比例因子取 1000量化步长 0.001 毫米满足要求缩放后坐标上限 5×10⁵远低于安全线。取 10000 也可以步长 0.0001更精细坐标上限 5×10⁶ 依然安全。这种量级下我会直接取 10000多点余量不吃亏。反例卫星影像的经纬度范围 ±180要求误差不超过 1 米约 1e-5 度。比例因子取 10⁷步长 1e-7 度够了缩放后坐标上限 1.8×10⁹安全。但如果有人为了更精确取 10¹²缩放后坐标就是 1.8×10¹⁴接近安全线再做偏移运算就可能溢出。这时候必须停手。5.2 批量处理时的对象复用单次裁剪的性能其实不太需要操心库内部的算法复杂度已经到了 O(n log n) 这个级别。真正影响体验的是批量场景一帧里几百个图形两两求交或者一次导入几万个地块做合并。第一个优化是复用引擎对象。反复创建销毁的开销不小尤其是对象内部会预分配缓冲区。做法是在循环外创建一个每次用之前清空用完保留。注意清空这个动作不能省前面说过。第二个优化是减少输入规模。裁剪之前先用包围盒做一次粗筛两个包围盒都不相交的图形直接跳过别送进库。这一步能砍掉大部分无效计算实现成本极低收益很高。我做过一个对比一万个地块两两求并集加包围盒预筛之后耗时从 3.2 秒降到 0.4 秒。第三个优化是控制输出点数。布尔运算本身不会产生太多点但偏移运算会产生大量用于近似圆弧的点。如果你的下游只是渲染容差可以给大一点如果下游要做进一步的几何运算才需要精细。我一般会给两套参数预览用粗的导出用细的。第四个优化是注意共线点的处理策略。库对是否保留共线点有开关保留会让点数变多但形状描述更完整不保留会让结果更精简。这个开关对性能的影响不算大但对下游影响不小——如果下游要做顶点索引精简过的结果更友好。5.3 结果后处理面积校验与去退化布尔运算的结果不保证是干净的。可能出现面积为零的退化环一条来回走的线、可能出现点数小于 3 的无效环、可能出现极细的碎片因为两个图形的边界只差零点几个单位。这些在下游都可能引发问题。我的标准后处理流程是这样先遍历结果算每条路径的有符号面积绝对值小于阈值的直接丢掉阈值取 1 到 2 个量化单位别取太大会误删真实的细长图形再检查点数少于 3 的丢掉最后如果下游需要做一次层级重建。面积校验还有个副产品它可以当作正确性检查。布尔运算有个数学性质并集的面积加上交集的面积等于两个输入面积之和。在一批数据上随机抽几个跑一下这个等式对不上就说明哪里出问题了。我用这个方法抓到过一次输入数据里混了未闭合路径的问题——单个图形看着正常加起来面积就是不对。还有一个容易忽略的点结果的坐标要转回原始量纲。除以缩放因子的时候用浮点除法别用整数除法否则会整体向内偏移多个相邻图形之间会出现肉眼可见的缝隙。6. 常见问题与排查实录6.1 结果为空或面积突变的排查表这类问题占了我在实际项目里遇到的八成以上整理成表方便对着查症状最可能的原因排查方法结果完全为空主体和裁剪的坐标量级不一致比如一个放大了 1000 倍另一个没放打印两边坐标的绝对值范围对比结果为空但图形明显相交填充规则用错自交轮廓在非零规则下被判成外部换成奇偶规则再跑一次结果是输入的完整拷贝裁剪区域根本没覆盖到主体或者裁剪路径方向导致被判为空把裁剪区域换成一个大包围盒验证面积只有预期的一小块裁剪路径的顶点顺序反了在非零规则下被当成孔检查裁剪路径的有符号面积符号面积比预期大很多主体本身自交非零规则下重叠部分被计了两次先用奇偶规则把主体规范化一遍结果里出现大量碎片输入有两个几乎重合但不完全重合的边界先对输入做一次小容差的简化排查的核心思路是二分定位先用两个最简单的方块验证环境再换成你的真实数据先用一个图形验证再上批量先用奇偶规则验证再换非零规则。每次只改一个变量很快就能锁定。6.2 孔洞与层级错乱的成因带孔图形的层级错乱是个高频问题症状是孔被填实了或者孔跑到外面去了。第一种成因是方向不一致。外环正着走、内环也正着走在非零规则下这两个环被当成两个独立实体交集结果里孔就没了。解决办法是在输入阶段做一次方向规范化算出每个环的有符号面积外环统一成一个方向内环统一成相反方向。库里有现成的判断函数几行代码的事。第二种成因是孔和外环不相交但被判定为嵌套。这种情况出现在图形有微小重叠或者有微小缝隙时——理论上内环应该完全在外环内部实际上有一两个单位的偏移判定就出错。解决办法是先把内环向内缩一点点或者把外环向外扩一点点制造明确的包含关系。第三种成因是用了平铺结果又自己重建层级。前面说过平铺结果丢掉了层级信息自己用点包含判断重建在共边、共点的情况下会判错。这种问题最隐蔽因为大部分数据都对只有边界情况错。直接换成树形输出一次解决。6.3 我在实际项目里踩过的几个坑第一个坑负零和符号问题。偏移量传 -0.0 的时候某些编译器下会得到一个非常小的负数导致内缩变成极小的外扩结果是图形几乎没变但多了一圈退化边。现在的做法是偏移量先做一次绝对值判断小于阈值直接返回原图。第二个坑多线程共享引擎对象。引擎对象内部有状态两个线程同时用一个对象结果会互相污染症状是随机出现错误的图形。这个坑很难查因为错误不固定。解决办法很简单每个线程一个对象或者加锁。我现在的做法是线程局部存储用起来最省心。第三个坑输入路径没有闭合。闭合环的最后一个点如果和第一个点重复库会自己处理但如果你传的路径首尾不接它会被当成开放路径在布尔运算里参与方式完全不同。批量数据里混进几条这样的路径结果就是大部分对少数几个莫名其妙。加一个输入校验检查首尾点距离超过阈值就报错比事后查便宜得多。第四个坑浮点参数在不同平台的舍入差异。偏移的容差参数是浮点在 x86 和 ARM 上某些中间结果的舍入可能差一个最低位导致圆角近似的点数差一两个。这个差异传到下游如果下游对点数敏感比如做顶点缓冲区的定长分配就会出问题。解决办法是给下游留余量别做精确的定长假设。第五个坑空输入的处理。主体为空或者裁剪为空时不同操作的行为不一样——空集和任何集合求并集是那个集合求交集是空集。如果你的业务逻辑没考虑这个会出现什么都没传进来但结果是一堆图形的诡异情况。加一层前置判断输入为空直接返回省得后面绕。最后说个我自己的体会。这类几何库用久了会发现真正的难点从来不是 API 怎么调而是数据本身的规范性。自交、方向不一致、首尾不闭合、坐标量级混乱这些问题在调库之前就已经存在了库只是把它们暴露出来。我现在的习惯是接入任何几何运算之前先写一个数据体检的小工具把轮廓数、点数、面积、方向、包围盒、是否自交全打出来看一遍。这一步花十分钟能省掉后面几小时的调试。至于参数怎么定我的经验是别追求理论最优先把一套能跑通的参数固定下来用真实数据跑冒烟测试看结果和预期差多少再针对性调——比对着文档推公式快得多。
