Actividad 3 - Convex hull

Para esta semana se nos pidió trabajar nuevamente con los bordes pero en este caso, teníamos que ubicar los puntos de las orillas que al unirlos encerraran por completo una figura.

Para esto utilice el algoritmo de gift wrapping el cual consiste en ubicar los puntos que se encuentran mas a la izquierda de la imagen.

Esta es la imagen que utilice para localizar los puntos mas a la izq:

Al aplicar el algoritmo si logre encontrar los puntos y esto fue lo que obtuve

Como se puede observar en las orillas de las imágenes se encuentran algunos puntos rojos, que vienen siendo los puntos mas a la izq del borde.

Este es el código que utilice para ubicar los puntos:
*****

	import Image #esto para trabajar con imagenes
	import sys
	import pygame
	import math
	from time import *
	import random
	import ImageDraw
	#cargamos y abrimos imagen
	def imagen():
	img = Image.open("cora.jpg").convert('RGB')
	#img2= Image.open("img3.jpg")
	#img6 =Image.open("prueba.png")
	ancho,alto = img.size
	img = convex(img,ancho,alto)
	return img, ancho, alto
	def bfs(img,ancho,alto,color,posa):
	pixel= img.load()
	cont=0
	cen1=[]
	cen2=[]
	cola=[] #creamos la cola
	puntos = []
	cola.append(posa) #posicion actual se agrega a la cola
	inicio = pixel[posa]
	while len(cola)>0:
	(i,j)=cola.pop(0)
	posa = pixel[i,j]
	if (posa == inicio or posa ==color):
	try:
	if(pixel[i-1,j]):
	if(pixel[i-1,j]==inicio):
	pixel[i-1,j] = color
	cola.append((i-1,j))
	cont+=1 # contador para encontrar los pixeles ke van en gris
	cen1.append((i-1))
	cen2.append((j))
	puntos.append((i-1,j))
	except:
	pass
	try:
	if(pixel[i+1,j]):
	if(pixel[i+1,j]==inicio):
	pixel[i+1,j] = color
	cola.append((i+1,j))
	cont+=1
	cen1.append((i+1))
	cen2.append((j))
	puntos.append((i+1,j))
	except:
	pass
	try:
	if(pixel[i,j-1]):
	if(pixel[i,j-1]==inicio):
	pixel[i,j-1] = color
	cola.append((i,j-1))
	cont+=1
	cen1.append((i))
	cen2.append((j-1))
	puntos.append((i,j-1))
	except:
	pass
	try:
	if(pixel[i,j+1]):
	if(pixel[i,j+1]==inicio):
	pixel[i,j+1] = color
	cola.append((i,j+1))
	cont+=1
	cen1.append((i))
	cen2.append((j+1))
	puntos.append((i,j+1))
	except:
	pass
	img = img.save('contorno.png', 'png')
	return cont,color,cen1,cen2,puntos
	def convex(img,ancho,alto):
	pixel= img.load()
	pts=[]
	for i in range(ancho):
	for j in range(alto):
	#print pixel[i, j]
	if pixel[i,j]==(255,255,255):
	a= 230
	b=230
	c=230
	(r,g,b)= (a,b,c)
	cont,color,cen1,cen2,puntos=bfs(img,ancho,alto,(r,g,b),(i,j))
	puntos = jarvis(puntos)
	for pts in puntos:
	pixel[pts]= (255,0,0)
	blue =(0,0,255)
	#pygame.draw.lines(pts,blue, 1)
	#print 'aki ando'
	img.save('contorno.png', 'png')
	return pts
	def turn(p1, p2, p3):
	t = cmp(0, (p2[0] - p1[0])*(p3[1] - p1[1]) - (p3[0] - p1[0])*(p2[1] - p1[1]))
	if t == -1: return 'LEFT'
	elif t == 0: return 'NONE'
	elif t == 1: return 'RIGHT'
	def jarvis(S):
	hull =[min(S)]
	#print hull
	i =0
	while(S):
	end = S[0]
	for j in range(len(S)-1):
	minimo = min(hull[i],end)
	if end == hull[i] or turn(S[j],hull[i],end)== 'LEFT':
	end = S[j]
	i+=1
	hull.append(end)
	#print hull
	if end == hull[0]:
	break
	return hull
	def main ():
	#pygame.display.set_caption("Ventana")
	r,ancho,alto = imagen()
	main()

view raw convex.py hosted with ❤ by GitHub

*****
Ademas de esto intente unir cada uno de los puntos pero al parecer la imagen contenía mucho ruido y lo que hacia era unir los puntos en donde había ruido, así que en la imagen se observan unos ligeros puntos azules alrededor de cada forma.. osea el intento de unir los puntos. La verdad esto no salio como esperaba :( .

Referencias:
http://en.wikipedia.org/wiki/Gift_wrapping_algorithm