计算最大圆形面积之和

Question

我有一个 n × n 整数矩阵，我想找到原点位于左上角且总和最大的圆形区域。考虑以下带有圆圈的网格。

这是用以下材料制成的：

import matplotlib.pyplot as plt
from matplotlib.patches import Circle
import numpy as np
plt.yticks(np.arange(0, 10.01, 1))
plt.xticks(np.arange(0, 10.01, 1))
plt.xlim(0,9)
plt.ylim(0,9)
plt.gca().invert_yaxis()
# Set aspect ratio to be equal
plt.gca().set_aspect('equal', adjustable='box')
plt.grid()   
np.random.seed(40)
square = np.empty((10, 10), dtype=np.int_)
for x in np.arange(0, 10, 1):
    for y in np.arange(0, 10, 1):
        plt.scatter(x, y, color='blue', s=2, zorder=2, clip_on=False) 
for x in np.arange(0, 10, 1):
    for y in np.arange(0, 10, 1):
        value = np.random.randint(-3, 4)
        square[int(x), int(y)] = value
        plt.text(x-0.2, y-0.2, str(value), ha='center', va='center', fontsize=8, color='black')

r1 = 3
circle1 = Circle((0, 0), r1,  color="blue", alpha=0.5, ec='k', lw=1)
plt.gca().add_patch(circle1)

在这种情况下，矩阵是：

[[ 3  0  2 -3 -3 -1 -2  1 -1  0]
 [-1  0  0  0 -2 -3 -2  2 -2 -3]
 [ 1  3  3  1  1 -3 -1 -1  3  0]
 [ 0  0 -2  0  2  1  2  2 -1 -1]
 [-1  0  3  1  1  3 -2  0  0 -1]
 [-1 -1  1  2 -3 -2  1 -2  0  0]
 [-3  2  2  3 -2  0 -1 -1  3 -2]
 [-2  0  2  1  2  2  1 -1 -3 -3]
 [-2 -2  1 -3 -2 -1  3  2  3 -3]
 [ 2  3  1 -1  0  1 -1  3 -2 -1]]

当圆的半径为3时，圆内的网格中有11个点。随着半径的增加，越来越多的点落入圆中。

我正在寻找一种快速的方法来找到一个半径，使其内的网格点的整数之和最大化。半径不会是唯一的，因此任何使总和最大化的半径都可以。我最终会想用更大的矩阵来做到这一点。

这个问题相关，但我不确定如何将其扩展到我的新问题。

Answer 1

在我看来，pandas DataFrame 是完成此任务的完美数据结构。以下是我如何重新构建此问题设置以使其存在于 df 中：

from itertools import product

x = np.arange(0,10,1)
y = np.arange(0,10,1)
xy = list(product(x,y))

df = pd.DataFrame(xy, columns=['x', 'y'])
df['score'] = np.random.randint(-3,4,len(df))

我们应该有网格上的每个点以及与之相关的分数。现在我们需要找出网格上的每个点距离原点（也是我们圆的中心点）有多远

df['distance'] = (df['x']**2 + df['y']**2)**0.5
df = df.sort_values(by='distance')

现在网格上的每个点都按距原点的距离升序排序。此时，我们可以直接跳转到与每个点相关的分数的累积总和，并找到该累积总和何时达到最大值。但是，当网格上的多个点与原点共享一定距离时，我们可以添加一个额外的步骤来处理，将它们的分数折叠到同一行中，以获得累积总和的好处。

df = df.groupby('distance')['score'].sum().reset_index()

现在是我们的累计总和。

df['cumulative_score'] = df['score'].cumsum()

我们可以找到

df['cumulative_score']

的 argmax 或将其绘制成视觉效果。在我们的例子中（给定我们随机生成的数据），答案是半径 2 和 3 之间的平局，得出的总和在 3 的圆内。

plt.plot(df['distance'], df['cumulative_score'])