# Suppose you have a black image with white spots
# This script will give you box coordinates of those spots
#
#
# live-wire.github.io
#
# We will look at the image from the bottom-left and spread outwards
# If a 1 is encountered, the algorithm will try to spread in all directions from that cell.
# See functions possible_moves, possible_moves_exhaustive


already_visited = set()
def is_valid_move(x, y, arr):
	if 0<=x<len(arr) and 0<=y<len(arr[0]) and (x,y) not in already_visited:
		return True
	else:
		return False

def visited(x, y):
	if (x,y) not in already_visited:
		already_visited.add((x,y))

def possible_moves(x, y):
	return [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]

def possible_moves_exhaustive(x, y):
	return [(x+1, y), (x+1, y-1), (x+1, y+1),
			(x, y+1), (x, y-1),
			(x-1, y), (x-1, y-1), (x-1, y+1)]

# use possible_moves_exhaustive if you want to connect blobs with diagonal elements
MOVES = possible_moves # possible_moves_exhaustive

# img should be a 2d array
def find_blobs(img):
	def boundary_update(n_x, n_y):
		if boundaries['left']>n_y: boundaries['left'] = n_y
		if boundaries['right']<n_y: boundaries['right'] = n_y
		if boundaries['up']>n_x: boundaries['up'] = n_x
		if boundaries['down']<n_x: boundaries['down'] = n_x
		visited(n_x, n_y)

	def spread(x, y):
		for item in MOVES(x,y):
			n_x, n_y = item
			if is_valid_move(n_x, n_y, img) and img[n_x][n_y]==1:
				boundary_update(n_x, n_y)
				spread(n_x, n_y)

	all_blobs = []
	boundaries = None
	for i in range(len(img)):
		for j in range(len(img[0])):
			boundaries = {
				'left':len(img[0]),
				'right':-1,
				'up':len(img),
				'down':-1
			}
			if img[i][j]==1 and is_valid_move(i, j, img):
				print(i, j)
				boundary_update(i, j)
				spread(i, j)
				all_blobs.append(boundaries)
	return all_blobs

img = [
	[0, 0, 0, 0, 1, 0],
	[0, 0, 0, 1, 0, 0],
	[0, 0, 0, 1, 1, 0],
	[0, 0, 0, 1, 0, 0],
	[0, 1, 0, 0, 0, 0],
	[0, 1, 0, 0, 0, 0]
]

print(find_blobs(img))