, 使用 Python 3.9 开发 ;
一、Graham 凸包扫描算法
1、凸包概念
凸包概念 : 在二维平面中 , 包围点集的最小凸多边形 , 其顶点集包含了给定点集中的所有点 , 并且不存在任何一条线段可以穿过这个多边形的内部而不与多边形的边界相交...凸包边界 , 其时间复杂度是 O(nlogn) ;
二、Graham 算法前置知识点
1、角排序
角排序 是 以角度大小进行排序 , 这里的角度是 选定的基准点 与 点集中的点 的 极角 进行排序 ;...) 确定 ;
在角排序中 , 极角是指从基准点出发到其他点的连线与某一固定方向的夹角 ;
角排序用于解决凸包算法中的子问题 , 例如 Graham 扫描算法中 , 需要对点集中的点按照其与基准点的极角进行排序..., 以便确定凸包的边界顺序 ;
在本算法中 , 以极坐标的原点为中心 , 进行角排序 ;
2、叉积
叉积 , 又称为 " 向量积 " 或 " 矢量积 " , 是两个向量之间的一种运算 , 叉积 的结果是一个新的向量...中 ,
从 第三个点开始循环 , 循环内容如下 :
先将要遍历的点放入 栈中 , 判断 新放入的点 是否在 栈顶 2 个元素组成的向量的左边 ,
如果在左边 , 说明该点是凸包上的点 , 栈中保留该点