几何算法经典问题
文章目录
- 几何算法经典问题
- 一、几何基础问题
- 1. 判断两条线段是否相交
- 2. 判断点是否在多边形内
- 3. 凸包计算
- 4. 判断一个有序点集的方向（顺时针 or 逆时针）
- 5. 求多边形面积和重心
- 二、 高阶图形问题
- 6. 最小外接矩形（Minimum Bounding Rectangle）
- 7. 多边形之间是否相交
- 8. 判断圆与矩形是否相交
- 9. 求两个矩形的交集面积
- 10. 点到线段的最短距离
- 11. 线段与多边形交点个数
- 12. 多边形剪切（Polygon Clipping）
- 三、 三维几何算法问题（3D Geometry）
- 13. 三维向量运算与空间关系判断
- 14. 判断两条3D线段是否相交
- 15. 3D 点到直线/平面的最短距离
- 16. 判断点是否在三角形/多面体内部
- 17. 三维凸包构建
- 18. 求两个立方体是否相交
- 19. 三维模型的旋转、缩放与变换
- 四、学习建议
一、几何基础问题
1. 判断两条线段是否相交
- 考点：向量叉积，跨立实验，快速排斥
- 推荐实现方法：
- 使用
cross(p1, p2, q1) 和 cross(p1, p2, q2) 判断是否在同侧（跨立实验） - 边界处理：是否共线、点在线段上
2. 判断点是否在多边形内
- 方法：
- 射线法（ray casting）
- 奇偶规则判断穿过边的次数
- 注意：边界点、共线点的特殊处理
3. 凸包计算
- 算法：
- Graham 扫描法（极角排序）
- Andrew 算法（单调链）
- 输入：平面上一组点
- 输出：构成凸包的顶点顺序列表
4. 判断一个有序点集的方向（顺时针 or 逆时针）
- 方法：Shoelace 公式求有向面积
- 正面积 → 逆时针，负面积 → 顺时针
5. 求多边形面积和重心
- 面积：Shoelace 公式
- 重心：每个三角形加权中心，积分法近似
二、 高阶图形问题
6. 最小外接矩形（Minimum Bounding Rectangle）
- 算法：Rotating Calipers（旋转卡壳）
- 输出：最小面积矩形的顶点坐标
7. 多边形之间是否相交
- 方法：
- 分离轴定理（SAT）
- 任意一条边与对方多边形边相交
- 一个多边形顶点是否落入另一个多边形
8. 判断圆与矩形是否相交
9. 求两个矩形的交集面积
- 方法：投影后在 x、y 轴求重叠部分面积
- 扩展：多个矩形并集面积（扫描线 + 线段树）
10. 点到线段的最短距离
- 用处：点线距离，圆线碰撞
- 技巧：投影判断点是否在线段投影内，若否取端点距离
11. 线段与多边形交点个数
12. 多边形剪切（Polygon Clipping）
- 算法：
- Sutherland-Hodgman 算法
- Weiler–Atherton 算法（适用于复杂多边形）
三、 三维几何算法问题（3D Geometry）
13. 三维向量运算与空间关系判断
- 内容：点积、叉积、共线性、共面性判断
- 应用：3D建模、物理仿真中的方向与法线计算
14. 判断两条3D线段是否相交
- 方法：向量投影 + 判定最近点对是否在两段范围内
- 注意：浮点精度、是否共面
15. 3D 点到直线/平面的最短距离
16. 判断点是否在三角形/多面体内部
- 方法：射线法扩展到 3D、体积法（四面体体积符号）
- 应用：点在多面体内部判断，BSP 树构建
17. 三维凸包构建
- 算法：Incremental/QuickHull/Chan’s algorithm
- 难点：三维可视面维护、面连通关系处理
18. 求两个立方体是否相交
- 方法：AABB 包围盒检测、OBB 分离轴定理（SAT）
- 应用：3D 碰撞检测、物理引擎
19. 三维模型的旋转、缩放与变换
- 考点：仿射变换矩阵（4x4）、欧拉角 vs 四元数
- 实战：WebGL/OpenGL 中坐标变换链条
四、学习建议
- 熟练掌握 2D 向量操作：叉积、点积、投影、角度
- 熟悉浮点精度问题的处理（EPS 比较）
- 多写边界处理（共线、端点、浮点误差）
- 三维空间概念理解要清晰：坐标系、法向、表面朝向
- 练习：LeetCode、NowCoder、牛客网图形类题库
