计算几何 计算几何是利用计算机建立数学模型解决几何问题的学科，在计算机图形学、CAD、机器人学等领域有广泛应用。 章节目录 基础知识 专题说明二维几何基础点、向量、直线、多边形三维几何基础三维空间的几何对象距离各种距离度量 经典问题 专题说明时间复杂度Pick定理格点多边形面积O(n)三角剖分多边形分解为三角形O(nlogn)凸包最小凸多边形O(nlogn)扫描线平面几何问题O(nlogn)旋转卡壳凸包直径、最远点对O(n)半平面交线性约束交集O(nlogn)最近点对平面最近两点O(nlogn) 高级技巧 专题说明随机增量法最小圆覆盖等反演变换圆与直线的转换杂项其他技巧和问题 常用技巧 向量叉积：判断左右、计算面积 极角排序：按角度排序点集 扫描线：将二维问题转化为一维 旋转卡壳：双指针遍历凸包