计算几何里的点积叉积、线段相交、凸包算法、多边形面积这四个东西几乎覆盖了二维几何编程八成的日常需求。我最早接触它们是在做一个图形编辑器的碰撞检测模块当时以为把公式抄下来就能跑结果上线之后遇到一堆肉眼看着明明相交却判成不相交的诡异问题排查了两天才发现是浮点误差和退化情形没处理。后来做地图标注、做物料排版、做游戏里的小地图裁剪又反复用到这套东西慢慢攒了一些真正能落地的经验。网上大部分教程只讲公式不讲边界代码跑得过样例跑不过真实数据。这篇就按我自己的实践顺序把四块内容串一遍从最基础的向量运算讲到能直接抄去用的完整实现顺带把踩过的坑和排查思路摊开说清楚。适合刚接触计算几何的同学当入门到进阶的过渡材料也适合已经写过一些几何代码但总在边界情况上翻车的朋友对照检查。1. 先把这几个模块的关系捋清楚1.1 为什么它们总是被放在一起讲这四个知识点看起来是并列的实际上是有依赖关系的。点积和叉积是原子运算线段相交判定是叉积的第一个正经应用凸包是线段拐向判断的批量版本多边形面积则是叉积的另一个经典用法。你把叉积吃透了后面三个基本就是换个场景调用同一个函数。我在实际项目里搭几何库的时候第一件事永远是写一个稳健的cross和dot然后在它们外层包一个带EPS比较的版本。这个习惯救过我好几次。因为几何问题的 bug 有个特点它不会在单点测试里暴露而是会在某个特定输入组合下突然炸掉而且往往是在线上环境数据量大、坐标分布杂的时候。举个我遇到过的真实场景某个排版工具需要判断两个矩形贴纸有没有重叠、如果有重叠需要沿边缘切开。最初的实现用的是简单的坐标区间比较矩形轴对齐时完全没问题后来产品要求支持旋转一定角度的贴纸代码立刻失效。改成线段相交判定加凸包相交判定之后才稳下来。这个转变让我彻底明白一件事几何问题不要试图用特例去糊老老实实回到向量运算才是长期方案。1.2 选型时的三个决策点真正动手前我一般会先确认三件事这三件事的选择会直接影响后面所有代码的写法。第一是坐标的量级。你的坐标是做屏幕像素级的0 到几千还是做地理经纬度的小数点后六七位还是做 CAD 那种高精度的。量级决定了EPS该取多少。用 1e-9 去判定像素级坐标等于没判用 1e-2 去判定经纬度精度又全丢了。第二是要不要保留共线点。做凸包的时候多边形的边上如果有三点共线你是把中间那个点踢掉还是保留大部分情况下踢掉更省事但如果这个凸包后面要用来做碰撞的接触点保留反而更好因为接触面可能是一整条边。这个决策要在写第一行代码前定下来不然改起来牵连一大片。第三是用整数还是浮点。如果输入本身就是整数坐标比如网格地图、棋盘、像素图片我强烈建议全程用整数运算只在最后算距离或者面积的时候转浮点。这样叉积的符号判断是绝对精确的一个EPS都不需要。这个技巧能消灭掉至少一半的精度问题。1.3 一个被低估的前置工作统一数据结构我见过太多项目里每个函数自己定义一套点结构Point、Vec2、Vector2D、pt到处都是字段名有的叫x/y有的叫px/py有的叫first/second。写几何代码本来就容易出错再加上类型转换出错的概率指数级上升。我的做法是整个项目只保留一个二维点类型同时提供向量和点的双重语义数学上它们本来就是同构的然后所有几何函数都围绕它展开。C 里就是一个struct加一堆运算符重载Python 里可以用dataclass或者干脆用元组加纯函数。下面是我常用的 Python 版本骨架后面所有代码都基于它from dataclasses import dataclass import math EPS 1e-9 dataclass(frozenTrue) class Pt: x: float y: float def __add__(self, o): return Pt(self.x o.x, self.y o.y) def __sub__(self, o): return Pt(self.x - o.x, self.y - o.y) def __mul__(self, k): return Pt(self.x * k, self.y * k) def sgn(v: float) - int: 带容差的三态符号函数整个库的核心守卫 if v EPS: return 1 if v -EPS: return -1 return 0sgn这个函数看着不起眼但它是我所有几何代码的地基。所有需要判断正负的地方一律调它绝不直接写 0。这样做的好处是精度策略集中在一个地方哪天发现EPS不合适改一个常量就够了不用去翻几百行代码。2. 点积与叉积所有判断的地基2.1 点积在回答什么问题点积的定义很朴素a · b ax*bx ay*by几何意义是|a||b|cosθ。我习惯把它理解成a 在 b 方向上有多少分量也就是投影。这个理解比背公式有用得多。比如你要判断两个向量是不是锐角取点积看正负就够了因为|a||b|恒为正符号完全由cosθ决定。同理钝角是负直角是零。我在项目里点积用得最多的地方是点到直线的最短距离。给定直线上两点 A、B 和任意点 P先算t dot(P-A, B-A) / dot(B-A, B-A)。这个t就是垂足在直线上的参数位置t在 0 到 1 之间说明垂足落在线段内部小于 0 说明离 A 端最近大于 1 说明离 B 端最近。算出t之后把 P 投影过去两点距离就是答案。def point_seg_dist(p: Pt, a: Pt, b: Pt) - float: ab b - a if ab.x 0 and ab.y 0: # 退化成点 return math.hypot(p.x - a.x, p.y - a.y) t ((p.x - a.x) * ab.x (p.y - a.y) * ab.y) / (ab.x*ab.x ab.y*ab.y) t max(0.0, min(1.0, t)) # 关键钳制到线段范围内 proj Pt(a.x ab.x * t, a.y ab.y * t) return math.hypot(p.x - proj.x, p.y - proj.y)这里那个max/min钳制是整个函数最有价值的一行。很多人写点到直线距离很顺一到点到线段距离就翻车原因就是忘了钳制。不钳制的话垂足跑到线段延长线上去了算出来的是点到直线的距离不是到线段的距离。这个 bug 在碰撞检测里尤其致命——玩家明明离墙还有一段距离系统判定你已经贴上了。注意钳制之后t的精度损失会累积如果你要做的是点是否在线段上这种判定不要用距离阈值用叉积判共线加坐标区间判精度高得多。2.2 叉积的符号比大小更重要叉积是二维里的伪标量a × b ax*by - ay*bx几何意义是|a||b|sinθ同时它的绝对值等于以 a、b 为邻边的平行四边形面积。我在代码里 90% 的叉积调用只关心符号不关心数值。符号告诉你的信息量非常大cross(b-a, c-a)为正说明 c 在向量 ab 的左侧为负说明在右侧为零说明三点共线。就这么一句话撑起了后面线段相交和凸包的全部逻辑。为什么是左侧想象你站在 a 点面朝 b 点c 在你的左手边那就是正。这个直觉在调试的时候特别好用你可以直接在纸上画一画验证代码算出来的符号对不对不用去推导。叉积的另一个高频用法是算三角形面积S |cross(b-a, c-a)| / 2。由此可以扩展到任意多边形这就是第 5 节要讲的鞋带公式。顺带提一句叉积还能判断多边形的顶点是顺时针还是逆时针排列把相邻边两两叉积加起来看总符号为正就是逆时针为负就是顺时针。这个判断在渲染和填充的时候必须先做不然填充区域会跑到外面去。2.3 EPS 到底该取多少这个问题我被问过很多次也踩过不少坑。先说结论没有一个放之四海皆准的值得看坐标量级和运算次数。一个比较可靠的估算方式是如果你的坐标量级是M比如最大坐标是 1e6双精度浮点的相对误差约 1e-16那么单次叉积运算的绝对误差上限大概是M * M * 1e-16。当M 1e6时误差上限就是 1e-4这时候你取EPS 1e-9完全没意义因为误差本身就比它大三个数量级。所以我一般在库里提供一个按量级自适应的 EPSdef eps_for(pts) - float: scale max(max(abs(p.x), abs(p.y)) for p in pts) return max(1e-12, scale * scale * 1e-12)这个策略偏保守但比我见过的直接写死 1e-9 要稳得多。当然如果你的坐标是整数或者量级很小比如像素级完全可以直接取 1e-9甚至用整数运算彻底绕开。还有一个技巧是比较前先做归一化。判断两个叉积结果是否相等时不要比绝对值而是把两个叉积都除以参与的向量长度比较正弦值是否相等。这样结果是无量纲的不受坐标量级影响。这个做法在判断角度关系时特别好用。3. 线段相交判定跨立实验的完整推导3.1 跨立实验的核心思想线段 AB 和线段 CD 相交本质上要求两件事同时成立C 和 D 分居直线 AB 的两侧并且 A 和 B 分居直线 CD 的两侧。这就是所谓的跨立。用叉积表达极其简洁。d1 cross(B-A, C-A)d2 cross(B-A, D-A)如果d1 * d2 0说明符号相反C、D 在 AB 两侧。同理算d3 cross(D-C, A-C)、d4 cross(D-C, B-C)如果d3 * d4 0A、B 在 CD 两侧。两个条件都满足就是严格相交。但这里有个陷阱直接乘d1 * d2可能会溢出。如果坐标量级大两个叉积都是 1e200 这个级别乘起来就 inf 了符号判断直接失效。稳妥的写法是比较符号def straddle(a: Pt, b: Pt, c: Pt, d: Pt) - bool: d1 cross(a, b, c) d2 cross(a, b, d) d3 cross(c, d, a) d4 cross(c, d, b) return (sgn(d1) * sgn(d2) 0) and (sgn(d3) * sgn(d4) 0)sgn返回值只有 -1、0、1乘起来绝对安全。3.2 四种退化情形必须分开处理严格相交只覆盖了两条线段在内部某点交叉这一种情况。真实数据里至少还有四种变体情形几何特征判定条件端点接触一个端点落在另一条线段内部叉积为 0 且点在段内端点重合两条线段共用端点坐标相等共线分离四点共线但区间不重叠坐标区间不交共线重叠四点共线且有公共部分坐标区间相交这四种情况如果不处理你的相交判定会在两条线段首尾相接时返回 false然后整条路径的连通性判断就断了。我做地图路径规划的时候就被这个坑过一次两条道路在路口共用角点结果判定不连通绕了一大圈才排查到。完整的实现我一般写成这样def cross(a: Pt, b: Pt, c: Pt) - float: return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) def on_seg(a: Pt, b: Pt, p: Pt) - bool: 前提p 与 a、b 共线判断 p 是否落在线段 ab 上 return (min(a.x, b.x) - EPS p.x max(a.x, b.x) EPS and min(a.y, b.y) - EPS p.y max(a.y, b.y) EPS) def seg_intersect(a: Pt, b: Pt, c: Pt, d: Pt) - bool: d1 sgn(cross(a, b, c)) d2 sgn(cross(a, b, d)) d3 sgn(cross(c, d, a)) d4 sgn(cross(c, d, b)) # 严格跨立 if d1 * d2 0 and d3 * d4 0: return True # 退化端点落在对方线段上 if d1 0 and on_seg(a, b, c): return True if d2 0 and on_seg(a, b, d): return True if d3 0 and on_seg(c, d, a): return True if d4 0 and on_seg(c, d, b): return True return False这个版本我用了好几年只要EPS选得合理基本没出过问题。3.3 快速排斥实验要不要加很多教材会先做一步快速排斥如果两条线段的外接矩形都不重叠那肯定不相交直接返回 false省掉后面的叉积计算。要不要加取决于你的数据。如果大部分线段对都是远离的比如空间索引的初步筛选这个剪枝能带来 3 到 5 倍的提速。但如果你的数据本来就密集大部分线段对都靠得很近那这步剪枝的命中率很低反而多了一堆比较开销。我实测下来的经验是在暴力两两判定的场景n 小于 2000加上它在已经有空间索引网格、四叉树的场景不要加。因为索引已经把大部分无关的过滤掉了剩下的候选本来就大概率相交排斥实验几乎不生效。注意快速排斥必须用带容差的比较max(a.x, b.x) min(c.x, d.x) - EPS这样写不能直接用。否则刚好贴边的情况会被误判成不相交又是一类难查的 bug。3.4 一组必要的测试用例写完相交判定我强烈建议先跑一遍下面这些用例。它们覆盖了我这些年遇到过的全部退化情形能过这组测试基本就不会有大问题了。tests [ ((0,0),(2,2),(0,2),(2,0), True), # 标准交叉 ((0,0),(2,0),(3,0),(5,0), False), # 共线分离 ((0,0),(4,0),(2,0),(6,0), True), # 共线重叠 ((0,0),(2,0),(2,0),(4,0), True), # 端点重合 ((0,0),(4,0),(2,0),(2,2), True), # T 型接触 ((0,0),(1,0),(2,0),(3,0), False), # 首尾相接但之间有缝 ((0,0),(1,1),(2,2),(3,3), True), # 完全共线重叠 ((0,0),(1,0),(0,1),(1,1), False), # 平行不相交 ]这组用例里我最想强调后三个。平行不相交看着简单但因为d1 d2 0如果没有处理好会走到端点落在线段上的分支里误判成相交。测试跑通了再谈优化。4. 凸包从朴素解到单调链4.1 为什么最终都收敛到单调链凸包的朴素算法是 O(n³)枚举每一对点组成的直线判断所有其他点是不是都在同一侧。n 到了一千就卡得跑不动了。中间层的方案是 Graham 扫描O(n log n)核心是按极角排序之后用栈维护拐向。这个算法我实现过三次每次都卡在同一个地方极角排序的基准点怎么选、共线点怎么处理、精度不够时排序不稳定怎么办。特别是极角排序要用atan2的时候浮点误差会让两个本该相邻的点顺序颠倒然后整个栈就崩了。现在我一律用Andrew 单调链。它只按坐标排序(x, y)字典序完全不涉及角度和三角函数精度天然稳健。思路也直观把点排序之后从左到右扫一遍构建下凸包再从右到左扫一遍构建上凸包拼起来就是完整的凸包。def convex_hull(points): pts sorted(set(points)) # 排序 去重 if len(pts) 2: return pts def build(seq): stack [] for p in seq: while len(stack) 2 and sgn(cross(stack[-2], stack[-1], p)) 0: stack.pop() stack.append(p) return stack lower build(pts) upper build(reversed(pts)) return lower[:-1] upper[:-1]这十几行代码能处理绝大多数情况我把它抄在笔记里用了很多年。4.2 那个和的差别决定成败上面代码里最关键的是那个sgn(...) 0。这个符号决定了共线点怎么处理用 0遇到共线就弹出最终凸包只保留极端顶点边上的中间点被删掉。用 0只弹出右转的点共线点保留在栈里。选哪个完全取决于你的下流需求。如果凸包后面要算面积、做包含判定用 0更干净顶点数最少。如果凸包要做碰撞接触面、要做贴边吸附必须用 0保留共线点否则一条直线边会被压缩成两个端点中间的接触点全丢了。我第一次做贴边吸附的时候就是用了 0结果物体贴着斜坡滑动时抖得厉害因为斜面上的接触点一直在跳。改成 0之后立刻就稳了。这个教训挺深的凸包的算法细节和业务语义是绑定的不能闭着眼睛抄。提示lower[:-1] upper[:-1]这个写法是为了避免首尾两个点重复出现。如果你用的是 0版本并且输入里有共线点这句需要额外检查一下重复用dict.fromkeys去个重更保险。4.3 单调链的手工推演算法光看代码容易懵我拿一个具体例子走一遍。假设点集是(0,0), (1,1), (2,0), (3,1), (4,0), (2,-1)排序后是(0,0), (1,1), (2,-1), (2,0), (3,1), (4,0)。构建下凸包时依次处理压入(0,0)、(1,1)来(2,-1)cross((0,0),(1,1),(2,-1)) 1*(-1) - 1*2 -3负右转保留。栈变(0,0),(1,1),(2,-1)来(2,0)cross((1,1),(2,-1),(2,0)) 1*0 - (-2)*1 2正左转弹出(2,-1)。再检查cross((0,0),(1,1),(2,0)) 0用 0会弹出(1,1)。栈变(0,0),(2,0)来(3,1)cross((0,0),(2,0),(3,1)) 2*1 - 0 2正保留。栈(0,0),(2,0),(3,1)来(4,0)cross((2,0),(3,1),(4,0)) 1*0 - 1*2 -2负保留。栈(0,0),(2,0),(3,1),(4,0)下凸包完成。上凸包反向扫一遍最后拼起来。手工推一遍之后这个算法在我脑子里就再也没忘过比看十遍代码都管用。建议每个人至少手推一次。4.4 凸包的几个实用扩展凸包本身不难难的是它衍生出来的一堆需求。我按使用频率排一下。点到凸包的距离。如果是判断点在凸包外有多远用二分找最近边。如果是点在内距离为 0。我一般偷懒直接用凸包的每条边跑一遍point_seg_dist取最小值O(h) 的复杂度h 是凸包顶点数通常很小实际够用。凸包包含判定。除了暴力叉积还有 O(log h) 的二分法以凸包第一个顶点为原点按极角二分找到点落在哪个三角形扇区里再判一次叉积。点数上千的时候这个优化才有意义否则直接暴力更快。动态凸包。如果点集一直在增删单调链就不好用了。这时候要么用垂直分解的树结构要么用可以维护上下凸包的平衡树。我做过一版代码量比静态版本大五倍除非真有性能瓶颈否则不建议上。5. 多边形面积鞋带公式及其边界5.1 鞋带公式的推导与符号含义鞋带公式的名字很形象因为它算的时候像是在系鞋带交叉相乘再相减。Area 0.5 * |Σ(x_i * y_{i1} - x_{i1} * y_i)|注意下标是绕圈的最后一个点和第一个点也要算一次。推导思路很简单把多边形从一个原点出发切成若干个三角形每个三角形的有向面积用叉积算加起来。由于内部有向面积会互相抵消最终剩下的正好是多边形面积。def polygon_area(poly) - float: n len(poly) s 0.0 for i in range(n): x1, y1 poly[i].x, poly[i].y x2, y2 poly[(i 1) % n].x, poly[(i 1) % n].y s x1 * y2 - x2 * y1 return abs(s) * 0.5这里我特意保留了abs之外的符号信息因为符号本身有语义正值表示逆时针负值表示顺时针。这个符号在判断多边形朝向时非常有用比单独写一个遍历叉积的函数要快。5.2 别急着取绝对值我见过不少代码上来就abs把符号丢了。然后下游要判断顶点顺序的时候又得重新扫一遍所有边算叉积和。其实鞋带公式已经算出来了白扔。我的习惯是写一个signed_area返回带符号的值再包一个polygon_area返回绝对值。朝向判断直接看signed_area 0。代码里少一次遍历也就少一次出错机会。def signed_area(poly) - float: n len(poly) return sum(poly[i].x * poly[(i1) % n].y - poly[(i1) % n].x * poly[i].y for i in range(n)) * 0.5另外坐标原点离多边形很远的时候鞋带公式会有精度损失因为每个叉积都很大互相抵消之后剩一个小数有效位就丢了。稳妥做法是先把所有点平移到以第一个点为原点的坐标系再算def signed_area_stable(poly) - float: ox, oy poly[0].x, poly[0].y n len(poly) s 0.0 for i in range(1, n - 1): ax, ay poly[i].x - ox, poly[i].y - oy bx, by poly[i1].x - ox, poly[i1].y - oy s ax * by - bx * ay return s * 0.5这个版本实际上是在做三角形扇形求和数值稳定性明显好于直接套鞋带公式尤其是在坐标量级 1e6 以上、多边形面积又不大的情况下差别很明显。我现在默认用这个版本。5.3 自交多边形与凹多边形怎么处理鞋带公式对凹多边形完全正确这一点很多人有误解。凹多边形的某些三角形有向面积是负的正好抵消掉多出来的部分最终结果依然准确。真正有问题的是自交多边形。比如画一个8字鞋带公式算出来的结果是两瓣面积的差不是和。这时候的面积怎么定义要看业务你是想做布尔运算求并集还是想求绝对覆盖面积。这两种需求对应的算法完全不同前者需要先做多边形求交后者需要把多边形拆成若干简单多边形。我做排版工具的时候就遇到过这个用户能随手乱画画出来的图形经常自交。最后的处理方案是先用扫描线把多边形拆成若干个单调多边形再分别算面积求和。这一步的实现量不小如果不是必须支持任意手绘输入我建议在交互层就限制住比如只允许拖拽出凸多边形。5.4 面积相关的几个延伸计算鞋带公式还能顺手带出几个常用量。形心重心。多边形的形心不是顶点的平均值那个只对三角形成立。正确做法是用带符号面积加权def centroid(poly): a signed_area(poly) if abs(a) EPS: return Pt(sum(p.x for p in poly)/len(poly), sum(p.y for p in poly)/len(poly)) cx cy 0.0 n len(poly) for i in range(n): p, q poly[i], poly[(i1) % n] f p.x * q.y - q.x * p.y cx (p.x q.x) * f cy (p.y q.y) * f return Pt(cx / (6 * a), cy / (6 * a))这个公式我用得很多做标签居中、做拖拽锚点都要它。注意面积接近 0 的时候要兜底否则除零。多边形周长。简单遍历相邻边求距离累加。但我提一个容易忽略的点如果首尾两点重复很多数据格式里多边形首尾是闭合的累加时会多算一段长度为 0 的边不影响结果但会多一次 sqrt。养成在入口处检查并去掉重复末点的习惯。6. 常见问题与排查实录6.1 精度问题速查表这类问题占了我在几何代码上花的时间的一大半。整理成表方便对照。现象可能原因排查手段处理方案交点算成 NaN两直线平行导致除零打印叉积分母先判平行再求交明明相交判 falseEPS 太小误差淹没打印四个叉积值按量级放大 EPS明明不相交判 true共线分支误命中检查sgn返回值修正on_seg区间凸包顶点顺序乱排序不稳定打印排序后的点列用元组字典序排序面积偶尔负顶点顺序不一致检查signed_area符号统一成逆时针输入大面积算偏小抵消误差平移原点重算用扇形求和版本我最想强调第二行和第三行。这两个现象看起来矛盾实际上经常同时存在于一个项目里一部分数据 EPS 太小漏判另一部分数据 EPS 太大误判。这时候不要盲目调 EPS正确做法是把四种退化情形分别写测试用例逐个确认找到真正出问题的那一条分支。6.2 性能排查的两个方向几何代码慢绝大多数情况不是算法复杂度问题而是两个细节没做好。第一个是开方次数。距离比较里频繁用hypot或sqrt其实比较距离大小的时候完全可以比平方距离省掉开方。我在一个 10 万点的最近点对检测里把开方去掉之后耗时从 1.2 秒降到 0.3 秒。这个优化几乎零成本只要注意别把平方距离当真距离传给下游就行。第二个是重复计算。向量减法在循环里被反复算比如b - a在四条边里各算一次。把它提到循环外面存变量性能能提升 20% 以上。这个在凸包构建里尤其明显因为栈操作会反复访问相邻两个点。至于空间索引我的经验是点数到 5000 以上再考虑上网格或四叉树。低于这个量级建索引的开销比重都超过收益。我做过一次对比测试2000 个点的暴力凸包是 3 毫秒加索引反而要 5 毫秒。数据量小的时候简单方案永远是对的。6.3 我在实际项目里踩过的坑挑几个印象深的说说。坑一整数坐标混用浮点 EPS。有一次做像素级的地图标注坐标全是整数但我图省事用了浮点版本加 1e-9 的 EPS。结果两条像素级线段共线判定频繁出错。原因是整数转浮点本身是精确的但叉积算完之后有些值恰好是 1 附近sgn判断没问题问题出在后面的向量缩放上引入了误差。后来改成全程整数运算一条 EPS 都不需要问题消失。坑二顺时针多边形输入传给期望逆时针的函数。这个错误我犯过不止一次。鞋带公式对两种顺序都能算出正确的面积绝对值但形心公式会算出一个完全相反的坐标凸包的单调链会构建出错误结果。现在我在所有接受多边形的函数入口都加了一句朝向检查不一致就自动翻转顶点顺序。这个防御性编程省了我很多调试时间。坑三abs用在了该保留符号的地方。上面提过但值得再强调。判断点在多边形内还是外、判断多边形是否自交都需要原始符号信息。养成先 signed 后 abs的习惯。坑四重合点没有去重。输入数据里偶尔有连续重复的顶点通常来自数据转换凸包算法会因此产生零长度的边然后叉积算出来全是 0判断全落在共线分支里输出结果看着对但顶点全是脏数据。在convex_hull入口加一个set去重就解决了。心得几何代码的稳健性不来自聪明的算法来自对输入数据的怀疑。我现在写任何一个几何函数第一件事是把所有退化输入列一遍空集、单点、两点、全共线、全重合、坐标超大量级。把这些都覆盖了剩下的常规情况基本不会出问题。7. 把这几个模块拼成一个可用的几何库单独的四个函数不难写难的是它们一起工作的时候不出岔子。我现在的做法是配一套统一的约定整个库内部严格遵守。第一条约定所有函数输入的多边形统一为逆时针。入口处用signed_area检查逆时针直接过顺时针就reversed一下。这一条消灭了我在朝向问题上 90% 的 bug。第二条约定所有返回多个点的函数都保证顶点不重复包括首尾不重复。凸包函数返回的第一个点和最后一个点不相等多边形函数不做自动闭合。这条约定让下游代码少一层判断。第三条约定所有容差比较走统一的sgn。禁止在任何几何判断里直接写裸的比较运算符。这是纪律问题违反一次就可能埋一个三个月后爆发的雷。按这三条约定写出来的库代码量其实不大一个文件两三百行但用起来非常省心。我现在新开项目直接把这套东西复制过去改改类型声明就能用。最后分享一个小技巧关于几何 bug 的定位。这类 bug 最难的地方是难以可视化你看到一堆数字不知道哪里错了。我的办法是写一个异步的小工具把出问题的输入点列画成 SVG。不用装任何图形库直接拼字符串在浏览器里打开就行def dump_svg(polys, w800, h600, scale40, pad20): def tx(p): return (p.x * scale pad, h - (p.y * scale pad)) out [fsvg xmlnshttp://www.w3.org/2000/svg width{w} height{h} stylebackground:#fff] colors [#e63946, #457b9d, #2a9d8f, #e9c46a] for i, poly in enumerate(polys): pts .join(f{tx(p)[0]:.2f},{tx(p)[1]:.2f} for p in poly) out.append(fpolyline points{pts} fillnone stroke{colors[i%4]} stroke-width1.5/) for p in poly: x, y tx(p) out.append(fcircle cx{x:.2f} cy{y:.2f} r2.5 fill#333/) out.append(/svg) return \n.join(out)把所有参与计算的原始点和结果多边形丢进去一眼就能看出是哪一步算歪了。这个方法帮我在半小时内定位过好几个此前查了大半天的问题比打日志猜数字高效太多。你可以在里面加标注文字、加点序号反正就是拼字符串想怎么改都行。实际动手的时候我还是建议按这个顺序推进先把点积叉积和sgn写稳用几十组手算的用例验证再上线段相交把四种退化情形全测一遍然后凸包记得手推一遍单调链最后多边形面积顺手把形心和朝向判断带出来。每一步都验证过再往下走比一口气写完再统一调试要快得多。
