计算几何
计算几何
基本概念
计算几何处理几何对象的计算问题，包括点、线、多边形等基本图形的各种运算。
特点
- 时间复杂度：与具体问题相关
- 空间复杂度：通常为
- 适用于几何对象的计算和判断
分类
| 点 | 坐标对 | 二维平面上的位置 |
| 向量 | 坐标差 | 方向和大小 |
| 线段 | 两个端点 | 有限直线 |
| 直线 | 点斜式/一般式 | 无限延伸 |
| 多边形 | 点集合 | 封闭图形 |
基本运算
基本运算是计算几何中的常用操作。
特点
- 时间复杂度：通常为
- 空间复杂度：
- 适用于基本几何运算
分类
| 向量运算 | 加减乘除 | 向量的基本运算 |
| 点积叉积 | 内积外积 | 向量的积运算 |
| 距离计算 | 欧氏距离 | 点线距离计算 |
| 方向判断 | 叉积符号 | 点的相对方向 |
高级算法
高级算法用于解决复杂的几何问题。
特点
- 时间复杂度：通常为
或更高
- 空间复杂度：与具体问题相关
- 适用于复杂几何问题求解
分类
| 凸包 | 求点集的凸包 | Graham扫描 |
| 线段相交 | 判断线段相交 | 扫描线算法 |
| 点在多边形内 | 判断点的位置 | 射线法则 |
| 最近点对 | 求最近两点 | 分治算法 |
应用场景对比
基本概念适合：
- 点线表示
- 向量运算
- 距离计算
- 方向判断
基本运算适合：
- 向量操作
- 角度计算
- 面积计算
- 相对位置
高级算法适合：
- 凸包问题
- 相交判断
- 包含判断
- 最近点对
选择建议
- 简单几何运算使用基本概念
- 需要精确计算时注意误差
- 复杂问题使用高级算法
- 注意数值稳定性
- 考虑特殊情况处理
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
海康威视公司福利 1154人发布
