星辰物语的个人博客

Personal blog of StarStory

0%

最小覆盖圆

发表于 更新于 分类于 ，

本算法实现了给定点集 求出能够覆盖所有点的最小圆

最小覆盖圆算法

Python版

前置算法

1.检验算法

1
2
3
4
5
6
7
8
9
10
def jc(p, r, c):
    '''
    检查点p是否在以r为半径 c为圆心的圆内
    :param p: 二元元组 检查点坐标
    :param r: 数字 圆半径
    :param c: 二元元组 圆心坐标
    :return: True:是 False:不在
    '''
    d = math.sqrt((p[0] - c[0]) ** 2 + (p[1] - c[1]) ** 2)
    return d < r

算法使用两点距离公式求取点到圆心距离 然后与半径比较 判断点是否在目标圆内

2.二点生成圆

1
2
3
4
5
6
7
8
9
10
def y2(p1, p2):
    '''
    二点生成圆
    :param p1: 点1 二元 元组 该点坐标
    :param p2: 点2
    :return: 半径 圆心坐标
    '''
    r = math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) / 2
    c = ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
    return r, c

二点生成圆算法十分简单 两点连线中点就是圆心 连线长度就是直径

3.三点生成圆

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
def solfun(a, b, c, d, e, f):
    '''
    解方程|a b| |e|
         |c d| |f|
    :param a: 解方程参数
    :param b:
    :param c:
    :param d:
    :param e:
    :param f:
    :return: 方程的解
    '''
    t = a * d - b * c
    x = (d * e - b * f) / t
    y = (a * f - c * e) / t
    return x, y


def y3(p1, p2, p3):
    '''
    三点构建圆
    :param p1:点1 二元元组 该点坐标
    :param p2: 点2
    :param p3: 点3
    :return: 半径 圆心坐标 如果构建失败返回False
    '''
    e = (p2[0] ** 2 - p1[0] ** 2 + p2[1] ** 2 - p1[1] ** 2) / 2
    f = (p3[0] ** 2 - p2[0] ** 2 + p3[1] ** 2 - p2[1] ** 2) / 2
    try:
        c = solfun(p2[0] - p1[0], p2[1] - p1[1], p3[0] - p2[0], p3[1] - p2[1], e, f)
    except:
        return False
    r = math.sqrt((p1[0] - c[0]) ** 2 + (p1[1] - c[1]) ** 2)
    return r, c

分为两个部分 第一部分solfun()求取形似
$$
ax+by=e\
cx+dy=f
$$
方程的解

第二部分使用公式

公式推导

首先假设所求圆心为$x_0,y_0$ 半径为r 得
$$
(x_1-x_0)^2+(y_1-y_0)^2=r^2①\
(x_2-x_0)^2+(y_2-y_0)^2=r^2②\
(x_3-x_0)^2+(y_3-y_0)^2=r^2③
$$
展开后③式-②式 ②式-①式
$$
\frac{x_2^2-x_1^2+y_2^2-y_1^2}2=(x_2-x_1)x_0+(y_2-y_1)y_0\
\frac{x_3^2-x_2^2+y_3^2-y_2^2}2=(x_3-x_2)x_0+(y_3-y_2)y_0
$$
求出abcdef参数 并带入公式求解

得到圆心 再与任一点求距离 得半径

主函数

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
def main():
    a = []
    global image
    image = np.zeros((800,800,3), np.uint8)
    for t in range(1, 50):
        a.append((random.random() * 400, random.random() * 400))
    for t in a:
        image = cv2.circle(image,(int(t[0])+100,int(t[1])+100),3,(0,255,255))


    random.shuffle(a)

    ct = (0, 0)
    r = 0

    b = []
    for p1 in a:
        if not jc(p1, r, ct):
            ct = p1
            r = 0
            c = []
            for p2 in b:
                if not jc(p2, r, ct):
                    r, ct = y2(p1, p2)
                    for p3 in c:
                        if not jc(p3, r, ct):
                            r, ct = y3(p1, p2, p3)
                c.append(p2)
        b.append(p1)
    print(ct, r)
    image = cv2.circle(image,(int(ct[0])+100,int(ct[1])+100),int(r),(255,255,255))
    cv2.imshow('a',image)
    cv2.waitKey(0)

2-8行生成一个随机点数列

11行对数列随机排序

13-29行为主要逻辑

分析

使用p1遍历a中所有点 如果发现某点p1不在当前圆中 说明p1在p1之前的点中一定是边点

接着重新遍历p1之前的点 如果发现某点p2不在当前圆中 说明p2在p2之前的点中一定是第二个边点

接着重新遍历p2之前的点 如果发现某点p3不在当前圆中 说明p3在p3之前的点中一定是第三个边点

以上三种情况 如果发现搜索点在当前圆中 则直接跳过

直到遍历完成 寻找到三个或两个边点和一个最小圆