python Graham求凸包问题并画图操作
作者:sunnyorrainy 时间:2023-06-01 12:37:00
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()
来源:https://blog.csdn.net/qq_43552826/article/details/104632831
标签:python,Graham,凸包,画图
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Python 数据可视化超详细讲解折线图的实现
2023-06-06 14:49:18
![](https://img.aspxhome.com/file/2023/9/90879_0s.png)
Tkinter组件Checkbutton的具体使用
2023-03-19 14:55:46
![](https://img.aspxhome.com/file/2023/7/68977_0s.png)
flask开启多线程的具体方法
2023-03-10 06:30:50
MySQL8新特性:持久化全局变量的修改方法
2024-01-19 05:38:30
html中的sub与sup标签
2009-03-06 13:12:00
![](https://img.aspxhome.com/file/UploadPic/20093/6/120757af09ag213-77s.jpg)
Anaconda之conda常用命令介绍(安装、更新、删除)
2021-06-11 22:52:03
![](https://img.aspxhome.com/file/2023/4/133784_0s.jpg)
JavaScript实现点击出现子菜单效果
2024-04-19 10:45:56
![](https://img.aspxhome.com/file/2023/6/135776_0s.jpg)
Fabric 应用案例
2021-10-11 13:13:01
解析mysql修改为utf8后仍然有乱码的问题
2024-01-14 14:36:09
vue.js中toast用法及使用toast弹框的实例代码
2024-05-08 09:33:02
![](https://img.aspxhome.com/file/2023/6/130276_0s.png)
最全的MYSQL备份方法
2009-12-29 10:19:00
终于搞懂了Python中super(XXXX, self).__init__()的作用了
2022-01-04 00:35:44
Python 批量合并多个txt文件的实例讲解
2022-09-18 07:39:47
CSS关于Border你可能会不注意的东西
2007-10-20 13:50:00
![](https://img.aspxhome.com/file/UploadPic/200710/20/20071020135623390s.gif)
JS实现页面打印(整体、局部)
2024-04-26 17:14:27
SQL提取数据库表名及字段名等信息代码示例
2024-01-26 23:18:54
tornado框架blog模块分析与使用
2023-01-29 10:39:27
python分别打包出32位和64位应用程序
2023-11-03 04:41:10
![](https://img.aspxhome.com/file/2023/6/68296_0s.jpg)
深入解析Python编程中super关键字的用法
2021-08-24 18:17:10
在访客的内心深处做导航
2008-06-05 12:43:00