方向判定

把 $a$ 当作原点，向量 $b-a$ 旋转到 $c-a$ 的方向就是三点转向；二维叉积或行列式给出带符号面积，据其符号判断左转、右转或共线。该判定不依赖坐标原点，但方向符号还依赖已选坐标的定向。对仿射变换 $F(x)=Lx+t$，有 $\mathrm{orient}(Fa,Fb,Fc)=\det \left(L\right)\mathrm{orient}(a,b,c)$；正行列式保号，负行列式翻号，奇异变换还可能把非零方向压成零。在几何算法中，许多“图形关系”最终都被还原为这一稳定谓词。符号正确比近似数值大小更重要，因为一个错误转向会改变凸包、相交或多边形拓扑。

$(0,0),(1,0),(0,1)$ 的值为 $1$，故左转；交换后两点符号反转。凸包算法用它弹出造成错误转向的栈顶点。整数坐标时可用足够宽的整数计算，但乘法仍可能溢出；固定 epsilon 不能在所有尺度下可靠区分零与非零。

对 $a=(0,0),b=(1,0),c=(1,1)$，行列式

故 $a\to b\to c$ 为逆时针左转；把 $c$ 换成 $(1,-1)$ 得负值，三点 $(0,0),(1,1),(2,2)$ 得零。

共线只说明落在同一直线上，不说明 $c$ 位于线段 $ab$ 内，还需坐标范围判断。大整数乘法可能溢出；浮点行列式在近共线输入上会由两个接近的乘积相减，消去误差公理库消去误差与稳定重写Cancellation and stable reformulation · Catastrophic cancellation解释相近量相减为何会放大已有误差，并用等价公式、缩放和专用函数改造有限精度计算路径。可能翻转本应可靠的符号。固定 epsilon 又不随坐标尺度变化，因此不能统一代表“足够接近零”；实现仍应按输入范围扩大整数类型，或采用精确、可自适应提高精度的符号判定。

例如 $a=(0,0),b=(M,M-1),c=(M+1,M)$，精确行列式为 $M^2-(M-1)(M+1)=1$。两项各有约 $M^2$ 的大小，结果却只剩 $1$；坐标很大时，普通浮点乘积可能舍入成相同数。自适应精确谓词公理库精确几何计算Exact geometric computation · EGC让组合控制流由数学上正确的几何谓词符号驱动，并把近似构造与精确判定分离。先用快速近似和已证明的误差界检查符号是否可信，只有无法确定时才增加精度；它不会把“近似算出零”直接认定为共线。

若整数坐标满足各分量绝对值不超过 $M$，差值绝对值至多 $2M$，两个乘积绝对值各至多 $4M^2$，因而 $8M^2$ 是行列式绝对值的一个安全粗界。类型选择还须覆盖差值及乘法中间结果，不能只检查最终返回类型。

内接圆判定公理库内接圆判定In-circle test · Incircle predicate · In-sphere predicate in 2D用带方向的行列式判定一点位于三点外接圆内、圆上还是圆外。把三点方向与第四点相对外接圆的位置结合起来；二者常共同作为 Delaunay 构造的鲁棒几何谓词，但不能互相替代。

行列式公理库行列式Determinant交换含幺环上方阵的交替多线性标量不变量。给出代数公式，仿射空间公理库仿射空间Affine space忘去原点但保留向量平移作用和仿射组合的空间。解释平移不变性。方向符号驱动凸包公理库凸包Convex hull包含给定点集的最小凸集，是凸几何中的基本包络对象，并可进一步研究其算法构造。与扫描线中的线段次序；点在多边形内判定公理库点在多边形内判定Point in polygon · Point-in-polygon test先识别边界，再以射线横截奇偶或绕数把查询点分类为简单多边形内部、外部或边界。用它识别边界和横截。Delaunay 三角剖分公理库Delaunay 三角剖分Delaunay triangulation以空外接圆条件或 Voronoi 邻接刻画有限平面点集的几何三角剖分。还要把 orientation 与 in-circle 谓词的符号约定配套，否则同一退化点集可能得到不一致拓扑。

随机增量构造公理库随机增量构造randomized incremental construction · RIC按随机排列插入对象，以冲突关系和反向分析控制几何结构的期望构建成本。会按随机顺序插入几何对象，并用这些精确谓词维护冲突关系；其期望复杂度来自排列随机性，不能由单次 orientation 的常数算术成本直接推出。若坐标是有界整数且中间乘积装得下机器字，符号判定可视为最坏 $O(1)$；任意精度整数或自适应精度浮点实现则要把位复杂度计入。输出敏感算法还需另报输出规模 $k$，而方向谓词本身没有“输出敏感时间”这一接口。