, 使用 Python 3.9 开发 ;
一、Graham 凸包扫描算法
1、凸包概念
凸包概念 : 在二维平面中 , 包围点集的最小凸多边形 , 其顶点集包含了给定点集中的所有点 , 并且不存在任何一条线段可以穿过这个多边形的内部而不与多边形的边界相交...;
下图中 ,
左侧的 P1 图是凸包 ;
右侧的 P2 图不是凸包 , 因为该图中 , A2 到 B2 的点连接线与 凸多边形 的边界发生了相交 ;
2、常用的凸包算法
常用的凸包算法有 :
Graham...扫描法
Jarvis 步进法
快速凸包算法
3、Graham 凸包扫描算法
在二维平面上给出一个有限个点的点集 , 其坐标都为 (x , y) ;
Graham 格雷厄姆 凸包扫描算法 , 可以找到上述点集的..., 值为两个向量所张成的平行四边形的面积 , 方向垂直于这个平行四边形的平面 , 符合右手定则 ;
判断 B 点 在 向量 OA 的左侧还是右侧 :
B 在 向量 OA 左侧 , 则 OA 与 OB...(point.x - 2, point.y - 2, point.x + 2, point.y + 2, fill="blue") # 绘制圆点
# 在画布上绘制凸包
def draw_convex_hull