La envolvente convexa - Informática...
Transcript of La envolvente convexa - Informática...
![Page 1: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/1.jpg)
Tema 3G
eometr
í a Com
putacional
La envolvente convexa
Curso: 1º de Ingeniería Informática, Plan 2004Profesora: Lidia Ortega AlvaradoDepartamento: InformáticaCurso académico: 2009/10Ubicación: http://wwwdi.ujaen.es/asignaturas/gc/tema3.odpActualizado: 19/10/2009
![Page 2: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/2.jpg)
La envolvente convexaÍndice
Definiciones de Envolvente Convexa Propiedades Algoritmos de cálculo
Algoritmo elemental El “scan” de Graham La marcha de Jarvis Quickhull Incremental Divide y Vencerás Diagrama Polar
Bibliografía
![Page 3: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/3.jpg)
La envolvente convexaIntroducción
Es uno de los cálculos más importantes en Geometría Computacional con aplicaciones en distintas áreas, dentro yfuera de la Geometría Computacional
EnvolventeConvexade objetos
recubrimiento o cobertura que encierra a todos los elementos
sin vértices cóncavos
de puntos, polígonos, círculos, objetos 3D, etc.
Estudiaremos el caso más sencillo: la envolvente convexade un conjunto de puntos en el plano
![Page 4: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/4.jpg)
La envolvente convexaDefiniciones
Definición intuitiva:Supongamos que cada punto del plano está representado comola cabeza de una puntilla hincada perpendicularmente sobreuna superficie plana. Si tomamos una goma elástica que envuelva a todas las puntillas, el resultado en la envolventeconvexa.
goma elásticatensa
goma al destensar
![Page 5: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/5.jpg)
La envolvente convexaDefiniciones
Definición 1:La envolvente convexa de un conjunto de puntos S es el polígono convexo P que contiene a todos los elementos de Scon menor área (o perímetro) posible
S
menorpolígonoconvexoque envuelvea todos
no envuelvea todos
existe otropolígono conmenor área
![Page 6: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/6.jpg)
La envolvente convexaDefiniciones
Definición 2:La envolvente convexa de un conjunto de puntos S es el polígono convexo P si para cada par de puntos x e y de S, elsegmento xy siempre está contenido en P
S
todos los posibles segmentos quedan dentro del polígono P
no se cumple la propiedad
![Page 7: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/7.jpg)
La envolvente convexaPropiedades
Propiedad 1:El cálculo de la envolvente convexa consiste en encontrar todoslos puntos extremos del conjunto S.Un punto x∈S es noextremo si existe un triángulo con vérticesen S (distintos de x) de forma que x esté dentro del triángulo.
S
punto interior
imposible encontrarun triángulo que lo envuelva
![Page 8: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/8.jpg)
La envolvente convexaPropiedades
Propiedad 2:Un punto x∈S es extremo si existe una recta pasando por xque deje al resto de puntos de S hacia un lado de dicha recta
S
![Page 9: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/9.jpg)
La envolvente convexaAlgoritmos elementales
Dado un conjunto S, encontrar todos sus puntos extremos ordenados en sentido antihorario
SSPropiedad 1:Cada punto p∈S puede estar en O(n3) triángulos distintosExisten O(n) puntos que cuestionar
O(n4)
Propiedad 2:Existen O(n2) pares de puntos distintosExisten O(n) puntos que cuestionar
O(n3)
![Page 10: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/10.jpg)
La envolvente convexaAlgoritmo: Graham's scan
ALGORITMO GRAHAM (VAR S:NubePuntos, n:entero, VAR Env:Poligono)ENTRADA: La nube de puntos S de tamaño nSALIDA: La envolvente convexa de S, CH(S)INICIO min < PuntoMenorOrdenada(S,n) OrdenarAngularmente(S,n,min) PilaCrea(Env) PilaPush(Env,S[0]) PilaPush(Env,S[1]) PilaPush(Env,S[2]) i < 1 MIENTRAS i < n1 REPETIR t < PilaPop (Env) SI Izquierda (PilaTope(Env), t, S[i]) ENTONCES PilaPush (Env, t) PilaPush (Env, i) i < i+1 FIN_SI FIN_MIENTRASFIN
S
Basado en la Propiedad 1
![Page 11: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/11.jpg)
La envolvente convexaAlgoritmo: Graham's scan
ALGORITMO GRAHAM (VAR S:NubePuntos, n:entero, VAR Env:Poligono)ENTRADA: La nube de puntos S de tamaño nSALIDA: La envolvente convexa de S, CH(S)INICIO min < PuntoMenorOrdenada(S,n) OrdenarAngularmente(S,n,min) PilaCrea(Env) PilaPush(Env,S[0]) PilaPush(Env,S[1]) PilaPush(Env,S[2]) i < 1 MIENTRAS i < n1 REPETIR t < PilaPop (Env) SI Izquierda (PilaTope(Env), t, S[i]) ENTONCES PilaPush (Env, t) PilaPush (Env, i) i < i+1 FIN_SI FIN_MIENTRASFIN
S
min
![Page 12: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/12.jpg)
La envolvente convexaAlgoritmo: Graham's scan
ALGORITMO GRAHAM (VAR S:NubePuntos, n:entero, VAR Env:Poligono)ENTRADA: La nube de puntos S de tamaño nSALIDA: La envolvente convexa de S, CH(S)INICIO min < PuntoMenorOrdenada(S,n) OrdenarAngularmente(S,n,min) PilaCrea(Env) PilaPush(Env,S[0]) PilaPush(Env,S[1]) PilaPush(Env,S[2]) i < 3 MIENTRAS i < n1 REPETIR t < PilaPop (Env) SI Izquierda (PilaTope(Env), t, S[i]) ENTONCES PilaPush (Env, t) PilaPush (Env, i) i < i+1 FIN_SI FIN_MIENTRASFIN
S
min
1
23
4
5
6
7
8
9
![Page 13: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/13.jpg)
La envolvente convexaAlgoritmo: Graham's scan
ALGORITMO GRAHAM (VAR S:NubePuntos, n:entero, VAR Env:Poligono)ENTRADA: La nube de puntos S de tamaño nSALIDA: La envolvente convexa de S, CH(S)INICIO min < PuntoMenorOrdenada(S,n) OrdenarAngularmente(S,n,min) PilaCrea(Env) PilaPush(Env,S[0]) PilaPush(Env,S[1]) PilaPush(Env,S[2]) i < 3 MIENTRAS i < n1 REPETIR t < PilaPop (Env) SI Izquierda (PilaTope(Env), t, S[i]) ENTONCES PilaPush (Env, t) PilaPush (Env, i) i < i+1 FIN_SI FIN_MIENTRASFIN
S
0
1
23
4
5
6
7
8
9
0 1 2
Env
![Page 14: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/14.jpg)
La envolvente convexaAlgoritmo: Graham's scan
ALGORITMO GRAHAM (VAR S:NubePuntos, n:entero, VAR Env:Poligono)ENTRADA: La nube de puntos S de tamaño nSALIDA: La envolvente convexa de S, CH(S)INICIO min < PuntoMenorOrdenada(S,n) OrdenarAngularmente(S,n,min) PilaCrea(Env) PilaPush(Env,S[0]) PilaPush(Env,S[1]) PilaPush(Env,S[2]) i < 3 MIENTRAS i < n1 REPETIR t < PilaPop (Env) SI Izquierda (PilaTope(Env), t, S[i]) ENTONCES PilaPush (Env, t) PilaPush (Env, i) i < i+1 FIN_SI FIN_MIENTRASFIN
S
0
1
23
4
5
6
7
8
9
0 1
Envi=3 t=2Izquierda(1,2,3)=V
![Page 15: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/15.jpg)
La envolvente convexaAlgoritmo: Graham's scan
t < PilaPop (Env) SI Izquierda (PilaTope(Env), t, S[i]) ENTONCES PilaPush (Env, t) PilaPush (Env, i) i < i+1 FIN_SI
S
0
1
23
4
56
7
8
9
0 1 2
Envi=4 t=3Izquierda(2,3,4)=F
0 1
Envi=4 t=2Izquierda(1,2,4)=V
0 1 2
Envi=5 t=4Izquierda(2,4,5)=V
![Page 16: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/16.jpg)
La envolvente convexaAlgoritmo: Graham's scan
t < PilaPop (Env) SI Izquierda (PilaTope(Env), t, S[i]) ENTONCES PilaPush (Env, t) PilaPush (Env, i) i < i+1 FIN_SI
S
0
1
23
4
5
6
7
8
9
0 1 2 4
Envi=6 t=5Izquierda(4,5,6)=V
0 1 2 4 5
Envi=7 t=6Izquierda(5,6,7)=V
0 1 2 4 5 6
Envi=8 t=7Izquierda(6,7,8)=F
![Page 17: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/17.jpg)
La envolvente convexaAlgoritmo: Graham's scan
t < PilaPop (Env) SI Izquierda (PilaTope(Env), t, S[i]) ENTONCES PilaPush (Env, t) PilaPush (Env, i) i < i+1 FIN_SI
S
0
1
23
4
5
6
7
8
9
0 1 2 4 5
Envi=8 t=6Izquierda(5,6,8)=F
0 1 2 4
Envi=8 t=5Izquierda(4,5,8)=F
i=8 t=4Izquierda(2,4,8)=V
0 1 2
Env
![Page 18: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/18.jpg)
La envolvente convexaAlgoritmo: Graham's scan
MIENTRAS i < n1 REPETIR t < PilaPop (Env) SI Izquierda (PilaTope(Env), t, S[i]) ENTONCES PilaPush (Env, t) PilaPush (Env, i) i < i+1 FIN_SI FIN_MIENTRAS
S
0
1
23
4
5
6
7
8
9
0 1 2 4
Envi=9 t=8Izquierda(4,8,9)=V
0 1 2 4 8 9
Envi=10
![Page 19: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/19.jpg)
La envolvente convexaAlgoritmo: Graham's scan
S
0
1
23
4
5
6
7
8
9
0 1 2 4 8 9
EnvLa solución son los puntos de la envolvente ordenados
Tiempo de ejecución:mínimo O(n)ordenación O(n log n)bucle principal O(2n)
Teorema:El cálculo de la envolventeconvexa utilizando el métodode Graham se realiza en tiempoóptimo Ω (n log n)
![Page 20: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/20.jpg)
La envolvente convexaAlgoritmo: La marcha de Jarvis (gift wrapping)
S
Basado en la Propiedad 2Un segmento definido por dos puntos x,y ∈S es una arista dela envolvente convexa sii el resto de puntos de S queda a un lado del segmento xy
La mejora de Jarvis: si el segmento xypertenece a la envolvente, el siguiente segmento será yz
xy
z
![Page 21: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/21.jpg)
0
La envolvente convexaAlgoritmo: La marcha de Jarvis
S
1. Encontrar el punto de menor ordenada (pertenece a la envolvente) 2. Encontrar el punto s
1 tal que s
0s
1 sea
el segmento con menor ángulo partiedo de s
0
3. Encontrar el punto s2 tal que s
1s
2 sea
el segmento con menor ángulo partiedo del ángulo de s
0s
1
. . . . .
n1. Encontrar el punto sn1
tal que s
n2s
n1 sea el segmento con menor
ángulo partiendo del ángulo de sn3
sn2
![Page 22: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/22.jpg)
0
La envolvente convexaAlgoritmo: La marcha de Jarvis
S
1. Encontrar el punto de menor ordenada (pertenece a la envolvente) 2. Encontrar el punto s
1 tal que s
0s
1 sea
el segmento con menor ángulo partiedo de s
0
3. Encontrar el punto s2 tal que s
1s
2 sea
el segmento con menor ángulo partiedo del ángulo de s
0s
1
. . . . .
n1. Encontrar el punto sn1
tal que s
n2s
n1 sea el segmento con menor
ángulo partiendo del ángulo de sn3
sn2
1
![Page 23: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/23.jpg)
0
La envolvente convexa
S
1. Encontrar el punto de menor ordenada (pertenece a la envolvente) 2. Encontrar el punto s
1 tal que s
0s
1 sea
el segmento con menor ángulo partiedo de s
0
3. Encontrar el punto s2 tal que s
1s
2 sea
el segmento con menor ángulo partiedo del ángulo de s
0s
1
. . . . .
n1. Encontrar el punto s0 tal que
sn1
s0 sea el segmento con menor
ángulo partiendo del ángulo de sn2
sn1
1
2
Algoritmo: La marcha de Jarvis
![Page 24: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/24.jpg)
La envolvente convexaLa solución son los puntos de la envolvente ordenados
0
La envolvente convexa
S
1
2
Tiempo de ejecución:mínimo O(n)Para k puntos O(n) O(k∙n)
Teorema:El cálculo de la envolventeconvexa utilizando el métodode Jarvis (gift wrapping) se realiza en tiempo O(n2)
Algoritmo: La marcha de Jarvis
0
La envolvente convexa
S
1
2
![Page 25: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/25.jpg)
La envolvente convexaEl tiempo de ejecución depende del valor de k
Tiempo de ejecución: O(n2)
La envolvente convexaAlgoritmo: La marcha de Jarvis
La envolvente convexa
Tiempo de ejecución: O(3n)
![Page 26: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/26.jpg)
La envolvente convexaLa envolvente convexa
Algoritmo: QuckhullLa envolvente convexa
Basado en el método de ordenación quicksort
min_y
min_x
max_y
max_y
puntos interiores(no se vuelven a procesar)
![Page 27: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/27.jpg)
La envolvente convexaLa envolvente convexa
Algoritmo: QuckhullLa envolvente convexa
Localizar 2 puntos extremos a, b de S
FUNCION QuickHull(a,b,S) SI NOT Vacio(S) c ← punto más lejano de ab A ←puntos a la derecha de ac B ←puntos a la derecha de cb RETURN QuickHull(a,c,A)+c+ +QuickHull(c,b,B) FIN_SI FIN_FUNCION a
b
c
![Page 28: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/28.jpg)
a
b
c
a
b
c
La envolvente convexaLa envolvente convexa
Algoritmo: QuckhullLa envolvente convexa
Localizar 2 puntos extremos a, b de S
FUNCION QuickHull(a,b,S) SI NOT Vacio(S) c ← punto más lejano de ab A ←puntos a la derecha de ac B ←puntos a la derecha de cb RETURN QuickHull(a,c,A)+c+ +QuickHull(c,b,B) FIN_SI FIN_FUNCION
a
b
c
![Page 29: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/29.jpg)
Algoritmo: Quckhull
Tiempo de ejecución en el peor de los casos:ocurre cuando todos los puntos están en la envolventeT(n) = T(n1)+O(n) O(n2)
Tiempo de ejecución en el mejor de los casos:ocurre cuando se realiza unasola división
La envolvente convexa
![Page 30: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/30.jpg)
Algoritmo: IncrementalBasado en el siguiente paradigma: se resuelve el problema para un tamaño i1, se añade un nuevo punto i, obteniéndose un nuevoresultado
s0,...,s
i1
si⊄CH(s
0,...,s
i1)
si⊂CH(s
0,...,s
i1)
descartar estos puntos
La envolvente convexa
![Page 31: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/31.jpg)
Algoritmo: Incremental
s0,...,s
i1
Conocer puntos tangentes
FUNCIÓN PuntosTangentes (S,n, q):k,lENTRADA: S: polígono convexo de tamaño n q: nuevo puntoSALIDA: k y l, puntos tangentesINICIO k ← 1 l ← 1 PARA i ← 0 HASTA n1 REPETIR SI XOR (Izquierda_sobre (S[i1],S[i],q), Izquierda_sobre(S[i],S[i+1],q)) ENTONCES SI k=1
ENTONCES k← i SINO l←i; SALIR_BUCLE;
FIN_SI FIN_PARAFIN
La envolvente convexa
i
i1
i+1
q
ID
punto tangente
![Page 32: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/32.jpg)
Algoritmo: Incremental
s0,...,s
i1
Conocer puntos tangentes
FUNCIÓN PuntosTangentes (S,n, q):k,lENTRADA: S: polígono convexo de tamaño n q: nuevo puntoSALIDA: k y l, puntos tangentesINICIO k ← 1 l ← 1 PARA i ← 0 HASTA n1 REPETIR SI XOR (Izquierda_sobre (S[i1],S[i],q), Izquierda_sobre(S[i],S[i+1],q)) ENTONCES SI k=1
ENTONCES k← i SINO l←i; SALIR_BUCLE;
FIN_SI FIN_PARAFIN
La envolvente convexa
i
i1
i+1
q
DD
punto NOtangente
![Page 33: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/33.jpg)
Algoritmo: Incremental
s0,...,s
i1
Conocer puntos tangentes
FUNCIÓN PuntosTangentes (S,n, q):k,lENTRADA: S: polígono convexo de tamaño n q: nuevo puntoSALIDA: k y l, puntos tangentesINICIO k ← 1 l ← 1 PARA i ← 0 HASTA n1 REPETIR SI XOR (Izquierda_sobre (S[i1],S[i],q), Izquierda_sobre(S[i],S[i+1],q)) ENTONCES SI k=1
ENTONCES k← i SINO l←i; SALIR_BUCLE;
FIN_SI FIN_PARAFIN
La envolvente convexa
i
i1
i+1
q
DD
punto NOtangente
![Page 34: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/34.jpg)
Algoritmo: Incremental
s0,...,s
i1
Conocer puntos tangentes
FUNCIÓN PuntosTangentes (S,n, q):k,lENTRADA: S: polígono convexo de tamaño n q: nuevo puntoSALIDA: k y l, puntos tangentesINICIO k ← 1 l ← 1 PARA i ← 0 HASTA n1 REPETIR SI XOR (Izquierda_sobre (S[i1],S[i],q), Izquierda_sobre(S[i],S[i+1],q)) ENTONCES SI k=1
ENTONCES k← i SINO l←i; SALIR_BUCLE;
FIN_SI FIN_PARAFIN
La envolvente convexa
i
i1 i+1
q
D I
punto tangente
![Page 35: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/35.jpg)
Algoritmo: Incremental
s0,...,s
i1
La envolvente convexaAñadir el punto a la envolvente
CH(s0,...,s
i1,q)= s
0,s
1,...,s
k1,s
k,q,s
l,s
l+1,s
l+2
kk1
k+1k
l1
ll+1
Nota:k y l son los puntostangentes, pero sabemosel orden de aparición en la secuencia
![Page 36: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/36.jpg)
Algoritmo: IncrementalLa envolvente convexa
Tiempo de ejecución:1. Comenzar con tres puntos (un triángulo siempre en convexo)
2. Para i=0 HASTA n3 puntos O(n2) calcular si está contenido en el polígono O(i) calcular tangentes O(i)
Tiempo de ejecución para algoritmo mejorado:1. Ordenar los puntos de izquierda a derecha O(n logn)1. Comenzar con tres puntos (un triángulo siempre es convexo)
2. Para i=0 HASTA n3 puntos O(n logn) calcular tangentes en tiempo O(log i)
![Page 37: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/37.jpg)
Algoritmo: Divide y Vencerás
Basado en el paradigma: CH(S) = CH(s0,...,s
k1)∪ CH(s
k,...,s
n1)
La envolvente convexa
S
1. Ordenar S por la coordenada x2. Dividir S en dos subconjuntos, S
I el
de la izquierda y SDel de la derecha,
ambos de tamaño n/23. Construir CH(S
I) y CH(S
D)
recursivamente4. Mezclar CH(S
I) y CH(S
D) consiguiendo
CH(S)
SI
SD
![Page 38: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/38.jpg)
Algoritmo: Divide y VencerásLa envolvente convexa
S
SI
SD
Mezclar las dos envolventes convexas
FUNCION MezclarEnvolventes (EI, ED: Poligono, n,m:Entero): E:PoligonoINICIO MenorTangente (EI, ED, n, m, a, b) MayorTangente (EI, ED, n, m, c, d) E < a + b +b+1,...,d1 + d + c + c+1,...,a1FIN
a
b
c
d
![Page 39: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/39.jpg)
Algoritmo: Divide y VencerásLa envolvente convexa
S
Mezclar las dos envolventes convexas
FUNCION MezclarEnvolventes (EI, ED: Poligono, n,m:Entero): E:PoligonoINICIO MenorTangente (EI, ED, n, m, a, b) MayorTangente (EI, ED, n, m, c, d) E < a + b +b+1,...,d1 + d + c + c+1,...,a1FIN
a
c
b
d
![Page 40: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/40.jpg)
Algoritmo: Divide y VencerásLa envolvente convexa
Cálculo de la menor tangente
FUNCION MenorTangente (EI, ED: Poligono, n, m: Entero):a,b:EnteroINICIO a < MasDecha (EI, n) b < MasIzda (ED, m) REPETIR aa < a bb < n MIENTRAS NO (TangenteMenor (EI,n,a,b)) a < (a1+n) mod n FIN_MIENTRAS MIENTRAS NO (TangenteMenor (ED,m,a,b)) b < (b+1) mod n FIN_MIENTRAS HASTA (aa=a AND bb=b)FIN
0 12
3
45
0
1
2
3
4
![Page 41: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/41.jpg)
Algoritmo: Divide y VencerásLa envolvente convexa
Cálculo de la menor tangente
FUNCION MenorTangente (EI, ED: Poligono, n, m: Entero):a,b:EnteroINICIO a < MasDecha (EI, n) b < MasIzda (ED, m) REPETIR aa < a bb < n MIENTRAS NO (TangenteMenor (EI,n,a,b)) a < (a1+n) mod n FIN_MIENTRAS MIENTRAS NO (TangenteMenor (ED,m,a,b)) b < (b+1) mod n FIN_MIENTRAS HASTA (aa=a AND bb=b)FIN
0 12
3
45
0
1
2
3
4
![Page 42: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/42.jpg)
Algoritmo: Divide y VencerásLa envolvente convexa
Cálculo de la menor tangente
FUNCION MenorTangente (EI, ED: Poligono, n, m: Entero):a,b:EnteroINICIO a < MasDecha (EI, n) b < MasIzda (ED, m) REPETIR aa < a bb < n MIENTRAS NO (TangenteMenor (EI,n,a,b)) a < (a1+n) mod n FIN_MIENTRAS MIENTRAS NO (TangenteMenor (ED,m,a,b)) b < (b+1) mod n FIN_MIENTRAS HASTA (aa=a AND bb=b)FIN
0 12
3
45
0
1
2
3
4
![Page 43: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/43.jpg)
Algoritmo: Divide y Vencerás
Tiempo de ejecución:1. Ordenar O(n logn)
2. Proceso recursivo Menor y mayor tangente O(n)
Ecuaciones de recurrencia:
![Page 44: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/44.jpg)
Algoritmo: diagrama polar
Basado en la Propiedad 2, pero mejorando la marcha de Jarvis
El diagrama polar es una teselación del plano que asigna una región polar a cada punto s
i de S, de modo que dicha región
es el lugar de los puntos más cercanos angularmente a si que
a ningún otro sj de S.
La cercanía angular debe ser considerada tomando un ángulode partida y una dirección de partida.
De algún modo el diagrama polar es un diagrama de Voronoi queutiliza el criterio del menor ángulo polar en vez de la menordistancia euclídea
![Page 45: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/45.jpg)
Cualquier punto x situado en esta regiónve primero al punto s
i antes que a
cualquier otro, al realizar un barridoangular en sentido antihorario y
partiendo del ángulo 0
Algoritmo: diagrama polar
S
si
x
![Page 46: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/46.jpg)
Algoritmo: diagrama polar
S
Existe una propiedad del diagrama polarque permite el cálculo de la envolventeconvexa: aquellos ejes polares oblicuosque no intersectan con otros ejes partende puntos que están en la porciónderecha de la envolvente convexa
![Page 47: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/47.jpg)
Algoritmo: diagrama polar
ALGORITMO DP (VAR S:NubePuntos, n:entero, VAR Env:Poligono)ENTRADA: La nube de puntos S de tamaño nSALIDA: La envolvente convexa de S, CH(S)INICIO OrdenarDescendiente(S,n) PilaCrea(Env) PilaPush(Env,S[0]) PilaPush(Env,S[1]) PARA i=2; i < n; i < i+1 REPETIR t < PilaPop(Env) MIENTRAS (NOT PilaVacia(Env) AND (la recta que pasa por los puntos TopePila(Env) y t intersecta con el semieje horizontal que parte de s[i] )) t<PiPop (Env) FIN_MIENTRAS PilaPush(t) PilaPush(S[i]) FIN_MIENTRASFIN
![Page 48: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/48.jpg)
Algoritmo: diagrama polar
S
En realidad la envolvente convexa es un subproducto del cálculo del diagramapolar: el conjunto de puntos que permanecen en la pila tras el proceso coincidecon la porción derecha de la envolvente convexa de S. El siguiente ejemplo muestra el estado de la pila al final de cada iteración
0
1
234
56
78
9
0 2
0 2 3
0 4
i=2
i=3
i=4
0 4 5
0 4 5 6
0 4 7
i=5
i=6
i=7
0 4 7 8 i=7
0 4 7 9 i=7
![Page 49: La envolvente convexa - Informática UPPueblainformatica.uppuebla.edu.mx/~abenitez/Cursos/verano2015/... · 2015-05-29 · Algoritmos elementales Dado un conjunto S, encontrar todos](https://reader030.fdocumento.com/reader030/viewer/2022040616/5f14f34fb862d171bf54b9d4/html5/thumbnails/49.jpg)
BibliografíaLa envolvente convexa
O´ROURKE Joseph. Computational Geometry in C. Cambridge University Press. 1998 (capítulo 3)
PREPARATA F.P., SHAMOS M.I. Computational Geometry. An Introduction. SpringerVerlag. 1985 (capítulo 3)