python - Moore Neighborhood in a matrix -
i have 2d text file converted image(the shape of 5 in case) , i'm trying implement moore neighborhood trace algorithm. problem when reach point in middle of matrix program starts visiting cells have been visited before never reaching bottom of matrix. input:
00000000000000000000 00000000000000000000 00000000000000000000 00001111111111100000 00001111111111100000 00001100000000000000 00001111111110000000 00001111111111100000 00000000000001110000 00000000000000110000 00011000000000110000 00011100000001110000 00001111111111110000 00000111111111000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 my output( 'x' border , cell 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 find @ iteration problem occurs (n=29) after starts going again
class parse: def __init__(self): self.state = 3 #entered w start looking n-e-s-w self.matrix = self.read_file() self.process() self.save_file() #handle files i/0 def read_file(self): ls = [] open("in","r") g: tmp = g.readlines() x in tmp: ls.append( [str(x[l]) l in xrange(len(x))] ) return ls def save_file(self): open("out","w") g: in xrange(len(self.matrix)): 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): x in xrange(len(self.matrix)): 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]) = 0 # iterations while < 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 direction skip def step(self,r,c): pos = [ [-1,0], [0,+1], [+1,0], [0,-1] ] #search in 4 directions of cell n-e-s-w p in xrange(len(pos)): sc = (p + self.state)%4 #start next direction clockwise entered x = pos[sc][0] + r y = pos[sc][1] + c #if cell 1 search neighborhood if self.matrix[x][y] == '1': self.neighborhod(x,y) return [x, y] #complete 0 cells 1 relative cell def neighborhod(self,r,c): pos = [ [-1,0], [0,+1], [+1,0], [0,-1] ] #search in 4 directions of cell n-e-s-w 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 direction skip p = parse() 
(please ignore green cells completion orange, wasn't unable rid of it)
i see logic problem. in neighborhod [sic], give no thought overall direction of investigation. instead, choose '1' , blindly select first direction has adjacent '0'. means when walk spot thickness of 1 character, run risk of stumbling out other side, breaking right through "thin wall".
you can fix trivial sense of wall recognition: new step must adjacent previous position. instead of starting left every time, start 45 or 90 degrees clockwise previous direction, cycling through choices there.
another way detect handful of possible "wall" shapes , set simple recognition patterns traverse them. grab 3x3 matrix previous position p, current position c, , '1' markings. here's sample pattern:
1p0 1x0 1c0 => 1p0 110 11c do these observations , suggestions moving?
Comments
Post a Comment