python Graham求凸包問題並畫圖操作

Posted on by

python Graham求凸包並畫圖

python寫Graham沒有c++那麼好寫，但是python畫圖簡單。隻需要用matplotlib裡的pyplot，c++畫圖太難瞭。

Graham算法寫起來比較簡單，隻需要想辦法對最小點和其他的點所連成的直線，與x軸正半軸的夾角進行排序，然後其他的就直接套用Graham算法模板就好瞭，因為c++可以重載排序函數sort，不用計算角度（用其他的數學方法），但是python不行（也許是我不知道而已，菜）。

python必須要在結構體裡面加上角度這個變量，然後才能按照角度排序。排好序後就變得容易瞭，用stack棧存放答案，算完答案後，用scatter（散點圖）畫出點，用plt（折線圖）畫邊界就好瞭。

import matplotlib.pyplot as plt
import math
import numpy as np  
class Node:
    def __init__(self):
        self.x = 0
        self.y = 0
        self.angel = 0
        #和最左下的點連成的直線，與x軸正半軸的夾角大小 
 
#按照角度從小到大排序
def cmp(x):
    return x.angel  
def bottom_point(points):
    min_index = 0
    n = len(points)
    #先判斷y坐標，找出y坐標最小的點，x坐標最小的點
    for i in range(1, n):
        if points[i].y < points[min_index].y or (points[i].y == points[min_index].y and
           points[i].x < points[min_index].x):
            min_index = i
    return min_index 
 
#計算角度
def calc_angel(vec):
    norm = math.sqrt(vec[0] * vec[0] + vec[1] * vec[1])
    if norm == 0:
        return 0
    angel = math.acos(vec[0]/norm)
    if vec[1] >= 0:
        return angel
    else:
        return math.pi * 2 - angel 
 
def multi(v1, v2):
    return v1[0] * v2[1] - v1[1] * v2[0] 
 
point = []
n = 30
#生成30個點的坐標，n可以修改
for i in range(n):
    temp = Node()
    temp.x = np.random.randint(1, 100)
    temp.y = np.random.randint(1, 100)
    point.append(temp)
index = bottom_point(point)
for i in range(n):
    if i == index:
        continue
    #計算每個點和point[index]所連成的直線與x軸正半軸的夾角
    vector = [point[i].x - point[index].x, point[i].y - point[index].y]
    #vector是向量
    point[i].angel = calc_angel(vector)
#排序
point.sort(key=cmp)
#答案存入棧中
stack = []
stack.append(point[0])
stack.append(point[1])
#for循環更新答案
for i in range(2, n):
    L = len(stack)
    top = stack[L - 1]
    next_top = stack[L - 2]
    vec1 = [point[i].x - next_top.x, point[i].y - next_top.y]
    vec2 = [top.x - next_top.x, top.y - next_top.y]
    #一定要大於等於零，因為可能在一條直線上
    while multi(vec1, vec2) >= 0:
        stack.pop()
        L = len(stack)
        top = stack[L - 1]
        next_top = stack[L - 2]
        vec1 = [point[i].x - next_top.x, point[i].y - next_top.y]
        vec2 = [top.x - next_top.x, top.y - next_top.y]
    stack.append(point[i])
#畫出圖像
for p in point:
    plt.scatter(p.x, p.y, marker='o', c='g')
L = len(stack)
for i in range(L-1):
    plt.plot([stack[i].x, stack[i+1].x], [stack[i].y, stack[i+1].y], c='r')
plt.plot([stack[0].x, stack[L-1].x], [stack[0].y, stack[L-1].y], c='r')
plt.show()

Python 找到凸包 Convex hulls

圖形學可以說經常遇到這東西瞭，這裡給出一個庫函數的實現

from scipy.spatial import ConvexHull
points = np.random.rand(10, 2) # 30 random points in 2-D
hull = ConvexHull(points)
import matplotlib.pyplot as plt
plt.plot(points[:,0], points[:,1], 'o')
for simplex in hull.simplices:
 plt.plot(points[simplex,0], points[simplex,1], 'k-')
plt.show()

以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。

推薦閱讀：