MUI_IIMA_1314_Geometria_Computacional_Envolvente_Convexa

1399 days ago by trinidad

Envolvente convexa

Algoritmo (lento) para calcular la envolvente convexa

Vamos a codificar el primer algoritmo explicado en clase.

Utilizaremos para ir probando los métodos el siguiente ejemplo.

puntos=[(0,2), (-1,0), (1,0), (0.1,0.5)] pp=sum([text(k,vector(puntos[k])+vector((0.1,0))) for k in range(len(puntos))])+points(puntos,size=50) pp.show(figsize=4,axes=False) 
       

En primer lugar, necesitamos una función que reciba la lista de puntos y dos puntos $p_i,p_j$ de la lista y devuelva cuántos puntos de la lista están "a la derecha" de la recta que une $p_i$ y $p_j$ en el sentido $p_i$ a $p_j$.

def cuenta_derecha(puntos,i,j): # Función que recibe una lista de pares de elementos, puntos, y dos posiciones de la lista, i,j, # Devuelve el número de puntos de la lista que están "a la derecha" de la recta que pasa por los puntos i y j, orientada en sentido i,j. n=len(puntos) ux=puntos[j][0]-puntos[i][0] uy=puntos[j][1]-puntos[i][1] contador=0 for k in [0..n-1]: vx=puntos[k][0]-puntos[i][0] vy=puntos[k][1]-puntos[i][1] if k!=i and k!=j and ux*vy-uy*vx<0: contador=contador+1 return contador 
       
cuenta_derecha(puntos,1,0) 
       

Vamos a crear también una función que reciba un vector y nos devuelva el ángulo con la horizontal.

def angulo(v): # Calcula el ángulo del vector v=(x,y) respecto de la horizontal if v[0]==0: if v[1]>0: alpha=pi/2 else: alpha=-pi/2 else: if v[0]>0: alpha=arctan(v[1]/v[0]) else: alpha=arctan(v[1]/v[0])+pi return alpha 
       
angulo([0,1]) 
       

Ahora ya podemos codificar el algoritmo. Recordemos que se trata de considerar todas las parejas de puntos $p_i,p_j$ y quedarnos con aquellas en las que no haya ningún punto a la derecha.

def convex_hull(puntos): # Calcula la envolvente conexa de una lista de puntos ch=[] n=len(puntos) for i in [0..n-1]: for j in [0..n-1]: if i!=j and cuenta_derecha(puntos,i,j)==0: alpha=angulo([puntos[j][0]-puntos[i][0],puntos[j][1]-puntos[i][1]]) ch=ch+[(puntos[i],puntos[j],alpha)] ch=sorted(ch,key=lambda k:k[2]) # Los ordenamos sólo para poder pintarlos como polígono. return [(k[0],k[1]) for k in ch] 
       
convex_hull(puntos) 
       
ch=sum([line(k) for k in convex_hull(puntos)]) (ch+pp).show(figsize=4,axes=False) 
       

También los podemos pintar rellenos.

polygon2d([k[1] for k in convex_hull(puntos)]).show(figsize=4,axes=False) 
       

 Veamos ahora un ejemplo más complejo

puntos=[(random(),random()) for k in [1..10]] 
       
(sum([text(k,vector(puntos[k])+vector((0.05,0))) for k in range(len(puntos))])+points(puntos,size=50)+sum([line(k) for k in convex_hull(puntos)])).show(figsize=4,axes=False) 
       

Envolvente convexa con comandos de Sage

Sage tiene implementado el algoritmo de cálculo de envolvente convexa en el comando Polyhedron.

ch = Polyhedron(vertices=puntos) ch.projection().render_outline_2d() 
       
ch = Polyhedron(vertices=puntos) ch.projection().render_fill_2d() 
       

Envolvente convexa 3D

También es válido para calcular componentes convexas en tres dimensiones (o en más).

puntos3d=[(random(),random(),random()) for k in range(50)] 
       
ch = Polyhedron(vertices=puntos3d) ch.projection().render_solid_3d(opacity = .7) 
       
ch.projection().render_wireframe_3d(thickness=4) 
       

Ejercicios

1. Obtener la envolvente convexa de los puntos $(-1,1)$, $(2,1)$, $(3,-1)$, $(-1,-3)$, $(-1/2,1/2)$, $(-1/2,-1/2)$, $(1/2,-1/2)$, $(1/2,1/2)$, $(0,0)$ utilizando el primer método (algoritmo lento).

2. Representar la envolvente convexa anterior como un polígono relleno.

3. Obtener la envolvente convexa de los puntos $(-1,1)$, $(2,1)$, $(3,-1)$, $(-1,-3)$, $(-1/2,1/2)$, $(-1/2,-1/2)$, $(1/2,-1/2)$, $(1/2,1/2)$, $(0,0)$ utilizando Polyhedron. Representarla como una figura rellena.

4. Crear conjuntos de pares de puntos de $[0,1]\times [0,1]$ aleatorios con 20, 50, 100 y 200 elementos. Calcular las envolventes conexas con los dos métodos. Obtener el tiempo que tarda cada método, para ello se utilizará %time, que escrito al principio de una celda nos devuelve el tiempo que tarda en ejecutarse.

 
       

En los ejercicios a continuación, vamos a leer un archivo en el que se encuentra un conjunto de datos, de modo que en cada fila están las coordenadas x e y de un punto y un número (por ejemplo, resultado de algún algoritmo de clasificación) que denominaremos identificador. Representaremos los datos y mediremos el área de los objetos de la figura. El aspecto de los datos es:

5. Lee el archivo csv globos.csv. En este caso nos vamos a encontrar que los datos están en formato texto. Para pasar un texto a un número real, se utiliza la función RDF y para pasarlo a número entero, ZZ. Una vez leído el archivo, recorreremos los datos ([ ... for k in datos]) para reformatearlos a nuestra conveniencia.

6. Filtra los datos para, o bien crear un conjunto de puntos por cada identificador, o bien crear una lista cuyos elementos sean la lista de puntos de cada identificador.

7. Representa las componentes conexas y los puntos en una gráfica (como arriba).

8. Calcula el área de cada una de las componente conexas. Puedes usar cualquiera de los métodos estudiados en clase o fijar un punto (por ejemplo, el primer vértice de la primera arista de la componente conexa), e ir triangulando con las siguientes aristas y calculando el área de los triángulos con la fórmula de Herón. Para aplicar la fórmula, es mejor definirla como una función que reciba los tres puntos y devuelva el área.

 
       

9. Consideramos la curva definida por los puntos $(0,0), (1,0), (1,1), (0,1), (3/4,1/2),(0,1/5),(0,0)$. Determinar si los puntos $(1/2,1/2)$, $(1/3,1/3)$, $(1/4,1/4)$, $(1/5,1/5)$ están dentro o fuera de ella (sin usar el dibujo).

10. Calcular el área de la superficie definida por $x^4-2x^2+xy+y^4-1<0$.