Xtal - 1 year ago 49

Python Question

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()

(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?