蠻力法姊妹篇 | Python分治法解決凸包問題并用matplotlib實作可視化以及與蠻力法的對比

之前寫了一篇Python蠻力法解決凸包問題并用matplotlib實作可視化，最後也給出了同樣是在1000個點的情況下蠻力法和分治法的差距有多大(蠻力法1154秒，分治法0.125秒…)

先解釋一下為什麼吧：

因為蠻力法的重點在于中間有三重循環，是以時間複雜度為O(n3)，而分治法需要對點集進行一次排序還有一次周遊，排序算法的複雜度為O(logn)，周遊一遍複雜度為O(n)，是以分治法的時間複雜度為O(nlogn)。

二者相比，完全就不是一個檔次啊…🌚

然後說說我的思路：

分治法，顧名思義，分而治之。

對于平面上的一個點集：

我們很容易找到最左邊的點和最右邊的點，将他們連起來，就會将整個點集分為上半部分和下半部分，同時這兩個點也必定是凸包的邊界點

接下來在其它點中找到兩個點，使之與這兩個點組成的三角形面積最大或最小(最大的是上半包的頂點；最小即為負的最大，說明這個點是下半包的頂點)，并将這兩個點添加到邊界點集合中。

找到兩個頂點後，繼續對上/下半包的點進行遞歸周遊，對于上半包來說，以新形成的那兩條邊為底，如果有點新編圍成的三角形面積為正，那就找到最大的繼續分三角形；下班包也是一樣的道理，隻是下半包需要找最小的。同樣将頂點添加到邊界點集合中去。

完了繼續遞歸，知道沒有符合條件的為止。此時的邊界點集合再加上最左邊和最右邊的兩個點，就是凸包所有的邊界點。

( BUT,你認為真實的過程就是這樣的嗎？不不不，這隻是一個便于我們了解的過程，真實的遞歸過程是這樣的：😏

如果你對這張圖是怎麼畫出來的有興趣，可以去我的這篇文章：分治法進階篇 | 利用matplotlib畫出凸包問題分治遞歸政策實作過程動态圖看看<有源碼欸>）

然後說代碼：

随機生成具有n個點的點集：

def rand_point_set(n, range_min=0, range_max=101):
    """
    随機生成具有 n 個點的點集
    :param range_max: 生成随機點最小值，預設 0
    :param range_min: 生成随機點最大值，預設 100
    :param n: int
    :return: list [(x1,y1)...(xn,yn)]
    """
    try:
        return list(zip([random.uniform(range_min, range_max) for _ in range(n)],
                        [random.uniform(range_min, range_max) for _ in range(n)]))
    except IndexError as e:
        print("\033[31m" + ''.join(e.args) + "\n輸入範圍有誤！" + '\033[0m')
           

判斷三角形的面積：

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
           

遞歸尋找上半部分的邊界點：

def border_point_up(left_point, right_point, lists, border_points):
    """
    尋找上半部分邊界點
    :param left_point: tuple, 最左邊的點
    :param right_point: tuple, 最右邊的點
    :param lists: 所有的點集
    :param border_points: 邊界點集
    :return:
    """
    area_max = 0
    max_point = ()
    for item in lists:
        if item == left_point or item == right_point:
            continue
        else:
            max_point = item if calc_area(left_point, right_point, item) > area_max else max_point
            area_max = calc_area(left_point, right_point, item) if calc_area(left_point, right_point,item) > area_max else area_max
    if area_max != 0:
        border_points.append(max_point)
        border_point_up(left_point, max_point, lists, border_points)
        border_point_up(max_point, right_point, lists, border_points)
           

遞歸尋找下半部分的邊界點：

def border_point_down(left_point, right_point, lists, border_points):
    """
    尋找下半部分邊界點
    :param left_point: tuple, 最左邊的點
    :param right_point: tuple, 最右邊的點
    :param lists: 所有的點集
    :param border_points: 邊界點集
    :return:
    """
    area_max = 0
    max_point = ()
    for item in lists:
        if item == left_point or item == right_point:
            continue
        else:
            max_point = item if calc_area(left_point, right_point, item) < area_max else max_point
            area_max = calc_area(left_point, right_point, item) if calc_area(left_point, right_point,item) < area_max else area_max
    if area_max != 0:
        border_points.append(max_point)
        border_point_down(left_point, max_point, lists, border_points)
        border_point_down(max_point, right_point, lists, border_points)
           

傳回順時針的邊界點集：

def order_border(lists):
    """
    傳回順時針的邊界點集
    :param lists: 無序邊界點集
    :return: list [( , )...( , )]
    """
    lists.sort()
    first_x, first_y = lists[0]  # 最左邊的點
    last_x, last_y = lists[-1]  # 最右邊的點
    list_border_up = []  # 上半邊界
    for item in lists:
        x, y = item
        if y > max(first_y, last_y):
            list_border_up.append(item)
        if min(first_y, last_y) < y < max(first_y, last_y):
            if calc_area(lists[0], lists[-1], item) > 0:
                list_border_up.append(item)
            else:
                continue
    list_border_down = [_ for _ in lists if _ not in list_border_up]  # 下半邊界
    list_end = list_border_up + list_border_down[::-1]  # 最終順時針輸出的邊界點
    return list_end
           

matplotlib畫圖：

def draw(list_points, list_borders):
    """
    畫圖
    :param list_points: 所有點集
    :param list_borders: 所有邊界點集
    :return: picture
    """
    list_all_x = []
    list_all_y = []
    for item in list_points:
        a, b = item
        list_all_x.append(a)
        list_all_y.append(b)
    list_borders.append(list_borders[0])
    for i in range(len(list_borders) - 1):
        one_, oneI = list_borders[i]
        two_, twoI = list_borders[i + 1]
        plt.plot([one_, two_], [oneI, twoI])
    plt.scatter(list_all_x, list_all_y)
    plt.show()
           

最後寫一個輸入函數：

因為我的随機點集生成函數 rand_point_set(n, range_min=0, range_max=101) 指定的後兩個參數是用來選擇生成點集範圍的，是以，這是我的輸入函數：

def main():
    """
    :return: 所有點
    """
    inputs = list(map(int, input().split()))
    if len(inputs) == 1:
        return rand_point_set(inputs[0])
    elif len(inputs) == 2:
        return rand_point_set(inputs[0], inputs[1])
    elif len(inputs) == 3:
        return rand_point_set(inputs[0], inputs[1], inputs[2])
    else:
        print("\033[31m輸入資料太多,請重新輸入!\033[0m")
        main()
           

最後把這些函數組合起來，

我把完整代碼(複制可用的那種)貼到這裡：

import random
import numpy as np
import matplotlib.pyplot as plt


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


def rand_point_set(n, range_min=0, range_max=101):
    """
    随機生成具有 n 個點的點集
    :param range_max: 生成随機點最小值，預設 0
    :param range_min: 生成随機點最大值，預設 100
    :param n: int
    :return: list [(x1,y1)...(xn,yn)]
    """
    try:
        return list(zip([random.uniform(range_min, range_max) for _ in range(n)],
                         [random.uniform(range_min, range_max) for _ in range(n)]))
    except IndexError as e:
        print("\033[31m" + ''.join(e.args) + "\n輸入範圍有誤！" + '\033[0m')


def border_point_up(left_point, right_point, lists, border_points):
    """
    尋找上半部分邊界點
    :param left_point: tuple, 最左邊的點
    :param right_point: tuple, 最右邊的點
    :param lists: 所有的點集
    :param border_points: 邊界點集
    :return:
    """
    area_max = 0
    max_point = ()
    for item in lists:
        if item == left_point or item == right_point:
            continue
        else:
            max_point = item if calc_area(left_point, right_point, item) > area_max else max_point
            area_max = calc_area(left_point, right_point, item) if calc_area(left_point, right_point,
                                                                             item) > area_max else area_max
    if area_max != 0:
        border_points.append(max_point)
        border_point_up(left_point, max_point, lists, border_points)
        border_point_up(max_point, right_point, lists, border_points)


def border_point_down(left_point, right_point, lists, border_points):
    """
    尋找下半部分邊界點
    :param left_point: tuple, 最左邊的點
    :param right_point: tuple, 最右邊的點
    :param lists: 所有的點集
    :param border_points: 邊界點集
    :return:
    """
    area_max = 0
    max_point = ()
    for item in lists:
        if item == left_point or item == right_point:
            continue
        else:
            max_point = item if calc_area(left_point, right_point, item) < area_max else max_point
            area_max = calc_area(left_point, right_point, item) if calc_area(left_point, right_point,
                                                                             item) < area_max else area_max

    if area_max != 0:
        border_points.append(max_point)
        border_point_down(left_point, max_point, lists, border_points)
        border_point_down(max_point, right_point, lists, border_points)


def order_border(lists):
    """
    傳回順時針的邊界點集
    :param lists: 無序邊界點集
    :return: list [( , )...( , )]
    """
    lists.sort()
    first_x, first_y = lists[0]  # 最左邊的點
    last_x, last_y = lists[-1]  # 最右邊的點
    list_border_up = []  # 上半邊界
    for item in lists:
        x, y = item
        if y > max(first_y, last_y):
            list_border_up.append(item)
        if min(first_y, last_y) < y < max(first_y, last_y):
            if calc_area(lists[0], lists[-1], item) > 0:
                list_border_up.append(item)
            else:
                continue
    list_border_down = [_ for _ in lists if _ not in list_border_up]  # 下半邊界
    list_end = list_border_up + list_border_down[::-1]  # 最終順時針輸出的邊界點
    return list_end


def draw(list_points, list_borders):
    """
    畫圖
    :param list_points: 所有點集
    :param list_borders: 所有邊界點集
    :return: picture
    """
    list_all_x = []
    list_all_y = []
    for item in list_points:
        a, b = item
        list_all_x.append(a)
        list_all_y.append(b)
    list_borders.append(list_borders[0])
    for i in range(len(list_borders) - 1):
        one_, oneI = list_borders[i]
        two_, twoI = list_borders[i + 1]
        plt.plot([one_, two_], [oneI, twoI])
    plt.scatter(list_all_x, list_all_y)
    plt.show()


def main():
    """
    :return: 所有點
    """
    inputs = list(map(int, input().split()))
    if len(inputs) == 1:
        return rand_point_set(inputs[0])
    elif len(inputs) == 2:
        return rand_point_set(inputs[0], inputs[1])
    elif len(inputs) == 3:
        return rand_point_set(inputs[0], inputs[1], inputs[2])
    else:
        print("\033[31m輸入資料太多,請重新輸入!\033[0m")
        main()


if __name__ == "__main__":
    print("""輸入規則:
最少一個最多三個
後面可以跟數字用來指定生成區間(預設[0，100])，中間用空格隔開
例如：
    輸入 10   ---即為在預設區間[0，100]生成10個随機點
    輸入 10 50   ---即為在區間[50,100]生成10個随機點
    輸入 10 50 200   ---即為在區間[50,200]生成10個随機點
請輸入:\t""")
    list_points = main()  # 所有點
    list_points.sort()
    border_points = []  # 邊界點集
    border_point_up(list_points[0], list_points[-1], list_points, border_points)  # 上邊界點集
    border_point_down(list_points[0], list_points[-1], list_points, border_points)  # 下邊界點集
    border_points.append(list_points[0])
    border_points.append(list_points[-1])  # 将首尾兩個點添加到邊界點集中
    # print(order_border(border_points))  # 順時針輸出邊界點
    draw(list_points, order_border(border_points))
           

下面是我用pyecharts畫的蠻力法和分治法實間對比圖：

可以看到，蠻力法随着點數的增加，時間幾乎是呈指數型增長；而分治法相對來說增長比較平緩，甚至于100個點的蠻力法耗時比100000個點的分治法耗時還要多！

PS：

上面的曲線是根據我的蠻力法和分治法得出來的資料，而且由于電腦組態、網速、背景程式等等一系列原因，不同的裝置結果可能會略有差異。但是總體增長趨勢趨勢一定是不變的！

🆗

最後在放一張分治法100000個點的圖：(也沒啥看頭…🌚)