寻找二维空间中最大的空圆形区域

Question

给定一个由圆形（灰色）占据的二维空间，是否有一种简单的方法可以找到最大的空圆形区域（蓝色）？我想我必须考虑空间划分，也许是四叉树，但我很好奇是否存在现有的解决方案，特别是对于圆形形状？

我的想法（既没有经过深思熟虑也没有实施，而且计算成本很高）：

1. 将空间划分为网格，越细越精确
2. 在每个网格点，计算 D，到任何相邻圆 C_i 的最小距离（= 到 C_i 中心的距离 - C_i 的半径）
3. 选择使 D 最大化的网格点

Answer 1

我通过制作二值图像，然后使用“Delaunay”转换坐标以生成三角剖分，解决了类似的问题，这与 Voronoi 曲面细分的原理相同，但不是单独的多边形，而是对每个点（像素）等距离进行三角剖分。 然后代码计算所有顶点的外心，最后计算最大的：

# Convert 255 to 1
z[z == 255] = 1

# Now, 'z' represents the binary image with values 0 and 1
binary_image = z

# Extract coordinates of points (where binary_image == 1)
points_y, points_x = np.where(binary_image == 1)
points = np.column_stack((points_x, points_y))

# Compute Delaunay triangulation
tri = Delaunay(points)

# Compute Voronoi diagram
vor = Voronoi(points)

# Calculate circumcenter distances and radii
circumcenter_distances = []
radii_data = {'Circumcenter': [], 'Radius': []}

for i, simplex in enumerate(tri.simplices):
    circumcenter = np.mean(tri.points[simplex], axis=0)

    # Calculate distances from the circumcenter to all vertices
    vertex_distances = [distance.euclidean(circumcenter, vertex) for vertex in tri.points[simplex]]

    circumcenter_distances.append(vertex_distances)

    # Find the minimum distance to any vertex as the radius
    min_distance = min(vertex_distances)
    radii_data['Circumcenter'].append(circumcenter)
    radii_data['Radius'].append(min_distance)

# Convert the data to a pandas DataFrame
radii_df = pd.DataFrame(radii_data)

# Find the largest empty circle
largest_empty_circle = radii_df.loc[radii_df['Radius'].idxmax()]

该代码适用于不对称形状，所以我认为它适用于圆形