共计 4890 个字符，预计需要花费 13 分钟才能阅读完成。
分治法求解思路
1. 找出由横坐标最大、最小的两个点 p1 p2 所组成的直线。用该直线将点集分成高低两 set1，set2 局部。
上半区分治：
2. 别离从 set1、set2 找出与线段 p1p2 形成的面积最大的三角形的点 p3,p4。
3. 从 set1 中找出在直线 p1p3 左侧的点集 leftset1、在直线 p3p2 右侧的点集 rightset1。
4 将 leftset1,leftset2 反复 2、3 步骤，直至找不到在直线更外侧的点。
下半区分治：
5. 从 set2 找出在直线 p1p4 左侧的点集 leftset2、在直线 p3p4 右侧的点集 rightset2。
6. 将 leftset1,leftset2 反复 2、3 步骤，直至找不到在直线更外侧的点。
合并：
其实在合并之前，答案就曾经生成了，只不过答案点集是毋庸的，当初让他按顺时针有序
点与直线的地位判断
可通过以下行列式的正负值判断直线与点之间的地位关系，同时数值为点与线段所围成的三角形的面积：
上面的 绘制过程 动态图，能够加深了解。思维就是递归地把整体分为两半，递归地为每一个半区找一个点使之与分界线组成的三角形面积最大，直到在这个半区的分界线以外找不出点再组成三角形，则这个半区进行，回溯到上一个半区持续解决 …
代码
| import random | |
| import matplotlib.pyplot as plt | |
| import matplotlib.animation as animation | |
| draw_line_lists = [] | |
| # 依据三角形的三个顶点坐标，计算三角形面积 | |
| def calc_area(a, b, c): | |
| x1, y1 = a | |
| x2, y2 = b | |
| x3, y3 = c | |
| return x1 * y2 + x3 * y1 + x2 * y3 - x3 * y2 - x2 * y1 - x1 * y3 | |
| # 在（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)])) | |
| def Up(left, right, points, borders): | |
| """ | |
| 寻找上半局部边界点 | |
| :param left: tuple, 最右边的点 | |
| :param right: tuple, 最左边的点 | |
| :param points: 所有的点集 | |
| :param borders: 边界点集 | |
| :return: | |
| """ | |
| # 画图用，记录解决步骤 | |
| draw_line_lists.append(left) | |
| draw_line_lists.append(right) | |
| # left 和 right_point 两个点形成了一个直线，当初想在这条直线下面寻找一个点，要求形成的三角形面积最大 | |
| area_max = 0 # 记录最大三角形的面积 | |
| for item in points: | |
| if item == left or item == right: # 形成直线的两个点，也在 lists 汇合里，但他不在这条直线的下面，不对他计算 | |
| continue | |
| else: | |
| temp = calc_area(left, right, item) # 暂存该点与直线形成的面积，用于接下来的迭代比拟 | |
| if temp > area_max: | |
| max_point = item # 记录以后形成最大三角形的那个点 | |
| area_max = temp # 记录以后最大三角形面积 | |
| if area_max != 0: # 这里其实就是递归边界。当一条线的下面不再有点能够试探，就进行，返回到上一层，解决他的兄弟节点的子树。borders.append(max_point) | |
| Up(left, max_point, points, borders) # 原来的左边界点不变，将刚找到的形成最大三角形失去点作为右边界点，持续递归 | |
| Up(max_point, right, points, borders) # 原来的右边界点不变，将刚找到的形成最大三角形失去点作为左边界点，持续递归 | |
| def Down(left, right, points, borders): | |
| """同 Up 中的参数""" | |
| # 画图用，记录解决步骤 | |
| draw_line_lists.append(left) | |
| draw_line_lists.append(right) | |
| # left 和 right_point 两个点形成了一个直线，当初想在这条直线上面寻找一个点，要求形成的三角形面积最大 | |
| area_max = 0 # 记录最大三角形的面积 | |
| for item in points: | |
| if item == left or item == right: # 形成直线的两个点，也在 lists 汇合里，但他不在这条直线的上面，不对他计算 | |
| continue | |
| else: | |
| temp = calc_area(left, right, item) # 暂存该点与直线形成的面积，用于接下来的迭代比拟 | |
| if temp < area_max: | |
| max_point = item # 记录以后形成最大三角形的那个点 | |
| area_max = temp # 记录以后最大三角形面积 | |
| if area_max != 0: # 这里其实就是递归边界。当一条线的上面不再有点能够试探，就进行，返回到上一层，解决他的兄弟节点的子树。borders.append(max_point) | |
| Down(left, max_point, points, borders) # 原来的左边界点不变，将刚找到的形成最大三角形失去点作为右边界点，持续递归 | |
| Down(max_point, right, points, borders) # 原来的右边界点不变，将刚找到的形成最大三角形失去点作为左边界点，持续递归 | |
| # 合并步骤。执行到这里时，分治曾经完结，答案曾经生成，这个函数的作用就是把无序的答案依照顺时针的程序整顿一下 | |
| def order_border(points): | |
| """ | |
| :param points: 无序边界点集 | |
| :return: list [(,)...(,)] | |
| """ | |
| points.sort() # 按 x 轴程序先排一下，用来寻找最右边和最左边的点 | |
| first_x, first_y = points[0] # 最右边的点 | |
| last_x, last_y = points[-1] # 最左边的点 | |
| up_borders = [] # 上半边界 | |
| dowm_borders =[] # 下半边界 | |
| # 对每一个点进行剖析 | |
| for item in points: | |
| x, y = item | |
| if y > max(first_y, last_y): # 如果比最右边和最左边点的 y 值都大，阐明肯定在上半区 | |
| up_borders.append(item) | |
| elif min(first_y, last_y) < y < max(first_y, last_y): # 如果比最右边和最左边点的 y 值两头，就要借助三角形的面积来做判断。如果面积为负，阐明是一个倒置的三角形，即第三个点在直线的下方，即下半区；否则为上半区 | |
| if calc_area(points[0], points[-1], item) > 0: | |
| up_borders.append(item) | |
| else: | |
| dowm_borders.append(item) | |
| else: # 如果比最右边和最左边点的 y 值都小，阐明肯定在下半区 | |
| dowm_borders.append(item) | |
| list_end = up_borders + dowm_borders[::-1] # 最终顺时针输入的边界点 | |
| return list_end | |
| def draws(points, list_frames, gif_name="save.gif"): | |
| """ | |
| 生成动态图并保留 | |
| :param points: 所有点集 | |
| :param list_frames: 帧 列表 | |
| :param gif_name: 保留动图名称 | |
| :return: .gif | |
| """ | |
| min_value = 0 | |
| max_value = 100 | |
| all_x = [] | |
| all_y = [] | |
| for item in points: | |
| a, b = item | |
| all_x.append(a) | |
| all_y.append(b) | |
| fig, ax = plt.subplots() # 生成轴和 fig, 可迭代的对象 | |
| x, y = [], [] # 用于承受后更新的数据 | |
| line, = plt.plot([], [], color="red") # 绘制线对象，plot 返回值类型，要加逗号 | |
| def init(): | |
| # 初始化函数用于绘制一块洁净的画布，为后续绘图做筹备 | |
| ax.set_xlim(min_value - abs(min_value * 0.1), max_value + abs(max_value * 0.1)) # 初始函数，设置绘图范畴 | |
| ax.set_ylim(min_value - abs(min_value * 0.1), max_value + abs(max_value * 0.1)) | |
| return line | |
| def update(points): | |
| a, b = points | |
| x.append(a) | |
| y.append(b) | |
| line.set_data(x, y) | |
| return line | |
| plt.scatter(all_x, all_y) # 绘制所有散点 | |
| ani = animation.FuncAnimation(fig, update, frames=list_frames, init_func=init, interval=1500) # interval 代表绘制连线的速度，值越大速度越慢 | |
| ani.save(gif_name, writer='pillow') | |
| 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) # 随机生成点 | |
| points.sort() # 先按 x 轴排序一下，用来寻找最右边和最左边的点 | |
| borders = [] # 边界点集 | |
| Up(points[0], points[-1], points, borders) # 上边界点集 | |
| Down(points[0], points[-1], points, borders) # 下边界点集 | |
| borders.append(points[0]) | |
| borders.append(points[-1]) # 将首尾两个点增加到边界点集中 | |
| results = order_border(borders) # 顺时针边界点 | |
| print(results) # 顺时针输入答案 | |
| results.append(results[0]) # 把最初一个点和源点连起来，绘制成闭合连线（仅在画图时这样解决）show_result(points,results) # 显示动态后果 | |
| draws(points, results, "result.gif") # 绘制动静后果 | |
| draws(points, draw_line_lists, "process.gif") # 绘制动静过程 |
程序运行后果
输出坐标点
[(101, 47), (32, 40), (21, 90), (65, 100), (98, 64), (81, 43), (51, 20), (75, 82), (90, 34), (38, 101)]
输入动静绘制过程
输入连接点程序
[(38, 101), (65, 100), (98, 64), (101, 47), (90, 34), (51, 20), (32, 40), (21, 90)]
动态输入最大凸多边形
动静输入最大凸多边形
正文完
