Mizipzor

January 25, 2009, January 25, 2009 21:02, permalink

No rating. Login to rate!

import random, math, glob, sys
from PIL import Image

INFINITE=1000000000

class Node:
	def __init__(self, pos, open=True):
		assert(len(pos)==2)
		self.pos = pos				#where this node is located
		self.neighbours = []		#a list of all neighbour nodes
		self.open = True			#True if this node is traversable
		self.distance = 0			#distance to the startnode
		self.visited = False		#True if this node has already been visited this run
		self.visited_from = None	# the tile we came from when calculating distance, not needed as were not interested in the path 
		
	def __repr__(self):
		s = "pos: "+str(self.pos)
		s += "\nopen: "+str(self.open)
		s += "\ndistance: "+str(self.distance)
		s += "\nvisited: "+str(self.visited)
		return s
		
	def add_neighbour(self, n):
		if not n in self.neighbours and n is not self and self.open and n.open:
			self.neighbours.append(n)
		
class Graph:
	def __init__(self):
		self.nodes = []
		self.longest_distance = (0,None,None) #three element tuple; distance, node1, node2
		
	def resize(self, xy):
		self.nodes = []
		self.longest_distance = (0,None,None)
		
		for y in range(xy[1]):
			for x in range(xy[0]):
				self.add_node(x, y)
		
	def add_node(self, x, y):
		self.nodes.append(Node((x,y)))
		
	def find_node(self, pos):
		for i in self.nodes:
			if i.pos==pos:
				return i
		return None
		
	def reset(self, startpos):
		for i in self.nodes:
			i.distance = INFINITE
			i.visited = False
		
	def calc_neighbours(self):
		print "calculating neigbours"
		for i in self.nodes:
			for x,y in zip((0,1,0,-1),(-1,0,1,0)):
				p = (i.pos[0]+x, i.pos[1]+y)
				n = self.find_node(p)
				if n :
					i.add_neighbour(n)
					
	def dijkstra(self, startpos):
		print "running dijkstra from",startpos,
		
		current = self.find_node(startpos)
		if current.open and len(current.neighbours)!=0:
			print "which has",len(current.neighbours),"neighbours"
		else:
			print "aborting, its not open or has no neighbours"
			return
		
		self.reset(startpos)
		current.distance = 0
	
		#run as long as we have nodes to visit
		while current:
			for i in current.neighbours:
				if not i.visited:
					dist = current.distance+1
					if dist < i.distance:
						i.distance = dist
						i.visited_from = current
			current.visited = True
			current = self.find_next_unvisited()

		#update longest distance
		longest = None
		for i in self.nodes:
			if longest==None or i.distance>longest.distance:
				if i.distance!=INFINITE:
					longest = i
		if longest.distance > self.longest_distance[0]:
			self.longest_distance = (longest.distance, self.find_node(startpos), longest)
			
	def calc_longest_distance(self):
		#run dijkstra on every node, each run will overwrite self.longest_distance
		for i in self.nodes:
			if i.open:
				self.dijkstra(i.pos)
				
	def find_next_unvisited(self):
		best = None
		for i in self.nodes:
			if not i.visited:
				if best==None or i.distance < best.distance:
					best = i
		return best
		
	def calc_bounds(self):
		x,y = 0,0
		for i in self.nodes:
			if i.pos[0]>x: 
				x = i.pos[0]
			if i.pos[1]>y: 
				y = i.pos[1]
		return x,y
		
	def ascii_repr(self):
		s = ""
		b = self.calc_bounds()
		for y in range(b[1]):
			for x in range(b[0]):
				n = self.find_node((x,y))
				if n and n.open:
					s += "."
				else:
					s += "#"
			s += "\n"
		return s
		
	def set_all_open(self, openflag):
		for i in self.nodes:
			i.open = openflag

def process_image(path, closedcolour=(0,0,0)):
	"""	opens a image and creates a graph from it, then runs the algorithm and 
		marks the two pixels furthest away from each other in red"""
	#create graph from file
	img = Image.open(path)
	#img.show()
	
	g = Graph()
	g.resize(img.size)
	
	for y in range(img.size[1]):
		for x in range(img.size[0]):
			if img.getpixel((x,y))==closedcolour:
				g.find_node((x,y)).open = False
			else:
				g.find_node((x,y)).open = True
	print g.ascii_repr()
				
	#run algorithm
	g.calc_neighbours()
	g.calc_longest_distance()
	
	#done
	print "best distance (",g.longest_distance[0],") is between"
	print g.longest_distance[1].pos,"and",g.longest_distance[2].pos
	
	#save image with red dots on the longest distance points
	img.putpixel(g.longest_distance[1].pos, (255,0,0))
	img.putpixel(g.longest_distance[2].pos, (255,0,0))
	img.save(path)
					
def main(globarg):
	for i in glob.glob(globarg):
		process_image(i)
	return
						
if __name__=="__main__":
	main(sys.argv[1])