点在三角形内：三种判法与一个 1e-12 的容差

一、一个点在边上，两个答案

取 A=(0.1, 0.2)、B=(1.3, 0.15)、C=(0.35, 1.7)，点 P=(0.95285536115989089, 0.16446435995167122)。P 是按 A+t(B−A) 生成的，t≈0.7107，按构造落在 AB 上。三次叉积 d1=6.938894e-18、d2=5.243330e-1、d3=1.288167，没有出现一正一负，判为在内。重心坐标 u=0.2892871990334、v=0.7107128009666、w=-1.1102230246251565e-16，w<0，判为在外。

两个实现都没有写错，它们对“边上”的定义不同。这个差异不是 1e-12 的容差问题，而是 1e-16 的舍入残差：P 在浮点里并不精确落在直线上。

二、三种写法与 10 万个点的结果

①三次叉积同号：算出 AB×AP、BC×BP、CA×CP，只要没有“既有正又有负”就算在内，零不算负。退化三角形上，落在同一条直线上的点三值全零，会被判为在内；如果三个顶点重合，则任意点都全零。

②重心坐标闭集：u、v 由叉积比得到，w=1-u-v，三个都 ≥0 才算内。

③同一组重心坐标，但三个都严格 >0，边上不算内。

固定种子 20261031 的线性同余，70% 均匀撒在包围盒，25% 在三条边附近加 ±1e-12 的扰动，5% 正好落在三条边上：

const A=[0.1,0.2], B=[1.3,0.15], C=[0.35,1.7];
const cr=(a,b,p)=>(b[0]-a[0])*(p[1]-a[1])-(b[1]-a[1])*(p[0]-a[0]);
const m1=p=>{const a=cr(A,B,p),b=cr(B,C,p),c=cr(C,A,p);return !(Math.min(a,b,c)<0&&Math.max(a,b,c)>0)};
const bc=p=>{const t=cr(A,B,C),u=cr(p,B,C)/t,v=cr(A,p,C)/t;return [u,v,1-u-v]};
const m2=p=>bc(p).every(x=>x>=0);
const m3=p=>bc(p).every(x=>x>0);

let s=20261031;
const rnd=()=>(s=(Math.imul(1664525,s)+1013904223)>>>0)/2**32;
const E=[[A,B],[B,C],[C,A]];
const T=[[0,0,0,0],[0,0,0,0],[0,0,0,0]];
for(let i=0;i<1e5;i++){
  const r=rnd(); let p;
  if(r<.7) p=[-.2+rnd()*1.8, -.2+rnd()*1.9];
  else{
    const [a,b]=E[rnd()*3|0], t=rnd();
    p=[a[0]+t*(b[0]-a[0]), a[1]+t*(b[1]-a[1])];
    if(r<.95) p=[p[0]+(rnd()*2-1)*1e-12, p[1]+(rnd()*2-1)*1e-12];
  }
  const x=m1(p), y=m2(p), z=m3(p), k=r<.7?0:r<.95?1:2;
  T[k][0]++; T[k][1]+=x!==y; T[k][2]+=x!==z; T[k][3]+=y!==z;
}
console.log(T);

实测：

[ [ 69789, 0, 0, 0 ], [ 25052, 2, 2, 0 ], [ 5159, 2007, 1692, 1031 ] ]

按子集整理：

至少一种结论不同的点有 2367 个。均匀点没有分歧；近边点只有 2 个，且这两个点实际离边只有 1e-16 量级，±1e-12 的随机扰动在法向上几乎抵消了；真正吵起来的是“正好在边上”的 5159 个点，①和②有 2007 个不同。

三、为什么“在边上”没有唯一定义

同样是用两端点线性插值生成、落在边上的点：

• P1=(0.95285536115989089, 0.16446435995167122)，w=-1.1102230246251565e-16，①内、②外、③外。
• P2=(0.31545681328279895, 1.4927408796967938)，v=0，d3=-6.938894e-18，①外、②内、③外。
• P3=(0.11316242860630155, 0.19945156547473744)，w=+1.7347234759768071e-18，①外、②内、③内。

P3 说明“严格大于 0”也不可靠：舍入把 w 推到了正的一侧，边点被并进了内部。三个点都在边上，结论却覆盖了内、外两种，且不是靠调参数能同时修好的。

离边 1e-12 时反而稳定。N=(0.64008795057984513, 1.2266986069506698) 离 BC 约 1e-12，u=-1.046244e-12，v=0.3053557、w=0.6946443，三种写法都判外。噪声在 1e-16，1e-12 已经比噪声高四个数量级，符号是可信的。所以“边上的点算不算内”必须先约定容差；没有容差，同一个点在不同实现里可以有任何答案。

四、带容差的判定函数

const cross3=(a,b,p)=>(b[0]-a[0])*(p[1]-a[1])-(b[1]-a[1])*(p[0]-a[0]);

function locate(p,a,b,c,eps=1e-12){
  const area2=cross3(a,b,c);
  if(!Number.isFinite(area2)||area2===0) return 'degenerate';
  const u=cross3(p,b,c)/area2;
  const v=cross3(a,p,c)/area2;
  const w=1-u-v;
  if(!Number.isFinite(u+v+w)) return 'degenerate';
  if(u<-eps||v<-eps||w<-eps) return 'outside';
  if(u<=eps||v<=eps||w<=eps) return 'edge';
  return 'inside';
}

function epsForWorld(tol,a,b,c){
  const area2=Math.abs(cross3(a,b,c));
  if(!area2) return NaN;
  const d=(p,q)=>Math.hypot(p[0]-q[0],p[1]-q[1]);
  const longest=Math.max(d(a,b),d(b,c),d(c,a));
  return tol*longest/area2;
}

eps 是重心坐标单位，不是世界坐标：它等于“允许离边 eps 个对应边的高”。默认 1e-12，比良态三角形下 u、v 的舍入（约 1e-16）大四个数量级，又远小于常见的几何尺度。若要固定世界容差 t，用 epsForWorld(t,...) 换算：三角形的短高是 |cross|/最长边，所以 eps=t×最长边/|cross|。这个换算保证三条边的判定带都不小于 t；退化时它返回 NaN，交给调用方处理。

退化三角形现在返回 'degenerate'，不再给出“内/外”的结论。边界统一用 <=，同一输入同一结果。拿它重跑 10 万个点：5159 个边点全部归 edge；25052 个近边点中 24376 个 edge、324 个 outside、352 个 inside；69789 个均匀点中 51152 个 outside、18637 个 inside。容差把 1e-16 的噪声收进了“边”，但也把离边 1e-12 以内的点一并算作边——这正是使用前要写清楚的约定。

三角形很扁时，叉积的相对误差会被放大，1e-12 可能低于噪声，此时应放大 eps 或改用精确的朝向谓词。对普通交互式绘图，上面的版本足够；对拓扑判定，先定容差，再谈“内”。

最后把可执行结论压成五条：

1. 先约定「边上的点算不算内」并把它写成常量；同一批点在不同实现下结论不同，不是实现写错，而是缺约定。
2. 判定优先用带容差的 locate()，不要裸用三次叉积同号或裸重心坐标；eps 是重心坐标单位，默认 1e-12 比 1e-16 量级的舍入残差高四个数量级。
3. 要固定世界距离容差 t，用 epsForWorld(t, A, B, C) = t×最长边/|cross| 换算，并确认三条边的判定带都不小于 t。
4. 退化三角形（叉积为 0 或非有限）单独返回 degenerate，不要给出「内/外」结论。
5. 三角形很扁时放大 eps 或改用精确朝向谓词；交互式绘图用默认版本，拓扑判定必须先定容差。

（完）