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

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

Это очень хорошо известная проблема обработки изображений, которая может быть решена с помощью морфологических операторов.

С этим вы можете использовать Scipy's 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.

Может быть, вам будет полезен ответ: как отследить путь в поиске по ширине?