【计算几何01】Graham-Scan算法计算凸包

​

​

import random"""
Computes the Convex Hull with the Graham Scan algorithm
Use:h = ConvexHull()print(h.hull)
"""class ConvexHull:def __init__(self, points):if not points:self.points = [(random.randint(0,100),random.randint(0,100)) for i in range(50)]else:self.points = pointsself.hull = self.compute_convex_hull()def get_cross_product(self,p1, p2, p3):return ((p2[0] - p1[0])*(p3[1] - p1[1])) - ((p2[1] - p1[1])*(p3[0] - p1[0]))def get_slope(self,p1, p2):if p1[0] == p2[0]:return float('inf')else:return 1.0*(p1[1]-p2[1])/(p1[0]-p2[0])def compute_convex_hull(self):hull = []self.points.sort(key=lambda x:[x[0],x[1]])start = self.points.pop(0)hull.append(start)self.points.sort(key=lambda p: (self.get_slope(p,start), -p[1],p[0]))for pt in self.points:hull.append(pt)while len(hull) > 2 and self.get_cross_product(hull[-3],hull[-2],hull[-1]) < 0:hull.pop(-2)return hullimport numpy as np
import matplotlib.pyplot as pltfig = plt.figure()
ax1 = fig.add_subplot(111)
#设置标题
ax1.set_title('Scatter Plot')
#设置X轴标签
plt.xlabel('X')
#设置Y轴标签
plt.ylabel('Y')
#画散点图
for pt in MakePoint.points:ax1.scatter(pt[0],pt[1],c = 'r',marker = 'o')
for pt in sidePoint:ax1.scatter(pt[0],pt[1],c = 'b',marker = '*')
#设置图标
plt.legend('x1')
#显示所画的图
plt.show()

​

import cv2
import numpy as np# 新建512*512的空白图片
img = np.zeros((512,512,3), np.uint8)
# 平面点集
pts = np.array([[200,250], [250,300], [300, 270], [270,200], [120, 240]], np.int32)
pts = pts.reshape((-1,1,2))
# 绘制填充的多边形
cv2.fillPoly(img, [pts], (255,255,255))
# 保存图片
cv2.imwrite('F://polygon.png', img)

import cv2# 读取图片并转至灰度模式
imagepath = 'F://convex.png'
img = cv2.imread(imagepath, 1)
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
# 二值化
ret, thresh = cv2.threshold(gray, 127, 255, cv2.THRESH_BINARY)
# 图片轮廓
image, contours, hierarchy = cv2.findContours(thresh, 2, 1)
cnt = contours[0]
# 寻找凸包并绘制凸包（轮廓）
hull = cv2.convexHull(cnt)
print(hull)length = len(hull)
for i in range(len(hull)):cv2.line(img, tuple(hull[i][0]), tuple(hull[(i+1)%length][0]), (0,255,0), 2)# 显示图片
cv2.imshow('line', img)
cv2.waitKey()

import sys
import random
import matplotlibmatplotlib.use('Qt5Agg')
from PyQt5 import QtCore, QtWidgets
from PyQt5.QtGui import QIcon
from PyQt5.QtWidgets import QApplication, QMainWindow, QMenu, QVBoxLayout, QHBoxLayout, QSizePolicy, QWidget, \QTextBrowser, QLineEdit, QPushButton, QMessageBox
from matplotlib.backends.backend_qt5agg import FigureCanvasQTAgg as FigureCanvas
from matplotlib.figure import Figure
from matplotlib.animation import FuncAnimation
import matplotlib.pyplot as pltxx = [random.randint(1, 10) for i in range(10)]
yy = [random.randint(1, 10) for i in range(10)]class MyMplCanvas(FigureCanvas):def __init__(self, parent=None, width=12, height=6, dpi=100):fig = Figure(figsize=(9, 7), dpi=100)self.ax = fig.add_subplot(1, 1, 1)FigureCanvas.__init__(self, fig)self.setParent(parent)FigureCanvas.setSizePolicy(self,QtWidgets.QSizePolicy.Expanding,QtWidgets.QSizePolicy.Expanding)FigureCanvas.updateGeometry(self)class ApplicationWindow(QtWidgets.QMainWindow):def __init__(self):QtWidgets.QMainWindow.__init__(self)self.index = 0self.dic = {}self.pointsSize = 30self.upper = 100self.lower = -100self.xx = [random.randint(self.lower, self.upper) for i in range(self.pointsSize)]self.yy = [random.randint(self.lower, self.upper) for i in range(self.pointsSize)]self.points = [[self.xx[i], self.yy[i]] for i in range(self.pointsSize)]self.points.sort(key=lambda x: (x[0], x[1]))self.setAttribute(QtCore.Qt.WA_DeleteOnClose)self.setWindowTitle("分治法生成凸包演示by18070542孙泽坤")self.main_widget = QtWidgets.QWidget(self)self.xs = []self.ys = []self.pointers = 0self.game_start()vbox = QtWidgets.QVBoxLayout(self.main_widget)self.canvas = MyMplCanvas(self.main_widget, width=6, height=6, dpi=100)  ###attention###vbox.addWidget(self.canvas)hbox = QtWidgets.QHBoxLayout(self.main_widget)self.textBrowser = QTextBrowser(self)self.button = QPushButton("下一步")self.quitButton = QPushButton("退出")self.introduceButton = QPushButton("查看凸包问题原理介绍")self.introduceButton.clicked.connect(self.introduce)self.button.clicked.connect(self.choice_point)self.quitButton.clicked.connect(self.exit_pragram)vbox.addWidget(self.button)vbox.addWidget(self.quitButton)vbox.addWidget(self.introduceButton)vbox.addWidget(self.textBrowser)self.setLayout(vbox)self.main_widget.setFocus()self.setCentralWidget(self.main_widget)self.ani = FuncAnimation(self.canvas.figure, self.update_line, interval=15)self.textBrowser.append("先把最左边和最右边的两个边界点({},{})和({},{})连接起来".format(self.points[0][0], self.points[0][1], self.points[self.pointsSize - 1][0], self.points[self.pointsSize - 1][1]))def caculate(self, x1, y1, x2, y2, x3, y3):return x1 * y2 + x3 * y1 + x2 * y3 - x1 * y3 - x2 * y1 - x3 * y2def judge(self, x1, x2, y1, y2):pta = tuple([x1, y1])ptb = tuple([x2, y2])numa = self.dic.get(pta, [])numb = self.dic.get(ptb, [])if ptb in numa or pta in numb:return Falsenuma.append(ptb)numb.append(pta)self.dic[pta] = numaself.dic[ptb] = numbreturn Truedef findUpperMax(self, x1, y1, x2, y2):flag = FalseupperMax = 0upperx = uppery = 0for i in self.points:if i[0] == x1 and i[1] == y1 or i[0] == x2 and i[1] == y2:continueareaData = self.caculate(x1, y1, x2, y2, i[0], i[1])if areaData > 0:if areaData > upperMax:flag = TrueupperMax = areaDataupperx = i[0]uppery = i[1]if flag == False:if self.judge(x1, x2, y1, y2) == False:returnself.xs.append([x1, x2])self.xs.append([y1, y2])returnif self.judge(x1, upperx, y1, uppery) == False:returnself.xs.append([x1, upperx])self.xs.append([y1, uppery])if self.judge(x2, upperx, y2, uppery) == False:returnself.xs.append([x2, upperx])self.xs.append([y2, uppery])self.findUpperMax(x1, y1, upperx, uppery)self.findUpperMax(upperx, uppery, x2, y2)def findBottomMin(self, x1, y1, x2, y2):flag = FalselowerMax = 0lowerx = lowery = 0for i in self.points:if i[0] == x1 and i[1] == y1 or i[0] == x2 and i[1] == y2:continueareaData = self.caculate(x1, y1, x2, y2, i[0], i[1])if areaData < 0:if areaData < lowerMax:flag = TruelowerMax = areaDatalowerx = i[0]lowery = i[1]if flag == False:if self.judge(x1, x2, y1, y2) == False:returnself.xs.append([x1, x2])self.xs.append([y1, y2])returnif self.judge(x1, lowerx, y1, lowery) == False:returnself.xs.append([x1, lowerx])self.xs.append([y1, lowery])if self.judge(x2, lowerx, y2, lowery) == False:returnself.xs.append([x2, lowerx])self.xs.append([y2, lowery])self.findBottomMin(x1, y1, lowerx, lowery)self.findBottomMin(lowerx, lowery, x2, y2)def scatter_points(self):self.canvas.ax.plot([self.points[0][0], self.points[self.pointsSize - 1][0]],[self.points[0][1], self.points[self.pointsSize - 1][1]], color='black')for i in range(0, self.pointsSize):self.canvas.ax.scatter(self.xx[i], self.yy[i], color='k', s=20)def game_start(self):self.findUpperMax(self.points[0][0], self.points[0][1], self.points[self.pointsSize - 1][0],self.points[self.pointsSize - 1][1])self.findBottomMin(self.points[0][0], self.points[0][1], self.points[self.pointsSize - 1][0],self.points[self.pointsSize - 1][1])def choice_point(self):self.textBrowser.clear()if self.pointers == len(self.xs):self.textBrowser.append("凸包生成完毕！点击退出键退出")returnself.ys.append(self.xs[self.pointers])self.ys.append(self.xs[self.pointers + 1])# print(self.xs[self.pointers][0], self.xs[self.pointers + 1][0],#             self.xs[self.pointers][1], self.xs[self.pointers + 1][1])text = "选择点({0},{1})和点({2},{3})，把它们连接起来" \.format(self.xs[self.pointers][0], self.xs[self.pointers + 1][0],self.xs[self.pointers][1], self.xs[self.pointers + 1][1])self.textBrowser.append(text)self.pointers += 2def update_line(self, i):self.canvas.ax.clear()self.scatter_points()for i in range(0, len(self.ys), 2):a = self.ys[i]b = self.ys[i + 1]if i == len(self.ys) - 2:self.canvas.ax.plot(a, b, color='red')else:self.canvas.ax.plot(a, b, color='black')if i == len(self.ys) - 2:self.canvas.ax.scatter(self.ys[i][0], self.ys[i + 1][0], color='red')self.canvas.ax.scatter(self.ys[i][1], self.ys[i + 1][1], color='red')def introduce(self):text = "第一步：把所有点在横坐标方向上按从小到大顺序排列，左右两个端点必定是凸包上的点\n第二步：在上凸包集合点中找一个距离直线最远的点，将它与左右端点连接起来\n第三步：重复递归求解到上半凸包的边\n第四步：下半凸包同理，通过递归求解，最终得到整个凸包"reply = QMessageBox.information(self, '分治法凸包问题原理介绍', text, QMessageBox.Yes)def exit_pragram(self):sys.exit(0)if __name__ == "__main__":App = QApplication(sys.argv)aw = ApplicationWindow()aw.show()App.exit()sys.exit(App.exec_())