Creating boundaries on numpy arrays-CodePudding

I am looking for an algorithm that will help me create a boundary around the points on a 2-dim array that are not zero. Let me give an example.

I have the following array:]

I want an algorithm that will give me the most efficient way I can create a "barricade" around each of the little "islands". For context, each group of 1s represent a source of resources in this resource management game, and I want to build walls around it to guard it from my opponent.

Essentially, this algorithm should give the value of the 2s in the following figure:

There are a few points to this:

The array is always square but the size of each dimension can vary from 12 to 40;
Units cannot move on diagonals;
There can be various islands (groups of 1s), and can have all sorts of irregular shapes;
Sometimes it might be more efficient to barricade two close by "islands" using the same barricade, if they are super close by.

Any ideas on this? I don't even know how to google this problem, so I ended up not finding anything. Thank you!

EDIT1: Code to create the initial array EDIT2: Fixed the answer

import numpy as np

size = 15
test_mat = np.zeros((size, size))
test_mat[(4, 5, 5, 6), (5, 4, 6, 5)] = 1
test_mat[(9, 9, 9, 10, 10, 11, 11), (8, 9, 10, 8, 10, 8, 10)] = 1

CodePudding user response：

How about this:

import numpy as np
from scipy.ndimage import binary_dilation, binary_erosion

size = 15
test_mat = np.zeros((size, size))
test_mat[(4, 5, 5, 6), (5, 4, 6, 5)] = 1
test_mat[(9, 9, 9, 10, 10, 11, 11), (8, 9, 10, 8, 10, 8, 10)] = 1

dilated = binary_dilation(test_mat).astype(int)
eroded = binary_erosion(dilated)
borders = dilated-eroded

which gives:

[[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 1 0 1 0 0 0 0 0 0 0 0]
 [0 0 0 1 0 0 0 1 0 0 0 0 0 0 0]
 [0 0 0 0 1 0 1 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 1 1 1 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 0 1 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 0 1 0 0 0]
 [0 0 0 0 0 0 0 1 0 1 0 1 0 0 0]
 [0 0 0 0 0 0 0 0 1 0 1 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]

CodePudding user response：

This does not solve my problem, just wanted to post an idea that I was playing with. Here goes the code:

import numpy

# Generate the map
size = 15
test_mat = np.zeros((size, size))
test_mat[(4, 5, 5, 6), (5, 4, 6, 5)] = 1
test_mat[(9, 9, 9, 10, 10, 11, 11), (8, 9, 10, 8, 10, 8, 10)] = 1

# Find a solution by applying a convulsion
conv_mat = np.array([
        [0, 1, 0], 
        [1, 1, 1],
        [0, 1, 0]])

conv = convolve(test_mat, conv_mat)
conv[test_mat > 0] = 0
conv[conv > 0] = 2
conv[test_mat > 0] = 1 # Mark the resources as 1

Using this code you get:

However, as you can see, when there is a gap, this does not find the right solution..