python Graham求凸包并畫(huà)圖
python寫(xiě)Graham沒(méi)有c++那么好寫(xiě)，但是python畫(huà)圖簡(jiǎn)單。只需要用matplotlib里的pyplot，c++畫(huà)圖太難了。
Graham算法寫(xiě)起來(lái)比較簡(jiǎn)單，只需要想辦法對(duì)最小點(diǎn)和其他的點(diǎn)所連成的直線，與x軸正半軸的夾角進(jìn)行排序，然后其他的就直接套用Graham算法模板就好了，因?yàn)閏++可以重載排序函數(shù)sort，不用計(jì)算角度（用其他的數(shù)學(xué)方法），但是python不行（也許是我不知道而已，菜）。
python必須要在結(jié)構(gòu)體里面加上角度這個(gè)變量，然后才能按照角度排序。排好序后就變得容易了，用stack棧存放答案，算完答案后，用scatter（散點(diǎn)圖）畫(huà)出點(diǎn)，用plt（折線圖）畫(huà)邊界就好了。
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
#和最左下的點(diǎn)連成的直線，與x軸正半軸的夾角大小
#按照角度從小到大排序
def cmp(x):
return x.angel
def bottom_point(points):
min_index = 0
n = len(points)
#先判斷y坐標(biāo)，找出y坐標(biāo)最小的點(diǎn)，x坐標(biāo)最小的點(diǎn)
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
#計(jì)算角度
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個(gè)點(diǎn)的坐標(biāo)，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
#計(jì)算每個(gè)點(diǎn)和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循環(huán)更新答案
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]
#一定要大于等于零，因?yàn)榭赡茉谝粭l直線上
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])
#畫(huà)出圖像
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
圖形學(xué)可以說(shuō)經(jīng)常遇到這東西了，這里給出一個(gè)庫(kù)函數(shù)的實(shí)現(xiàn)
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()
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
您可能感興趣的文章:- python 生成任意形狀的凸包圖代碼
- 基于python 凸包問(wèn)題的解決
- Python求凸包及多邊形面積教程
