找到最佳的裁剪圆

Question

给定一个 n × n 整数矩阵，我想找到使总和最大化的剪裁圆。这是一张图片，然后是解释/代码：

圆的圆心在(0,0)，我们只对与网格相交的部分感兴趣。网格中的每个整数坐标都有一个整数。圆可以有任何半径（不一定是整数半径，但下面会详细介绍）。

还有一条对角线可能会夹住圆圈，如图所示。对角线始终以网格边界上的整数坐标开始和结束，并向下和向右与水平线成 45 度角，如图所示。

剪裁圆的分数是圆内和对角线一侧（包括（0,0））的所有整数的总和。在图中，这将包括边界上（或靠近边界）的 3, 1, -2, -2, 0, -3, -3, 0, 3, 0 以及靠近 (0, 0) 的所有内容。

尽管圆可以有任意半径，但我们只需要考虑与网格点精确相交的圆，因此有 n^2 个不同的相关半径。此外，我们只需要记录圆与对角线相交的一个位置即可完全指定剪切的圆。如果最优解根本没有对角线剪切圆，那么我们只需要返回圆的半径。

如果我们只想找到最佳圆，我们可以在与输入大小成比例的时间内快速完成：

import numpy as np
from math import sqrt
np.random.seed(40)

def find_max(A):
    n = A.shape[0]
    sum_dist = np.zeros(2 * n * n, dtype=np.int32)
    for i in range(n):
        for j in range(n):
            dist = i**2 + j**2
            sum_dist[dist] += A[i, j]
    cusum = np.cumsum(sum_dist)
    # returns optimal radius with its score
    return sqrt(np.argmax(cusum)), np.max(cusum)
A = np.random.randint(-3, 4, (10, 10))
print(find_max(A))

多快可以找到最佳裁剪圆？

Answer 1

首先创建累积频率表或芬威克树。您将获得每个圆半径的记录，其值对应于距原点该距离处的探索权重。然后，从原点开始BFS。

对于每个对角“边界”，您需要使用半径：权重键值对更新表/树（向现有值添加权重）。然后，您还需要在表/树中查询刚刚添加的每个半径处的当前累积总和，记下最大值并相应地更新全局运行最大值。

搜索结束后，您将获得剪贴圆的最大总和。如果你想重建圆，只需存储最大半径和 BFS 深度以及全局最大和本身。

这将在

O(N^2 log N)

时间内为您提供解决方案，因为将会有 N^2 次更新和查询，每个都是

O(log N)

。

这个解决方案背后的直觉是，通过沿着这个对角线“边界”向外探索，您隐式地剪切了您查询的所有圆圈，因为它上面/右侧的权重尚未添加。通过计算刚刚更新的半径的最大值（在每个搜索深度），您还可以强制约束圆与裁剪线在整数坐标处相交。