Xtal Xtal - 7 months ago 23
Python Question

Moore Neighborhood in a matrix

I have a 2d text file converted from a image(the shape of 5 in this case) and I'm trying to implement Moore Neighborhood Trace algorithm.
The problem is that when i reach a point in the middle of the matrix my program starts visiting cells that have been visited before never reaching the bottom of the matrix.
My input:

00000000000000000000
00000000000000000000
00000000000000000000
00001111111111100000
00001111111111100000
00001100000000000000
00001111111110000000
00001111111111100000
00000000000001110000
00000000000000110000
00011000000000110000
00011100000001110000
00001111111111110000
00000111111111000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000


My output( 'x' is the border , A is the cell where I am after N iterations)

00000000000000000000
00000000000000000000
00000xxxxxxxxxx00000
000011111111111x0000
000011111111111x0000
000011xxxxxxxxx00000
0000111111111x000000
000011111111A1100000
000000000000x1110000
00000000000000110000
00011000000000110000
00011100000001110000
00001111111111110000
00000111111111000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000


I manage to find at which iteration the problem occurs (n=29) after that it starts going up again

class parse:

def __init__(self):
self.state = 3 #entered from W so start looking from N-E-S-W
self.matrix = self.read_file()
self.process()
self.save_file()

#Handle Files I/0
def read_file(self):
ls = []
with open("in","r") as g:
tmp = g.readlines()

for x in tmp:
ls.append( [str(x[l]) for l in xrange(len(x))] )

return ls


def save_file(self):
with open("out","w") as g:
for i in xrange(len(self.matrix)):
for j in xrange(len(self.matrix)):
g.write(self.matrix[i][j])
g.write('\n')

#End File Handle


#Trace Algorithm
#non-negative x

def start_pixels(self):

for x in xrange(len(self.matrix)):
for y in xrange(len(self.matrix)):

if self.matrix[x][y] == '1':

return [x,y]

def process(self):
init_point = self.start_pixels()

start = self.step(init_point[0], init_point[1])
i = 0 # iterations

while i < 29:

tmp = self.step(start[0],start[1])

start= tmp

i+=1

self.matrix[start[0]][start[1]] = 'A' #current cell
print self.state #print the direction to skip

def step(self,r,c):
pos = [ [-1,0], [0,+1], [+1,0], [0,-1] ] #search in the 4 directions of the cell N-E-S-W

for p in xrange(len(pos)):

sc = (p + self.state)%4 #start from the next direction clockwise from which was entered

x = pos[sc][0] + r
y = pos[sc][1] + c


#if the cell is 1 search its neighborhood
if self.matrix[x][y] == '1':
self.neighborhod(x,y)
return [x, y]


#complete 0 cells with 1 relative to the cell
def neighborhod(self,r,c):
pos = [ [-1,0], [0,+1], [+1,0], [0,-1] ] #search in the 4 directions of the cell N-E-S-W

for p in xrange(len(pos)):

x = pos[p][0] + r
y = pos[p][1] + c


if self.matrix[x][y] != '1':
self.matrix[x][y] = 'x'
self.state = p #assign the direction to skip



p = parse()


Animated version

(please ignore the green cells completion with orange, i wasn't unable to get rid of it)

Answer

I see the logic problem. In neighborhod [sic], you give no thought to the overall direction of investigation. Instead, you choose a '1' and then blindly select the first direction that has an adjacent '0'. This means that when you walk into a spot with a thickness of 1 character, you run the risk of stumbling out the other side, breaking right through the "thin wall".

You can fix this with some trivial sense of wall recognition: the new step must be adjacent to the previous position. Instead of starting to the left every time, start 45 or 90 degrees clockwise from your previous direction, cycling through the choices from there.

Another way is to detect the handful of possible "wall" shapes and set up simple recognition patterns to traverse them. Grab the 3x3 matrix with your previous position P, current position C, and '1' markings. Here's a sample pattern:

1P0    1x0
1C0 => 1P0
110    11C

Do these observations and suggestions get you moving?