python画图：小圆覆盖大圆问题
2021-08-06 19:56:43
小圆覆盖大圆
用至少多少个半径为r的小圆覆盖半径为R的大圆
是的任意两个小圆圆心距离为根号3r，且任意三个圆之间交于一点
python实现：
import numpy as npimport matplotlib.pyplot as pltdef circle1(p,r,theta):''' p为列表，原点 r为半径 ''' X = p[0] + r * np.cos(theta) Y = p[1] + r * np.sin(theta) plt.plot(X, Y)# ==========================================# 圆的基本信息# 1.圆半径R = 1000r = 60.5test_r1 = r * np.sqrt(3)theta = np.arange(0, 2*np.pi, 0.01)# 2.圆心坐标a, b = (0., 0.)# ==========================================X = a + R * np.cos(theta)Y = b + R * np.sin(theta)plt.plot(X, Y)X = a + r * np.cos(theta)Y = b + r * np.sin(theta)plt.plot(X, Y)p = []clo = 0clo_old = 0clo_a = 0# 奇数列for j in range(1, 12, 2): clo += 2 clo_a = 0 for i in range(1, 20, 2): p.append([j*r*3/2, i*test_r1/2]) p.append([j*r*3/2, -i*test_r1/2]) p.append([-j*r * 3 / 2, i * test_r1 / 2]) p.append([-j*r * 3 / 2, -i * test_r1 / 2]) clo_a +=2# 偶数列for i in range(0, 12, 2): clo += 2 clo_old = 0 for j in range(11): p.append([i*r*3/2, j*test_r1]) p.append([i*r*3/2, -j*test_r1]) p.append([-i * r * 3 / 2, j * test_r1]) p.append([-i * r * 3 / 2, -j * test_r1]) clo_old += 2print('总列数：%d' % (clo-1))print('偶数列：%d' % (clo_old-1))print('奇数列：%d' % clo_a)for p1 in p: circle1(p1, r, theta)# ==========================================plt.show()
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
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
最终结果为：
修改一下，去掉多余小圆
import numpy as npimport matplotlib.pyplot as pltdef circle1(p,r,theta):
X = p[0] + r * np.cos(theta)
Y = p[1] + r * np.sin(theta)
plt.plot(X, Y)# ==========================================# 圆的基本信息# 1.圆半径R = 1000r = 60.5test_r1 = r * np.sqrt(3)theta = np.arange(0, 2*np.pi, 0.01)# 2.圆心坐标a, b = (0., 0.)# ==========================================X = a + R * np.cos(theta)Y = b + R * np.sin(theta)plt.plot(X, Y)X = a + r * np.cos(theta)Y = b + r * np.sin(theta)plt.plot(X, Y)p = []clo = 0clo_old = 0clo_a = 0# 奇数列for j in range(1, 12, 2):
clo += 2
clo_a = 0
for i in range(1, 20, 2):
p.append([j*r*3/2, i*test_r1/2])
p.append([j*r*3/2, -i*test_r1/2])
p.append([-j*r * 3 / 2, i * test_r1 / 2])
p.append([-j*r * 3 / 2, -i * test_r1 / 2])
clo_a +=2# 偶数列for i in range(0, 12, 2):
clo += 2
clo_old = 0
for j in range(11):
p.append([i*r*3/2, j*test_r1])
p.append([i*r*3/2, -j*test_r1])
p.append([-i * r * 3 / 2, j * test_r1])
p.append([-i * r * 3 / 2, -j * test_r1])
clo_old += 2count = 0for p1 in p:
if p1[0]*p1[0]+p1[1]*p1[1] <= 1000000:
count += 1
circle1(p1, r, theta)
elif p1[0]*p1[0]+p1[1]*p1[1] <= (1000+60.5)*(1000+60.5):
count += 1
circle1(p1,r,theta)# ==========================================plt.show()1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636412345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
结果如图：
综合各个元素最终修改版
import numpy as npimport matplotlib.pyplot as pltimport math# 求两圆交点def insec(p1, r1, p2, r2): x = p1[0] y = p1[1] R = r1 a = p2[0] b = p2[1] S = r2 c = (a - x) ** 2 + (b - y) ** 2 d = np.sqrt(c) if (d > (R + S)) or d < (abs(R - S)): # print('Two circles have no intersection') return None, None elif d.all == 0: # print('Two circles have same center!') return None, None else: A = (R ** 2 - S ** 2 + d ** 2) / (2 * d) h = np.sqrt(R ** 2 - A ** 2) x2 = x + A * (a - x) / d y2 = y + A * (b - y) / d x3 = round(x2 - h * (b - y) / d, 2) y3 = round(y2 + h * (a - x) / d, 2) x4 = round(x2 + h * (b - y) / d, 2) y4 = round(y2 - h * (a - x) / d, 2) c1 = [x3, y3] c2 = [x4, y4] return c1, c2# 判断一点是否在(0,0)大圆内def in_circle(p, r): n = p[0] ** 2 + p[1] ** 2 if n < r ** 2: return True else: return False# 画圆def circle1(p, r, theta): X = p[0] + r * np.cos(theta) Y = p[1] + r * np.sin(theta) plt.plot(X, Y)# 判断重复画第几象限的圆def re_circle(p, r, theta): if p[0] == 0: # (0,0) 位置画一个 if p[1] == 0: circle1([p[0], p[1]], r, theta) # print('(%.3f,%.3f)' % (p[0], p[1])) return 1 # 0列之重复画上下两个 else: circle1([p[0], p[1]], r, theta) # print('(%.3f,%.3f)' % (p[0], p[1])) circle1([p[0], -p[1]], r, theta) # print('(%.3f,%.3f)' % (p[0], -p[1])) return 2 # y=0的小圆只需要画x周上的两个 elif y1[i] == 0: circle1([p[0], p[1]], r, theta) # print('(%.3f,%.3f)' % (p[0], p[1])) circle1([-p[0], p[1]], r, theta) # print('(%.3f,%.3f)' % (-p[0], p[1])) return 2 # 第一象限内的需要画四个 else: circle1([p[0], p[1]], r, theta) # print('(%.3f,%.3f)' % (p[0], p[1])) circle1([p[0], -p[1]], r, theta) # print('(%.3f,%.3f)' % (p[0], -p[1])) circle1([-p[0], p[1]], r, theta) # print('(%.3f,%.3f)' % (-p[0], p[1])) circle1([-p[0], -p[1]], r, theta) # print('(%.3f,%.3f)' % (-p[0], -p[1])) return 4# ==========================================# 圆的基本信息# 1.圆半径R = 1000r = 30.5test_r1 = r * np.sqrt(3)theta = np.arange(0, 2 * np.pi, 0.01)n = math.ceil(R/(3*r/2))+1# 2.圆心坐标# ==========================================# 画大圆fig = plt.figure()axes = fig.add_subplot()axes.axis('equal')X = R * np.cos(theta)Y = R * np.sin(theta)plt.plot(X, Y)# 每列x，y坐标x1 = [0.] * n y1 = [0.] * n N = [0] *n# 存取每一列初始圆的圆心for i in range(n): x1[i] = i * r * 3 / 2 if i % 2: y1[i] = test_r1 / 2 else: y1[i] = 0# count存放小圆数量count = 0for i in range(n): c = insec([x1[i], y1[i]], r, [0, 0], R) # 当x坐标表示的小圆和大圆没有交点但圆心在大圆内，或者小圆与大圆有焦点的时候则考虑该列 # 否则从该列开始就不需要进行循环 if (c == (None, None) and x1[i]**2 + y1[i]**2 < 1000**2) or c != (None, None): for j in range(n): c = insec([x1[i], y1[i]], r, [0, 0], R) if c == (None, None): if x1[i]**2 +y1[i]**2 < 1000**2: N[i] += re_circle([x1[i], y1[i]], r, theta) else: count += N[i] if i != 0: N[i] /= 2 y1[i] = temp break else: # # 求(x1[i],y1[i])圆与下面的一个圆的交点 # c = insec([x1[i], y1[i]], r, [x1[i], ], R) N[i] += re_circle([x1[i], y1[i]], r, theta) temp = y1[i] y1[i] += test_r1 else: break# ==========================================plt.axhline(0, -1111, 1111)plt.axvline(0, -1111, 1111)print(count)# for i in range(len(x1)):# print('(%.3f,%.3f)' % (x1[i], y1[i]))# for i in range(len(N)):# print('%d' % int(N[i]))plt.show()
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
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
结果：
点击阅读全文
打开CSDN，阅读体验更佳
Python实现小圆覆盖大圆问题
问题回顾 给定一个半径为10m的圆，和若干半径为1m的小圆（小圆个数足够多），现在要用若干小圆来覆盖这个大圆。问至少需要多少个小圆才能覆盖这个半径为10m的圆？ 求解思路 为保证小圆数量最小，既圆与圆之间不重叠，既相切情况。 因为需要考虑大圆与小圆之间的间隙，也要考虑小圆与小圆之间的间隙。 故只能采取近似思想进行计算。 1、当r<R<2r时，n=1; 2、当2r<=R<2.1547r时，n=2; 3、... 浏览器打开
最小圆覆盖问题 算法步骤与证明+代码模板
最小圆覆盖定义 最小圆覆盖问题是什么呢？就是指在二维平面上有一堆点，然后我们要求一个最小半径的圆能够将所有点全部都包住，这就是最小圆覆盖问题。 最小覆盖圆的性质 性质1：最小覆盖圆是唯一的 证明：我们假设有两个圆O1，O2，他们半径都是r，都是最小覆盖圆，那么所有的点一定在两圆的交集部分。那我们以两圆交集部分的弦长为直径，做一个新圆，该圆依旧包含所有点，而且他的直径是原来圆的弦长，一定是小于原来圆的直径的，因此和原来的圆是最小覆盖圆相矛盾，所以最小覆盖圆是唯一的。 性质2：若圆O1是点集S的最小覆盖圆，则 浏览器打开
赞 (0)