关于python:使用分治法解决凸包问题

47次阅读

共计 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)]

动态输入最大凸多边形

动静输入最大凸多边形


正文完
 0