Заполнение вогнутого многоугольника, представленного как двоичная матрица

Question

В моей задаче я представляю вогнутый многоугольник как матрицу из единиц и нулей, где один означает, что данная точка принадлежит многоугольнику. Например, следующие простой квадрат и 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) * являются «незаполненными ». Цель состоит в том, чтобы заполнить их (т. Е. Изменить их значение на 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

Это очень хорошо известная проблема в обработке изображений, которые могут быть решены с помощью 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]]) 

Answer 2

Я не верю, что существуют некоторые общие решения цели в Python или любой другой. Это классический поиск по ширине в начале графика. Для каждого 0 существует либо путь соседних нулей, так что хотя бы один из этих нулей находится в положении (y, x) так, что (x = 0 или y = 0 или x = maxx или y = maxy), или этот 0 должен быть изменен на 1.

может быть, ответ здесь будет полезным для вас: How to trace the path in a Breadth-First Search?