Lab3. Convex Hull

Mi repositorio

Para esta semana se trabajo nuevamente con los bordes pero ahora, teníamos que ubicar los puntos de las orillas que al unirlos envuelve por completo una figura. 

El algoritmo usado para obtenerlo es  convex hull  al igual que de Jarvi’s march el cual resulta ser uno de los más sencillos

• ·Se inicia a un punto extremo dentro de los puntos del contorno, normalmente el que se encuentre más a la izquierda. 
• En cada paso, se prueba cada punto de los puntos y se encuentra cual hace la vuelta más larga hacia la derecha. Este punto debe estar en el contorno

En este caso no se obuvo el resultado al hacer el envolvimiento uniendo los puntos, pero si aparecen dentro de los bordes

Código

	import Image
	from sys import argv
	import ImageDraw
	TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0)
	def turn(p, q, r):
	return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)
	#distancias entre p y q
	def dist(p, q):
	dx, dy = q[0] - p[0], q[1] - p[1]
	return dx * dx + dy * dy
	def next_hull_pt(points, p): #Para devolver el siguiente punto convexo desde la primer distancia p
	q = p
	for r in points:
	t = turn(p, q, r)
	if t == TURN_RIGHT or t == TURN_NONE and dist(p, r) > dist(p, q):
	q = r
	return q
	def convex_hull(points): # Aplicamos algoritmo Convex Hull que devuelve los puntos envolventes hacia la izquierda
	hull = [min(points)]
	for p in hull:
	q = next_hull_pt(points, p)
	if q != hull[0]:
	hull.append(q)
	return hull
	def bfs(imagen, rcolor, px, altura, ancho): # alicamos bfs para darle color al contorno de la imagen tomando los pixeles vecinos
	pixeles = imagen.load()
	(fila, columna) = px
	original = pixeles[fila, columna]
	cola = [(fila, columna)]
	cola2 = []
	while len(cola) > 0:
	(fila, columna) = cola.pop(0)
	actual = pixeles[fila, columna]
	if actual == original or actual == rcolor:
	for dx in [-1, 0, 1]:
	for dy in [-1, 0, 1]:
	candidato = (fila + dy, columna + dx)
	if candidato[0] >= 0 and candidato[0] < altura and candidato[1] >= 0 and candidato[1] < ancho:
	contenido = pixeles[candidato[0], candidato[1]]
	if contenido == original:
	pixeles[candidato[0], candidato[1]] = rcolor
	cola.append(candidato)
	cola2.append(candidato)
	return cola2
	def main(image):
	im = Image.open(image)
	w, h = im.size
	pix = im.load()
	hulls = []
	#draw = ImageDraw.Draw(im)
	for i in range(w):
	for j in range(h):
	if pix[i, j] == (255, 255, 255):
	coords = bfs(im, (255, 0, 0), (i, j), w, h)#BFS anteri
	#print coords
	hulls.append(convex_hull(coords))
	for hull in hulls:
	for points in hull:
	pix[points] = (0, 0, 0)
	#draw.line(((hulls[i][j], hulls[i][j+1])), fill=(0, 0, 255))
	im.save("fin.jpg")
	return hulls
	image = argv[1]
	main(image)

view raw convex.py hosted with ❤ by GitHub