av一区二区在线观看_亚洲男人的天堂网站_日韩亚洲视频_在线成人免费_欧美日韩精品免费观看视频_久草视

您的位置:首頁(yè)技術(shù)文章
文章詳情頁(yè)

python Graham求凸包問(wèn)題并畫(huà)圖操作

瀏覽:6日期:2022-06-17 15:17:53
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 pltimport mathimport numpy as np class Node: def __init__(self):self.x = 0self.y = 0self.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 ConvexHullpoints = np.random.rand(10, 2) # 30 random points in 2-Dhull = ConvexHull(points)import matplotlib.pyplot as pltplt.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è)參考,也希望大家多多支持好吧啦網(wǎng)。

標(biāo)簽: Python 編程
相關(guān)文章:
主站蜘蛛池模板: 国产大毛片 | 91久久精品国产 | 精品亚洲一区二区三区四区五区 | 黄色香蕉视频在线观看 | 成人av免费 | 欧美一区精品 | 午夜视频一区 | 91中文在线观看 | 久久精品国产一区老色匹 | 第一区在线观看免费国语入口 | 久久av一区二区三区 | 国产激情一区二区三区 | 国产一二三区精品视频 | 男女久久久 | 91在线最新| 久久亚洲国产 | 亚洲男人天堂av | 久久久久久国产精品免费免费狐狸 | 国产中文字幕亚洲 | 九九色综合 | 国产激情 | 91在线观看免费 | 国产精品久久久久久影院8一贰佰 | 国产精品美女久久久久aⅴ国产馆 | 天天干夜夜操视频 | 91精品久久久久久久久 | 久久久久久国产精品免费免费男同 | 伊人二区| 欧美日韩高清在线一区 | www日本高清| 国产午夜高清 | 精品欧美一区二区三区 | 日韩在线播放网址 | 99久久精品免费视频 | 激情网站 | 懂色tv | 波多野结衣一区二区三区 | 免费在线观看黄网站 | 亚洲一区二区中文字幕在线观看 | 日韩a在线| 一道本视频 |