-
Notifications
You must be signed in to change notification settings - Fork 0
/
quickcvx_vis.py
293 lines (266 loc) · 9.17 KB
/
quickcvx_vis.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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
#！python
#code = utf-8
"""
快速凸包算法的可视化分析
Author:MokeyDChaos
Date:2019-04-15
Version:1.1
"""
import random
import math
import operator
import matplotlib.pyplot as plt
import copy
import time
def SortList(elem):
"""
对列表进行排序时使用
"""
return elem[0]
def GenerScatter(num):
"""
生成一定数量的随机整数坐标点
@num:随机点的数量
@return:坐标点的数组
"""
random_sca_list = []
for i in range(num):
ran_num = (random.randint(-100, 100), random.randint(-100, 100))
random_sca_list.append(ran_num)
return random_sca_list
def GetLine(point1, point2, flag = None):
"""
求出过两点的直线Ax + By + C = 0
@point1:直线经过的一个点
@point2:直线经过的另一个点
@return：[A, B, C]
"""
A = (point1[1] - point2[1])
B = (point2[0] - point1[0])
C = point1[0] * point2[1] - point1[1] * point2[0]
return [A, B, C]
def PointDisLine(point, line):
"""
点到线的距离
@point:点
@line:线
@return:距离 dis
"""
return (line[0] * point[0] + line[1] * point[1] + line[2]) / math.sqrt(line[0] * line[0] + line[1] * line[1])
def PointDivison(point_set, line, cvxhu_point):
"""
直线将坐标点集划分为两个
@point_set:坐标点集合
@line:线
@cvx:_point:凸包点
@return:pos_set, neg_set
"""
pos_set = []
neg_set = []
for i in range(len(point_set)):
dis = PointDisLine(point_set[i], line)
if dis > 0:
pos_set.append(point_set[i])
elif dis < 0:
neg_set.append(point_set[i])
return pos_set, neg_set
def PointSearch(point_set, line, cvxhu_point):
"""
寻找点集中到直线最远的点
@point_set:作标点
@line:线
@cvxhu_point:凸包点集合
@return:最远的点point
"""
max_dis = 0
max_point = (0, 0)
j = []
for i in range(len(point_set)):
dis = abs(PointDisLine(point_set[i], line))
# print('point', point_set[i], 'dis', dis)
if max_dis < dis:
max_dis = dis
max_point = point_set[i]
# 如果为0说明它已经在凸包点集合中了
if dis == 0:
j.append(i)
# 这里多个点相等的情况下我们是取数组中第一个点
cvxhu_point.append(max_point)
if len(j):
point_set.remove(point_set[j[0]])
point_set.remove(max_point)
return max_point
def CvxSearchSm(point_set, cvxhu_point, line):
"""
在点集中寻找凸包点
@point_set:坐标点集合
@cvxhu_point:凸包点集合
@line:存放寻找基线经过的两个点的数组
"""
# 一定要注意python中赋值、浅拷贝、深拷贝之间的区别呀
flag = point_set
# 最初的基线
base_line = GetLine(line[0], line[1])
fir_point = PointSearch(flag, base_line, cvxhu_point)
for i in range(len(line)):
# 更新递归需要的点集合，和线
line_set = [line[i], fir_point]
temp_line = GetLine(line[i], fir_point)
# 和基线首尾相连的划分线
judge_line = GetLine(line[1 - i], line[i])
temp_flag = copy.copy(flag)
while len(temp_flag) >= 1 :
sub_po_set, sub_neg_set = PointDivison(temp_flag, temp_line, cvxhu_point)
# 使用距离之间是否同号来判断点在哪一侧,这里一定注意让两个向量是首尾相连
if len(sub_neg_set):
if len(sub_po_set):
# 使用距离的乘积的正负来判断哪一个点集是我们需要的
if PointDisLine(sub_neg_set[0], temp_line) * PointDisLine(sub_neg_set[0], judge_line) > 0:
temp_flag = sub_po_set
elif PointDisLine(sub_neg_set[0], temp_line) * PointDisLine(sub_neg_set[0], judge_line) < 0:
temp_flag = sub_neg_set
else:
print('程序错误点位于线上')
else:
if PointDisLine(sub_neg_set[0], temp_line) * PointDisLine(sub_neg_set[0], judge_line) < 0:
temp_flag = sub_neg_set
else:
temp_flag = []
else:
if len(sub_po_set):
if PointDisLine(sub_po_set[0], temp_line) * PointDisLine(sub_po_set[0], judge_line) < 0:
temp_flag = sub_po_set
else:
temp_flag = []
else:
temp_flag = []
CvxVis(flag, list(set(cvxhu_point)), line[i], fir_point, temp_flag)
# 这里因为flag的赋值不是实时受temp控制，所以加入判断防止错误点进入凸包集
if len(temp_flag) > 1:
# print('开始递归')
CvxSearchSm(temp_flag, cvxhu_point, line_set)
# 递归后因为递归函数会继续执行之前不成立判断下的内容，这里判断如果要搜索的点集已经存在于凸包集合我们就将搜索点集赋值为空集
if len(list(set(cvxhu_point).intersection(flag))):
temp_flag = []
if len(temp_flag) == 1:
cvxhu_point.append(temp_flag[0])
temp_flag = []
def CvxVis(point_set, cvxhu_point = None, point1 = None, point2 = None, marked_pointset = None):
"""
将凸包可视化，用来检验算法正确性
@point_set:坐标点
@cvxhu_point:凸包点集合
@point1,point2:用来检验算法正确性的，无意义
"""
p_x = []
p_y = []
c_x = []
c_y = []
a = []
b = []
mk_x = []
mk_y = []
# 这里对凸包点集重新排列方便可视化检验程序正确性
if cvxhu_point:
for each in cvxhu_point:
if each[1] > 0:
a.append(each)
else:
b.append(each)
a.sort(key = SortList)
b.sort(key = SortList, reverse = True )
cvxhu_point = a + b
# 使凸包相连
if len(a):
cvxhu_point.append(a[0])
else:
cvxhu_point.append(b[len(b)-1])
for i in range(len(cvxhu_point)):
c_x.append(cvxhu_point[i][0])
c_y.append(cvxhu_point[i][1])
plt.scatter(c_x, c_y, c = 'r')
plt.plot(c_x, c_y, c = 'b')
for i in range(len(point_set)):
p_x.append(point_set[i][0])
p_y.append(point_set[i][1])
plt.scatter(p_x, p_y, c = 'r', marker = 'x')
if point1:
plt.plot([point1[0], point2[0]], [point1[1], point2[1]], c = 'g')
if marked_pointset:
for i in range(len(marked_pointset)):
mk_x.append(marked_pointset[i][0])
mk_y.append(marked_pointset[i][1])
plt.scatter(mk_x, mk_y, c = 'g', marker = '*')
plt.show()
def FunctionForClasswork():
"""
对不同规模的数据统计快包算法的运行时间并绘制N-T表格和曲线图
"""
n = 10
N = []
T = []
while n < 10000:
n = n * 2
a = GenerScatter(n)
a.sort(key = SortList)
cvxhu_point = [a[0], a[len(a)-1]]
first_line = GetLine(a[0], a[len(a)-1])
# 分为两个点集
po_set, neg_set = PointDivison(a, first_line, cvxhu_point)
# 作为凸包点集合
cvxhu_po = copy.copy(cvxhu_point)
cvxhu_neg = copy.copy(cvxhu_point)
# 作为基线经过点集合
cvxhu_po1 = copy.copy(cvxhu_point)
cvxhu_neg1 = copy.copy(cvxhu_point)
# 开始计时
time_start = time.time()
# 分别搜索两个点集中的凸包点
if len(po_set):
CvxSearchSm(po_set, cvxhu_po, cvxhu_po1)
if len(neg_set):
CvxSearchSm(neg_set, cvxhu_neg, cvxhu_neg1)
# 合并两个凸包点集合
cvxhu_point = list(set(cvxhu_po + cvxhu_neg))
#结束计时
time_end = time.time()
N.append(n)
T.append(time_end - time_start)
print('N:', N)
print('T:', T)
plt.plot(N, T)
plt.title('N-T figure')
plt.xlabel('N')
plt.ylabel('T')
plt.show()
def main():
a = GenerScatter(20)
CvxVis(a)
# 生成10个散点
cvxhu_point = []
# 按x轴排序
a.sort(key = SortList)
cvxhu_point = [a[0], a[len(a)-1]]
first_line = GetLine(a[0], a[len(a)-1])
# 分为两个点集
po_set, neg_set = PointDivison(a, first_line, cvxhu_point)
# 作为凸包点集合
cvxhu_po = copy.copy(cvxhu_point)
cvxhu_neg = copy.copy(cvxhu_point)
# 作为基线经过点集合
cvxhu_po1 = copy.copy(cvxhu_point)
cvxhu_neg1 = copy.copy(cvxhu_point)
# 分别搜索两个点集中的凸包点
CvxVis(a, point1 = a[0], point2 = a[len(a)-1], marked_pointset = po_set)
if len(po_set):
CvxSearchSm(po_set, cvxhu_po, cvxhu_po1)
CvxVis(a, point1 = a[0], point2 = a[len(a)-1], marked_pointset = neg_set)
if len(neg_set):
CvxSearchSm(neg_set, cvxhu_neg, cvxhu_neg1)
# 合并两个凸包点集合
cvxhu_point = list(set(cvxhu_po + cvxhu_neg))
print(cvxhu_point)
CvxVis(a, cvxhu_point)
# FunctionForClasswork()
if __name__ == "__main__":
main()