在给定起点 (numpy) 的情况下，找到适合一组点的最大圆

Question

给定一个起点(82, 186)和周围点[(105, 186), (95, 157), (81, 159), (64, 173), (52, 188), (127, 195)]集合，如何确定适合这些点的最大圆？

注意：中心不必是起点

cX, cY = (82, 186)
points = [(105, 186), (95, 157), (81, 159), (64, 173), (52, 188), (127, 195)]
def closest_node(node, nodes):
    nodes = np.asarray(nodes)
    deltas = nodes - node
    dist = np.linalg.norm(deltas, axis=1)
    min_idx = np.argmin(dist)
    return nodes[min_idx], dist[min_idx], deltas[min_idx][1]/deltas[min_idx][0]  # point, distance, slope
(pX, pY), d, m = closest_node((cX, cY), points)
cv2.circle(img, (cX, cY), int(d), (255, 0, 255), 1)  # circle with center C, touching point P
# learning rate
a = 0.2
# sign for direction
sX = 1 if cX - pX > 0 else -1
sY = 1 if cY - pY > 0 else -1
dx = (d * a) * np.sqrt(1 / (1 + m**2))
# New center
nX = cX + sX * dx
nY = cY + sY * m * dx
cv2.circle(img, (int(nX), int(nY)), int(d + (d * a)), [0, 0, 0], 1)

所以我试图迭代地接近第二点(然后是第三点(，但我认为如果有矢量化的方法会更好。我该怎么做？

编辑：使用Voronoi的解决方案

from scipy.spatial import Voronoi
points = np.array(points)
if len(points) >= 4:
    vor = Voronoi(points)
    max_d = 0
    max_v = None
    for v in vor.vertices:
        cv2.circle(img, (int(v[0]), int(v[1])), 3, [200, 200, 0], 1)
        _, d, _ = closest_node(v, points)
        if d > max_d:
            max_d = d
            max_v = v
    cv2.circle(img, (int(max_v[0]), int(max_v[1])), int(max_d), [0, 0, 0], 1)

Answer 1

这是

找到最大的内切圆的问题(而它的中心位于点云的凸包内(。

它可能在O(nlogn(时间内使用Voronoi图来解决。

对于蟒蛇 - scipy包含Voronoi例程