形式陈述

计算几何研究几何对象的离散算法表示与复杂度，典型输入是点、线段、多边形和半空间，基本谓词包括方向测试、相交、包含与距离比较。算法正确性通常分为组合结构正确和数值实现可靠两层；实数 RAM、代数决策树或有限精度机器模型会给出不同成本。常用范式包括扫描线、分治、随机增量、对偶和空间分解。退化位置与精确谓词必须显式处理。

直觉

几何图形连续，但算法只能处理有限表示。关键是找出由少量符号判定决定的组合结构，再避免浮点误差把“左转”误判成“右转”。

例子与边界

平面凸包可用方向测试和排序求解；线段相交扫描线把二维事件按横坐标排序。三点共线、多个事件同坐标、点落在边界等退化情形会破坏只为一般位置设计的代码。浮点 epsilon 不是普遍正确的精确几何方案：尺度变化和运算累积会使固定阈值失效。输入坐标为整数时，方向行列式可用足够宽整数精确计算，但仍需防溢出。

推论与应用

计算几何支撑 GIS、图形学、机器人、CAD、碰撞检测和空间数据库，并连接凸优化、拓扑与数据结构。

参考资料

• Mark de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008，Chs. 1–7。
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。