计算二维图中 even/odd 个数字的总数

Question

我有一个尺寸为 M x N 的图表。
我也有两点[X,Y]
和范围r

我们只能水平或垂直移动 1 space（我们总是要移动）。我们的目标是找到我们可以达到的可能性总数。

在此示例中，我们有 M=5、N=4、[X=2、Y=1] 和 r=3。

我们可以看到，r是一个奇数，所以我们要搜索奇数。结果显然是（所有奇数相加后）12

我首先尝试了暴力破解，但它太慢了 (O(n^2))。

所以我在数学上进行了更多尝试。我尝试了 Von Neumann Neighborhood 算法，但我完全被困在那里。最后，我通过计算对应于 x 和 y 的行中的垂直和水平计数来尝试它（x 中的计数是 3，[=25 中的计数=] 是 3).

我的下一步是找到拐角并使用 Taxicab geometry 计算到达那里需要多少 r 秒。

然后我将图像分成 4 个部分（象限）。当从[X, Y]到给定象限角的路径小于r时，只需将方格数除以2。当路径较大时，我创建r_，即由 path to corner 与 r → r_ = taxicab - r 的差异决定。然后从矩形的内容中减去 r_ 并再次除以 2。

可以看到，结果也正确的出来了，3 + 3 + 1 + 1 + 2 + 2 = 12.

但是

在此请教：

我们仍在处理偶数和奇数，因此在除以奇数后经常会出现舍入错误2.（例如 M=2, N=4, X=0, Y=0, r=4 - 见图片。有 8 个字段 - 3 个空白。但是 5/2 是 2.5 => 为什么取 3 而不是 2？我尝试添加不同的规则，但它与示例不同例如。）
对于这样的计算，是否有更高效的算法同样快速且不易出错？

Answer 1

我们可以计算位于网格之外的方块，然后从范围内的 odd/even 个方块总数中减去这些方块（不考虑 in/out 的边界）。

这实际上比我们想象的要容易。首先，我们希望能够计算范围内 odd/even 方格的数量，而不考虑边界。使用 N - S = N * (N + 1) / 2 以内自然数之和的公式，我们可以推导出几个简单的方程式：

def count_all(size):
    if size % 2:  # odd size
        return (size + 1) ** 2
    return size * (size + 2) + 1

尝试自己推导出这些可能是一个很好的练习，或者至少用几个例子验证它们实际上是正确的。

继续 - 我们可以通过“缩小”我们的半径来消除从上方落在边界外的点。这是非常直观的，所以让我给你一张图。想象只有范围是某个固定数字的点，比如说 range=13，而我们的中心在 lower-right 象限中，比如 (17, 5)。如果我们绘制这些点，用线连接它们，就会创建一个菱形：

 |    /\
 |   /  \
 |  /    \
-+-----------
 | /      \
 | \      /
 |  \    /
 |   \  /
 |    \/

如果我们只关心计算轴上方的点数，我们可以等效地只计算相应向上移动的较小菱形的轴上方的点数。示例：

 |    /\
 |   /  \
 |  /    \
-+-----------
 |  \    /
 |   \  /
 |    \/

现在，这非常使用起来很方便，因为恰好一半钻石在上面，一半在下面。尽管我们做了一半要小心——有些点落在轴上，并且 both 需要等效地考虑在边界内或边界外，但我们可以很容易地解释这一点。

利用这种洞察力，我们可以通过缩小范围和移动中心点来计算落在轴边界外的点数，并在这个新图的一半上计算点数。计数代码：

def count_side(size):
    if size % 2:
        return (size + 1) // 2
    return size // 2 + 1

def count_half(size):
    if size < 0:
        return 0
    return count_all(size) // 2 + count_side(size)

请注意，我们必须小心处理偶数范围，因为我们需要恰好计算一次中心（范围 0）。

虽然我们还没有完成 - 如果我们只是减去超出范围的点数然后独立地向左，我们就会多算要删除的点数，因为我们计算点数在 top-left 象限两次。为了解决这个问题，我们使用相同的技巧。我们将首先缩小 + 移动钻石穿过 x-axis，然后 我们将在这颗新钻石上再做一次，但穿过 y-axis。请注意，这颗新钻石最终将以原点为中心。我建议您在此时暂停片刻，想象一下并说服自己这很好，并且实际上会为我们提供任何特定范围的新钻石，包含落在 [=52 中的点数的 4 倍=] 象限.

使用这个，我们计算 top-left 象限中的点数，re-add 它们占总数。然后我们对右侧、底部和其他三个角重复相同的过程，以获得总和。完整解决方案如下：

from itertools import product


def count_all(size):
    if size % 2:
        return (size + 1) ** 2
    return size * (size + 2) + 1

def count_side(size):
    if size % 2:
        return (size + 1) // 2
    return size // 2 + 1

def count_half(size):
    if size < 0:
        return 0
    return count_all(size) // 2 + count_side(size)

def count_quarter(size):
    if size < 0:
        return 0
    return count_all(size) // 4 + count_side(size)

def get_deltas(pos, limit):
    return -(pos + 1), pos - (limit + 1)

def count_inside(c, r, x, y, s):
    total = count_all(s)

    vertical_deltas   = get_deltas(x, c)
    horizontal_deltas = get_deltas(y, r)

    out_sides = sum(count_half(s + delta) 
        for delta in horizontal_deltas + vertical_deltas)

    out_corners = sum(count_quarter(s + delta_vert + delta_horiz)
        for delta_vert, delta_horiz in product(vertical_deltas, horizontal_deltas))
    
    inside = total - out_sides + out_corners
    return inside

举几个例子：

>>> print(count_inside(5, 4, 2, 1, 3))
12
>>> print(count_inside(5, 4, 2, 1, 4))
14
>>> print(count_inside(5, 4, 2, 1, 5))
15
>>> print(count_inside(10, 6, 3, 2, 8))
36

计算二维图中 even/odd 个数字的总数

Counting the total number of even/odd numbers in a 2D graph

algorithm

matrix

graph

count

von-neumann