Python:完整的非对称网格

Question

我有一个 n 维点网格，但其中有空洞，我想获得缺失的网格点列表。但是，我不想扩展现有网格的边界。

例如在 2D 中，如果上下或左右有任何值，我只需要网格点坐标。这是一幅卡通片，其中 o 是一个现有点，x 是我想要的坐标。

    o o o o o 
o o x o o x o
o x x o o
  o x o o
  o o o o

虽然数据不在网格中。它只是一个坐标列表，即

coords = [(1000,3.5), (1000,4.0), (1000,4.5), (1000,5.0), (1000,5.5), 
(1100,4.5), (1100,5.5), (1200,4.0), (1200,4.5), (1200,5.0), (1200,5.5), 
(1300,3.5), (1300,4.0), (1300,4.5)]

所以我想要的值是 [(1100,3.5), (1100,4.0), (1100,5.0), (1200,3.5)]。

我尝试获取每个参数的最小值和最大值并制作一个新轴 numpy.arange(min(param1),max(param1),100)，然后通过将其与旧值进行比较numpy.setdiff1d() 但这使网格在不必要时成为矩形。

关于如何有效地做到这一点有什么想法吗？

Answer 1

我认为最简单的方法是将网格映射到矩形阵列。因为这样就可以相对简单快速地确定哪些点属于标准。缺点是 RAM 使用最终可能会成为一个问题，尤其是对于稀疏网格。

仍然有争议的一点是应该如何定义网格。其他答案目前使用元素之间沿维度的最小差异作为该方向上网格的步长。但是，这在极少数情况下会带来问题。例如。如果已知坐标是:

2, 4, 6, 9, 11

然后步长将取等于 2，但显然这在 9 处出错了。也许最好取连续差异的最大公约数？例如。在this answer的帮助下.在我的代码中，我采用了不同的方法:仅使用已知坐标中存在的“刻度”来构建网格。

对于 2D 情况，类似以下内容就足够了:

def find_holes_2d(coords):
    coords = np.asanyarray(coords)

    # determine grid and transform coordinates
    uniq_x, labels_x = np.unique(coords[:,0], return_inverse=True)
    uniq_y, labels_y = np.unique(coords[:,1], return_inverse=True)

    # layout the known grid in an array
    grid = np.zeros([len(uniq_x), len(uniq_y)], bool)
    grid[labels_x, labels_y] = True

    # see which grid points are inside known coordinates
    x_fwd  = np.logical_or.accumulate(grid, axis=0)
    x_bkwd = np.logical_or.accumulate(grid[::-1], axis=0)[::-1]
    y_fwd  = np.logical_or.accumulate(grid, axis=1)
    y_bkwd = np.logical_or.accumulate(grid[:,::-1], axis=1)[:,::-1]

    # select the holes according to the criteria
    holes = ~grid & (x_fwd & x_bkwd | y_fwd & y_bkwd)

    # Transform positions back to original coordinates
    I,J = np.where(holes)
    return np.column_stack([uniq_x[I], uniq_y[J]])

相同的方法可以应用于 ND 情况，例如:

def find_holes(coords):
    coords = np.asanyarray(coords)

    uniq, labels = zip(*[np.unique(c, return_inverse=True) for c in coords.T])

    grid = np.zeros(map(len, uniq), bool)
    grid[labels] = True

    candidates = np.zeros_like(grid)
    for dim in range(grid.ndim):
        grid0 = np.rollaxis(grid, dim)
        inside = np.logical_or.accumulate(grid0, axis=0) & 
                 np.logical_or.accumulate(grid0[::-1], axis=0)[::-1]
        candidates |= np.rollaxis(inside, 0, dim+1)
    holes = candidates & ~grid

    hole_labels = np.where(holes)

    return np.column_stack([u[h] for u, h in zip(uniq, hole_labels)])

---

最后，还有一个问题，如这个玩具示例所示:

o x o o
x   x o
o o o o

这里仍有一个漏洞“未被发现”。这很容易解决，方法是将找到的孔的坐标(x)添加到原始坐标并运行第二次迭代。