[L2] 50_计算几何

核心哲学：用“不精准”的浮点数模拟物理世界。核心逻辑：处理精度，并将散点转化为有序线条（扫描/旋转）。

1. 知识图谱与演化

• 核心工具: 向量叉积、凸包、扫描线、半平面交。

• 演化路径:

  1. 点线关系：利用叉积判断方向与交点。

  2. 凸性封装：提取点集的最外层轮廓（凸包）。

  3. 动态扫描：利用旋转卡壳或扫描线将二维静态问题转化为一维动态问题。

  4. 区域切割：求解多边形的交并补（半平面交）。

2. 决策矩阵

• 点集最远距离 / 围栏问题：[[Note] 凸包体系] (旋转卡壳)。

• 矩形面积并 / 轮廓线长度：[[Note] 扫描线与半平面] (扫描线)。

• 多边形核 / 区域交集：[[Note] 扫描线与半平面] (半平面交)。

• 最小圆覆盖 / 积分：[[Note] 几何基础]。

3. 核心板块索引

3.1 几何基础

3.1 [L3] 51 几何基础

• [[Note] 向量运算]: 点积, 叉积, 极角排序.

• [[Note] 最小圆覆盖]: 随机增量法。

• [[Note] 自适应辛普森]: 数值积分。

3.2 [L3] 52 凸包体系

• [[Note] 二维凸包]: Andrew 算法。

• [[Note] 旋转卡壳]: 凸多边形直径与宽。

• [[Note] 闵可夫斯基和]: 凸多边形的向量和。

3.3 [L3] 53 扫描线与半平面

• [[Note] 面积并]: 扫描线 + 线段树。

• [[Note] 半平面交]: 多边形切割与核。