填充表示为二进制矩阵的凹多边形

Question

在我的任务中，我将凹多边形表示为 1 和 0 的矩阵，其中 1 表示给定点属于该多边形。比如下面是一个简单的正方形和一个u型多边形：

0 0 0 0     0 0 0 0 0 0 0
0 1 1 0     0 1 1 0 0 1 1
0 1 1 0     0 1 1 1 1 1 1
0 0 0 0     0 1 1 1 1 1 1

但是，有时我会得到不完整的表示，其中：(1) 包含所有边界点，(2) 缺少一些内部点。例如，在下面放大版的u型多边形中，位置(1,1)、(1,6)、(3,1)、...、(3,6)*处的元素是"unfilled"。目标是填充它们（即，将它们的值更改为 1）。

1 1 1 0 0 1 1 1
1 0 1 0 0 1 0 1
1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1

您知道 Python/NumPy 中是否有简单的方法可以做到这一点吗？

*(行,列),从左上角开始数

Answer 1

我不相信 Python 或其他任何地方会存在一些通用的解决方案。这是经典的广度优先图搜索。对于每个 0 要么存在一条相邻零点的路径，以便这些零点中至少有一个位于位置 (y,x) 以便 (x = 0 or y = 0 or x = maxx or y = maxy) 或者这个 0 应该改为 1.

也许这里的回答对您有帮助：How to trace the path in a Breadth-First Search?

Answer 2

这是图像处理中一个众所周知的问题，可以使用 morphological operators 解决。

有了它，您可以使用 scipy 的 binary_fill_holes 来填充面具上的孔：

>>> import numpy as np
>>> from scipy.ndimage import binary_fill_holes
>>> data = np.array([[1, 1, 1, 0, 0, 1, 1, 1],
                     [1, 0, 1, 0, 0, 1, 0, 1],
                     [1, 1, 1, 1, 1, 1, 0, 1],
                     [1, 0, 0, 0, 0, 0, 0, 1],
                     [1, 1, 1, 1, 1, 1, 1, 1]])

>>> filled = binary_fill_holes(data).astype(int)
>>> filled
array([[1, 1, 1, 0, 0, 1, 1, 1],
       [1, 1, 1, 0, 0, 1, 1, 1],
       [1, 1, 1, 1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1, 1, 1, 1],
       [1, 1, 1, 1, 1, 1, 1, 1]])

填充表示为二进制矩阵的凹多边形

Filling in a concave polygon represented as a binary matrix

python

numpy

concave

concave-hull