-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.py
94 lines (73 loc) · 2.76 KB
/
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
from PyQt5.QtWidgets import *
from PyQt5.QtGui import *
from PyQt5.QtCore import *
class Widget(QWidget):
def __init__(self):
super().__init__()
self.points = []
self.points_pos = []
self.hull = []
self.draw_convex = False
def keyPressEvent(self, e):
if e.modifiers() & Qt.ControlModifier and e.key() == Qt.Key_L:
self.points = []
self.points_pos = []
self.hull = []
self.draw_convex = False
self.update()
def mousePressEvent(self, event):
if event.button() == Qt.LeftButton:
self.points.append(event.pos())
self.points_pos.append((event.pos().x(), event.pos().y()))
if event.button() == Qt.RightButton:
print(self.andrew(self.points_pos))
self.hull = self.andrew(self.points_pos)
self.draw_convex = True
self.update()
def paintEvent(self, event):
super().paintEvent(event)
if not self.points:
return
painter = QPainter(self)
painter.setPen(QPen(Qt.black, 4.0))
for i in range(len(self.points)):
painter.drawPoint(QPoint(self.points[i]))
painter.setPen(QPen(Qt.blue, 2.0))
if self.draw_convex:
for i in range(len(self.hull)):
if ((self.hull[i][0], self.hull[i][1]) == self.rightmost_point):
painter.setPen(QPen(Qt.green, 2.0))
painter.drawLine(QPoint(self.hull[i][0], self.hull[i][1]),
QPoint(self.hull[(i + 1) % len(self.hull)][0], self.hull[(i + 1) % len(self.hull)][1]))
def andrew(self, points):
points = sorted(set(points))
if len(points) <= 1:
return points
"""
Векторное произведение.
> 0, если правый поворот
< 0, если левый поворот
= 0, ecли коллинеарные
"""
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
# Строим нижнюю оболочку
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
# Строим верхнюю оболочку
self.rightmost_point = points[-1]
print(self.rightmost_point)
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]
if __name__ == '__main__':
app = QApplication([])
w = Widget()
w.show()
app.exec()