共计 3185 个字符，预计需要花费 8 分钟才能阅读完成。
凸包
凸包（Convex Hull）是一个计算几何（图形学）中的概念。点集 Q 的凸包是指一个最小凸多边形，满足 Q 中的点或者在多边形边上或者在其内。
正式探讨凸包问题之前，这里先引入一个辅助概念——“方向”。
有序点的方向
一个立体内有序点的方向（Orientation）能够有三种：
- 逆时针 CounterClockwise
- 顺时针 Clockwise
-
共线 Colinear
对于点 \(a(x_1, y_1)\)、\(a(x_2, y_2)\)、$c(x_3, y_3)$，
线段 ab 的斜率为
$$
\sigma = \frac{y_2 – y_1}{x_2 – x_1}
$$
线段 bc 的斜率为
$$
\tau = \frac{y_3 – y_2}{x_3 – x_2}
$$
- 若 \(sigma < \tau\)，方向是逆时针（向左转）
- 若 \(sigma = \tau\)，方向是共线
- 若 \(sigma > \tau\)，方向是顺时针（向右转）
因而，三个有序点的方向依赖于表达式（通分失去）
$$
(y_2 – y_1) \times (x_3 – x_2) – (y_3 – y_2) \times (x_2 – x_1)
$$
- 若表达式为负，方向是逆时针
- 若表达式为 0，方向是共线
- 若表达式为正，方向是顺时针
Graham Scan
算法能够分为两个次要局部：
-
预处理
- 找到最左下方的点。使该点 p0 作为输入凸包的第一个元素 points[0]。
- 将剩下的 n – 1 个点依照与 p0 的极角序排序，若有角度雷同，仅保留间隔 p0 最远的那个点
-
承受或回绝点
- 创立空栈 S，将【栈顶的下一个点、位于栈顶的点】入栈。
- 解决残余的每个 points[i]：
-
追踪以后的三个点：栈顶的下一个点、位于栈顶的点，以后剖析的点 points[i]。三点之间有两条连线，看作是两个向量，计算他们之间的叉积，返回三点之间的关系：
<0，阐明第三个点是向左转，则保留第二个点（栈顶元素），将第三个点进栈
\>0，阐明第三个点是向右转，则删除第二个点（栈顶元素），再将第三个点进栈
=0，阐明三点共线（可采纳 >0 的解决形式）
算法的第 1.1 步（找到最左下方的点）花 O(n) 工夫，第 1.2 步（点的排序）花 O(n * logn) 工夫。
第 2 个步骤中，每个元素入栈和出栈最多一次，假如栈操作 O(1) 工夫，则第 2 步总共花 O(n) 工夫。因而总体的工夫复杂度是 O(n * logn)。
代码
import random
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import math
# 在（start,end) 区间内，随机生成具备 n 个点的点集（return: list [(x1,y1)...(xn,yn)]）def sample(n, start=0, end=101):
return list(zip([random.randint(start, end) for _ in range(n)], [random.randint(start, end) for _ in range(n)]))
'''
# 计算两个向量之间的叉积。返回三点之间的关系：<0，阐明第三个点是向左转，则保留第二个点（栈顶元素）, 再退出第三个点
>0，阐明第三个点是向右转，则删除第二个点（栈顶元素）, 再退出第三个点
=0，阐明三点共线
'''
def ccw(a, b, c):
return ((b[1] - a[1]) * (c[0] - b[0])) - ((c[1] - b[1]) * (b[0] - a[0]) )
# 别离求出前面 n - 1 个点与出发点的斜率，借助 sorted 实现从小到大排序
def compute(next):
start = points[0] # 第一个点
# 按极角序排列的办法，但当初输出的坐标点是笛卡尔坐标点。不适宜用这个
# angle = math.atan2(start[2] - next[2], start[1] - next[1] )
# return angle
# 按斜率排列的办法
if start[0] == next[0]: # 如果 x 坐标雷同，那么求斜率时会呈现分母为 0 的状况, 间接返回斜率无穷大
return 99999
slope = (start[1] - next[1]) / (start[0] - next[0])
return slope
def Graham_Scan(points):
# # 找到最右边且最上面的点作为出发点，和第一位调换
Min=9999
for i in range(len(points)):
# 寻找最右边的点
if points[i][0]<Min:
Min = points[i][0]
index = i
# 如果同在最右边，可取 y 值更小的
elif points[i][0]==Min:
if points[i][1]<=points[index][1]:
Min = points[i][0]
index = i
# 和第一位调换地位
temp = points[0]
points[0] = points[index]
points[index] = temp
# 排序：从第二个元素开始，按与第一个元素的斜率排序
points = points[:1] + sorted(points[1:], key=compute) # 前半部分是出发点；后半局部是通过按斜率排序之后的 n - 1 个坐标点 留神：“+”是拼接的含意，不是数值相加
# 用列表模仿一个栈。（最先退出的是前两个点，前两次 while 必然不成立，从而将点加进去）convex_hull = []
for p in points:
'''
# 如果能顺时针方向（右转）连贯第三个顶点，就删除栈顶元素再退出这个顶点；否则（向左转才达到第三个顶点），间接退出这个顶点
convex_hull[-2]：栈顶元素上面的元素
convex_hull[-1]：栈顶元素
p：要剖析的第三个顶点
'''
while len(convex_hull) > 1 and ccw(convex_hull[-2], convex_hull[-1], p) >= 0:
convex_hull.pop()
convex_hull.append(p)
return convex_hull
def show_result(points, results):
"""
画图
:param points: 所有点集
:param results: 所有边集
:return: picture
"""
all_x = []
all_y = []
for item in points:
a, b = item
all_x.append(a)
all_y.append(b)
for i in range(len(results)-1):
item_1=results[i]
item_2 = results[i+1]
# 横坐标, 纵坐标
one_, oneI = item_1
two_, twoI = item_2
plt.plot([one_, two_], [oneI, twoI])
plt.scatter(all_x, all_y)
plt.show()
if __name__ == '__main__':
# points = [(101, 47), (32, 40), (21, 90), (65, 100), (98, 64), (81, 43), (51, 20), (75, 82), (90, 34), (38, 101)]
points = sample(100)
hull = Graham_Scan(points)
print(hull)
# 可视化，有利于查看后果的正确性
hull.append(hull[0]) # 把最初一个点和源点连起来，绘制成闭合连线（仅在画图时这样解决）show_result(points, hull)
程序运行后果
连接点的程序：
[(2, 5), (21, 0), (91, 1), (101, 9), (99, 62), (91, 88), (75, 101), (27, 98), (12, 96), (2, 92), (2, 53)] 可视化：
https://ysw1912.github.io/pos…
https://en.wikipedia.org/wiki…
