Search code examples
pythonnumpyscipy-spatial

Getting the boundary of numpy array shape with a hole

I am trying to obtain an ndarray of points along the boundary of a shape denoted by 1's in the array. I tried using scipy.spatial.ConvexHull but the boundary created by the convex hull did not account for the hole in the middle of the shape (I need a boundary around the hole too). This is the kind of boundary I am trying to create from the array. How can I account for the hole in the shape?

enter image description here

The colored in area is the area that the boundary points should be calculated from. enter image description here

import numpy as np
from skimage.measure import label, regionprops
import matplotlib.pyplot as plt
from scipy.spatial import Voronoi, voronoi_plot_2d, ConvexHull


arr = np.array([
    [1,1,1,1,1,1,0,0,0,1,0],
    [1,1,1,1,1,1,0,0,0,1,0],
    [1,1,0,0,0,1,1,1,1,1,0],
    [1,1,0,1,1,1,1,1,0,0,0],
    [1,1,1,1,1,1,0,0,0,0,0],
    [0,1,1,1,1,0,0,0,0,0,0],])

coords = []
for x in range(arr.shape[0]):
    for y in range(arr.shape[1]):
        if arr[x][y] > 0:
            tile = [x,y]
            coords.append(tile)
            # print("tile", tile)
coords = np.array(coords)
# print(coords)

hull = ConvexHull(coords)
plt.plot(coords[:,0], coords[:,1], 'o')
for simplex in hull.simplices:
    plt.plot(coords[simplex, 0], coords[simplex, 1], 'k-')

plt.plot(coords[hull.vertices,0], coords[hull.vertices,1], 'r--', lw=2)
plt.plot(coords[hull.vertices[0],0], coords[hull.vertices[0],1], 'ro')
Solution

  • This is a bit hacky, but if you convolve the zeros with the right kernel (v4 or v8) you get the outer part plus the frontier, so if you do an and kind of operation with the inner part you get only the frontier. Here's an example:

    import numpy as np
from scipy.signal import convolve2d

arr = np.array([
    [1,1,1,1,1,1,0,0,0,1,0],
    [1,1,1,1,1,1,0,0,0,1,0],
    [1,1,0,0,0,1,1,1,1,1,0],
    [1,1,0,1,1,1,1,1,0,0,0],
    [1,1,1,1,1,1,0,0,0,0,0],
    [0,1,1,1,1,0,0,0,0,0,0],
])

# v4 example, 
kernel = np.array([
    [0,1,0],
    [1,0,1],
    [0,1,0],
])

# you have to zero pad first in order to get the edges
padded = np.pad(arr, ((1, 1), (1, 1)), 'constant', constant_values=0)

# the `astype(bool)` is for normalization
# the `and` operation in this case is the elementwise product
frontier = convolve2d(1-padded, kernel, mode='valid').astype(bool) * arr