计算几何问题

几何图形连续，算法却只能处理有限表示；计算几何的困难因而不只在组合规模，还在连续坐标与离散拓扑的相互作用。一次符号误差就可能把“共线”变成“左转”，进而改变整张结构。有效算法通常先找出少数可靠谓词——方向、内外、相交、距离比较——再用扫描线、分治或随机增量组织全局计算。几何退化不是实现角落，而是定理假设和数据模型的一部分。

平面凸包可按极角或坐标排序后维护方向判定；线段相交则可由扫描线范式公理库扫描线范式Sweep-line paradigm · Plane sweep按事件推进一条虚拟直线，并用动态有序状态维护当前横截面组合关系的计算几何范式。把二维变化压成事件队列和一维状态。三点共线、多个事件同坐标、点落在边界等退化情形会破坏只为一般位置设计的代码。固定浮点 epsilon 不是普遍正确的精确几何方案：尺度变化和误差累积会使阈值失效；整数坐标可用足够宽的精确行列式，但仍需防溢出。

“图上看起来不相交”不是数学判定；端点接触、重合线段和重复点必须预先规定是否计为相交。高维算法的复杂度还会随维数迅速增长，二维直觉不能无条件外推。

仿射空间公理库仿射空间Affine space忘去原点但保留向量平移作用和仿射组合的空间。提供坐标背景，方向判定公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。是二维算法的核心原语。扫描线范式公理库扫描线范式Sweep-line paradigm · Plane sweep按事件推进一条虚拟直线，并用动态有序状态维护当前横截面组合关系的计算几何范式。按一个坐标推进事件并维护横截面次序；随机增量构造公理库随机增量构造randomized incremental construction · RIC按随机排列插入对象，以冲突关系和反向分析控制几何结构的期望构建成本。随机打乱对象，以冲突图把重建成本计入期望。面对预处理后的查询，正交范围搜索公理库正交范围查询Orthogonal range searching在固定维点集中对轴对齐盒执行报告、计数、判空或聚合查询。报告轴对齐区域内的对象，点定位问题公理库平面点定位问题Planar point location预处理平面直线细分后，查询点所在面并规定边界退化语义。则在平面细分中寻找包含查询点的面，两者都必须把预处理、空间、查询和输出 $k$ 分开报告。

对象与查询还由简单多边形公理库简单多边形Simple polygon由不自交的闭合折线围成、没有孔洞并具有明确内部与外部的平面多边形。、点内判定公理库点在多边形内判定Point in polygon · Point-in-polygon test先识别边界，再以射线横截奇偶或绕数把查询点分类为简单多边形内部、外部或边界。等页面固定；点集结构由凸包公理库凸包Convex hull包含给定点集的最小凸集，是凸几何中的基本包络对象，并可进一步研究其算法构造。、Voronoi 图公理库Voronoi 图Voronoi diagram · Voronoi tessellation按到有限站点集中的最近距离把度量空间划分为闭合单元及其公共边界。和Delaunay 三角剖分公理库Delaunay 三角剖分Delaunay triangulation以空外接圆条件或 Voronoi 邻接刻画有限平面点集的几何三角剖分。承担；最近点对公理库平面最近点对Closest pair of points · Planar closest pair以分治和窄带 packing 证书在 O(n log n) 时间求 Euclidean 平面最近点对。展示几何分治路线。总页只提供对象—谓词—范式—查询结构的方法地图，各专页分别证明不变量、保证类型和退化边界。