凸包算法的四个退化输入：共线、重复点、单点和空集

凸包算法的正常路径很短：把点按 x 排序，从左到右扫一遍下凸壳，从右到左扫一遍上凸壳，遇到不该拐弯的点就弹栈。真正让实现分叉的，是那些「不太像点集」的输入：重复点、三点共线、所有点都在一条线上、只有一个点、一个点都没有。

这些输入不处理，代码在演示页上可能照样能跑，但下游会开始出问题：凸包顶点数虚高、三角形面积和对不上、欧拉关系检查失败，最后表现为一个很难定位的几何错误。下面按四类退化输入拆开讲，顺序按它们在代码里被处理的先后。

主循环长什么样

先把正常路径摆出来。点集去重后，按 x 再按 y 排序：

const order = pts.map((_, i) => i).sort((a, b) =>
  pts[a].x - pts[b].x || pts[a].y - pts[b].y);

const lower = [];
for (const i of order) {
  while (lower.length >= 2 &&
         cross(pts[lower[lower.length - 2]], pts[lower[lower.length - 1]], pts[i]) <= 0) {
    lower.pop();
  }
  lower.push(i);
}

上凸壳反向再扫一遍，最后两个栈各弹掉一个端点，拼起来就是逆时针的凸包。

关键在那个 <= 0。cross 返回三个点的有向面积两倍：正值表示左转，负值表示右转，零表示三点共线。用 <= 0 弹栈，等于要求每个拐点都必须是严格左转，共线的中间点会被一并弹掉。这不是顺手写的边界条件，而是「凸包顶点」的定义决定的：一条直边上的中间点不改变外边界，不应该出现在顶点列表里。

第一类：重复点

重复点最容易被忽略，因为它在视觉上完全看不出来。两个坐标完全相同的点，排序后相邻，cross 算出来是 0，主循环有时会把其中一个弹掉，看起来「自动处理了」。但弹栈不是去重机制：一个重复点会不会被弹掉，取决于它落在凸包上还是内部、以及相邻点的顺序，不能把去重寄托在它身上。去重必须是入口的独立步骤，凸包和剖分两个入口都先做一次：

function dedupe(points) {
  const seen = new Set(), pts = [], orig = [];
  for (let i = 0; i < points.length; i++) {
    const p = points[i];
    const key = p.x + '|' + p.y;
    if (seen.has(key)) continue;
    seen.add(key);
    pts.push({ x: p.x, y: p.y });
    orig.push(i);
  }
  return { pts, orig, dropped: points.length - pts.length };
}

这里用的是精确相等，不是「距离小于某个 epsilon 就算重复」。原因很实际：去重发生在算法入口，此时还没有坐标跨度，也就没有一个合理的尺度去定 epsilon；如果按固定绝对距离去重，坐标整体放大一千倍后，这个阈值就失去了意义。精确相等至少语义明确：同一个坐标只保留第一次出现。真要合并近邻点，那是另一个问题，应该由调用方先做，并且明确容差和合并规则。

保留 orig 是为了把去重后的下标映射回原始输入：导出算例、和外部实现对拍、或者把结果对应回用户原始数据时，都需要知道「第 i 个去重点对应原数组的哪一项」。dropped 则直接显示在指标面板里，让「输入 24 个点，去重后 23 个」这件事可见，而不是悄悄发生。

第二类：共线中间点

共线中间点分两种情形，处理方式完全不同。

第一种是「凸包边上的共线点」。比如正方形四条边的中点。它们不是拐点，不应该进凸包顶点列表，但仍然属于输入点集，三角剖分需要把它们插进去，否则「每个点都被覆盖」的检查会失败。所以凸包只返回拐点，这些点留在 pts 里，由剖分阶段处理。

第二种是「所有点都共线」。这时候没有拐点，凸包退化成一条线段。代码在进入主循环之前就判断：

if (allCollinear(pts)) {
  let i0 = 0, i1 = 0;
  for (let i = 1; i < pts.length; i++) {
    if (pts[i].x < pts[i0].x || (pts[i].x === pts[i0].x && pts[i].y < pts[i0].y)) i0 = i;
    if (pts[i].x > pts[i1].x || (pts[i].x === pts[i1].x && pts[i].y > pts[i1].y)) i1 = i;
  }
  out.hullIndices = i0 === i1 ? [i0] : [i0, i1];
  out.hullPoints = out.hullIndices.map(i => pts[i]);
  out.degenerate = true; out.collinear = true;
  out.perimeter = out.hullPoints.length === 2 ? dist(out.hullPoints[0], out.hullPoints[1]) : 0;
  out.inside = pts.length - out.hullPoints.length;
  return out;
}

这里有两个选择值得说清楚。

第一，全共线时返回两个端点，而不是抛错。抛错看起来更「严格」，但会把调用方逼进一个尴尬的位置：演示页只是想画一条线，剖分只是想知道「没有三角形」，两者都不需要异常。返回 degenerate: true、collinear: true、面积 0、周长等于两端距离，调用方可以正常渲染，也可以根据标记跳过后续步骤。异常应该留给「调用方无法继续」的情况，而不是「几何结构退化」这种情况。

第二，判断共线本身也需要容差。代码用的是：

if (Math.abs(cross(a, b, pts[i])) > 1e-9 * (1 + dist2(a, b))) return false;

cross 的量纲是长度平方，dist2(a, b) 也是长度平方，两者可以直接比。乘上 1 + 是为了在两点几乎重合、dist2 趋近于 0 时，右边仍保留 1e-9 的绝对下限；否则容差会随距离一起压到 0，任何微小的叉积都会被判成不共线。这个容差不是为了把「几乎共线」硬判成共线，而是为了不让浮点舍入把一条精确的直线判成不共线。

第三类：单点

单点没有几何结构可言，但它是 UI 的合法状态：用户只点了一个点，或者拖动时暂时把点删到只剩一个。代码里的处理是：

if (pts.length === 1) {
  out.hullIndices = [0]; out.hullPoints = [pts[0]]; out.degenerate = true;
  return out;
}

不抛错，返回一个带 degenerate 标记的结构。上层拿到 hullPoints.length === 1，画一个点、跳过填充、跳过三角剖分即可。

第四类：空集

空集更彻底：没有点，也就没有凸包。代码只做一件事：

if (pts.length === 0) { out.degenerate = true; return out; }

返回空结构，hullPoints.length === 0。上层不需要为「画布被清空」写一个单独的异常分支，按退化状态处理即可。

剖分函数也做了同样的判断：少于 3 个点返回 degenerate: '点数不足 3'，全共线返回 degenerate: '全部共线'。

这类「返回退化标记」的写法有一个额外好处：它让退化状态可以被断言。测试里可以直接写：

ok('剖分：全共线 → 退化且不抛错',
  d.degenerate === '全部共线' && d.triangles.length === 0);
ok('剖分：两点 → 退化',
  C.delaunay([P(0, 0), P(1, 1)]).degenerate === '点数不足 3');

如果函数在退化时抛异常，测试就只能写 try/catch，而且很难区分「预期内的退化」和「真的写错了」。

一个容易误解的计数口径

凸包结果里有一个 inside 字段：

out.inside = pts.length - out.hullIndices.length;

名字叫「内部点数」，但它实际统计的是「不是凸包拐点的点数」。如果有一个点恰好落在凸包边的中间，它会被算进 inside，尽管它并不在凸包严格内部。这个口径是有意选的：凸包顶点列表只保留拐点，所以「非顶点」自然包括内部点和边界上的共线点。如果业务需要区分「严格内部」和「边界非拐点」，得另外做点在多边形边界上的判定，不能靠这个字段。

这也是为什么演示页的指标面板写的是「内部点数」，而不是「严格内部点数」。名字可以简化，口径必须在代码和文档里说清楚，否则下一个读代码的人会把边界点当成内部点。

这些分支怎么被固定住

凸包相关的断言有 12 条，覆盖的正是上面四类输入：

• 正方形四个顶点全保留，面积 10000，周长 400，逆时针；
• 边中点和内部点被剔除，剔除后凸包仍是 4 个顶点、面积仍是 10000；
• 全共线四个点退化成两个端点，面积 0；
• 单点返回 1 个顶点；
• 空输入不抛错；
• 重复点去重后剩 3 个顶点；
• 正圆上 12 个点全部保留为凸包顶点。

这些数字都不大，但每一条都对应一个具体的分支。断言的价值不在于「证明算法对」，而在于把「退化时应该发生什么」从口头约定变成可执行的检查。以后改主循环、改容差、改去重策略，只要这 12 条还过，至少这四类输入的行为没有被悄悄改掉。

写凸包时可以先问的四个问题

1. 输入里有重复点吗？去重放在算法入口还是调用方？去重后的下标还能映射回原输入吗？
2. 共线的中间点要保留还是剔除？如果剔除，下游是否知道这些点仍然需要被剖分覆盖？
3. 全共线时返回什么？抛错、返回空、还是返回两个端点加退化标记？调用方能不能在不写特殊分支的情况下继续？
4. 单点和空集是合法状态还是错误？如果是合法状态，返回结构里的哪个字段能让上层区分「空」和「只有一个点」？

这四个问题都不涉及主循环，却决定了这个凸包实现能不能被安全地嵌进一条更长的流水线。主循环写对只是开始，退化路径写清楚，才算真正可用。

（完）