内接圆判定

提升映射

把平面点送到抛物面。前三点决定的圆对应提升空间中的一个平面；第四点位于圆内还是圆外，转化为其提升点位于该平面的哪一侧。行列式同时计算这个有向侧别。

这个符号关系也能直接从圆方程核验。设三点外接圆的圆心为 $o$、半径为 $R$。把行列式的第三列减去 $2o_x$ 倍第一列、$2o_y$ 倍第二列，再加 $(\Vert o{\Vert }^2-R^2)$ 倍第四列；前三行的新第三项为零，第四行为 $\Vert d-o{\Vert }^2-R^2$。沿该列展开，得到

这同时说明为什么先平移到 $d$ 不改变结果。

方向条件不能省略：交换 $a,b$ 会改变行列式符号，却不会改变几何圆。只有把圆判定与三角形方向绑定，符号才有固定语义。

取

三点逆时针，其外接圆圆心为 $(1/2,1/2)$。点 $d=(1/2,1/2)$ 在圆内，点 $(1,1)$ 在圆上，而 $(2,2)$ 在圆外，对应行列式正、零、负。

浮点直接求行列式在近共圆输入上可能因消去误判符号。几何算法需要的是谓词符号，而不是近似行列式数值；可用足够宽的整数或自适应精确算术取得原输入的真实符号。若另用 symbolic perturbation，应明确它按一套一致的无穷小扰动规则选择退化结果，而非把原来精确为零的行列式声称为非零。四点共圆时 Delaunay 对角线不唯一，算法必须规定一致的退化处理。

内接圆行列式在四点近共圆时会发生严重消去，符号必须由精确几何计算理路精确几何计算Exact geometric computation · EGC让组合控制流由数学上正确的几何谓词符号驱动，并把近似构造与精确判定分离。或可靠自适应谓词确定。用普通浮点结果的接近零值直接决定 Delaunay 翻边会破坏组合一致性。

Delaunay 三角剖分理路Delaunay 三角剖分Delaunay triangulation以空外接圆条件或 Voronoi 邻接刻画有限平面点集的几何三角剖分。的局部空圆条件用该谓词判断是否翻转一条边。增量构造在定位包含新点的三角形后，反复检查相邻三角形的外接圆。

方向判定理路方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。回答三点位于直线哪一侧；内接圆判定回答第四点相对圆的位置。二者都是鲁棒计算几何的基础谓词，但矩阵维度、几何退化与符号约定不同。

最小包围圆理路最小包围圆Minimum enclosing circle · Smallest enclosing disk · Welzl algorithm · Welzl 最小圆算法用至多三个边界点核验最小圆，并以强制边界的随机递归在期望线性算术时间内构造它。另外解决“哪一个圆能最小地覆盖全部输入”的优化问题：它需要至多三点的凸组合最优证书，并在违反时维护强制边界子问题。钝角三角形的外接圆就可能大于其最小包围圆，所以一个正确的四点内圆谓词并不独自完成该优化。