内接圆判定

形式陈述 ​

给定平面点

$$a=(a_x,a_y),b=(b_x,b_y),c=(c_x,c_y),d=(d_x,d_y),$$

定义

$$\mathrm{InCircle}(a,b,c,d)=\det \left(\begin{array}{cccc}{a}_x& a_y& a_x^2+a_y^2& 1\\ b_x& b_y& b_x^2+b_y^2& 1\\ c_x& c_y& c_x^2+c_y^2& 1\\ d_x& d_y& d_x^2+d_y^2& 1\end{array}\right).$$

若 $a,b,c$ 逆时针且不共线，则：

• 行列式 $>0$：$d$ 在三点外接圆内；
• 行列式 $=0$：四点共圆；
• 行列式 $<0$：$d$ 在圆外。

若 $a,b,c$ 顺时针，符号整体反转。因此实际接口应先核对 $\mathrm{orient}(a,b,c)$，或返回二者符号乘积

$$\mathrm{sign}(\mathrm{orient}(a,b,c))\mathrm{sign}(\mathrm{InCircle}(a,b,c,d)).$$

把坐标先平移到 $d$ 可得到数值更紧凑的 $3\times 3$ 行列式，但判定完全相同。

直觉 ​

提升映射

$$(x,y)\mapsto (x,y,x^2+y^2)$$

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

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

例子与边界 ​

取

$$a=(0,0),b=(1,0),c=(0,1).$$

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

浮点直接求行列式在近共圆输入上可能因消去误判符号。几何算法需要的是谓词符号，而不是近似行列式数值；可使用整数扩展精度、自适应精确算术或 symbolic perturbation。四点共圆时 Delaunay 对角线不唯一，算法必须规定一致的退化处理。

推论与应用 ​

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

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

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

参考资料

• Jonathan Richard Shewchuk, “Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates,” Discrete & Computational Geometry 18, 1997.
• Mark de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008, Chapter 9.
• Steven Fortune, “Numerical Stability of Algorithms for 2D Delaunay Triangulations,” International Journal of Computational Geometry & Applications 5(1–2), 1995.