Diferencia entre revisiones de «Envoltura convexa»
m (Texto reemplazado: «<div align="justify">» por «») |
|||
| (No se muestran 5 ediciones intermedias de 3 usuarios) | |||
| Línea 26: | Línea 26: | ||
|web= | |web= | ||
}} | }} | ||
| − | |||
'''Envoltura convexa.''' Es uno de los cálculos más importantes en [[geometría computacional]] con aplicaciones en distintas áreas, dentro y fuera de la misma. | '''Envoltura convexa.''' Es uno de los cálculos más importantes en [[geometría computacional]] con aplicaciones en distintas áreas, dentro y fuera de la misma. | ||
==Características== | ==Características== | ||
Envolvente convexa de objetos, o también conocido como cierre | Envolvente convexa de objetos, o también conocido como cierre | ||
| − | convexo consiste en recubrimiento o cobertura que encierra a todos los elementos de un conjunto, sin vértices cóncavos, de puntos, polígonos, círculos, objetos [[3D]] | + | convexo consiste en recubrimiento o cobertura que encierra a todos los elementos de un conjunto, sin vértices cóncavos, de puntos, polígonos, círculos, objetos [[Animación 3D|3D]]. |
La computación del cierre convexo de una nube finita de puntos, especialmente en el plano, ha sido exhaustivamente estudiada y tiene aplicaciones, como por ejemplo, en el procesado de imágenes y en localización. | La computación del cierre convexo de una nube finita de puntos, especialmente en el plano, ha sido exhaustivamente estudiada y tiene aplicaciones, como por ejemplo, en el procesado de imágenes y en localización. | ||
| Línea 36: | Línea 35: | ||
Desafortunadamente, no es posible construir la definición intuitiva de cierre convexo citada anteriormente de forma natural, por lo que hay que identificar las nociones apropiadas que nos conduzcan a un algoritmo. | Desafortunadamente, no es posible construir la definición intuitiva de cierre convexo citada anteriormente de forma natural, por lo que hay que identificar las nociones apropiadas que nos conduzcan a un algoritmo. | ||
== Definiciones == | == Definiciones == | ||
| − | + | === Definición intuitiva === | |
| − | Supongamos que cada punto del plano está representado como la cabeza de una puntilla hincada perpendicularmente sobre una superficie plana. Si tomamos una goma elástica que envuelva a todas las puntillas, el resultado en la envolvente convexa. | + | [[Archivo:envcon1.jpg|250px|thumb|right|Goma elástica]] |
| − | + | Supongamos que cada punto del plano está representado como la cabeza de una [[puntilla]] hincada perpendicularmente sobre una superficie plana. Si tomamos una goma elástica que envuelva a todas las puntillas, el resultado en la envolvente convexa. | |
| − | + | ==== Definición 1 ==== | |
La envolvente convexa de un conjunto de puntos S es el [[Polígono|Polígono]] convexo P que contiene a todos los elementos de S con menor área (o perímetro) posible. | La envolvente convexa de un conjunto de puntos S es el [[Polígono|Polígono]] convexo P que contiene a todos los elementos de S con menor área (o perímetro) posible. | ||
| − | [[ | + | [[Archivo:envcon2.jpg|250px|thumb|left|Polígono que contiene a todos los elementos]]. |
| − | + | ==== Definición 2 ==== | |
La envolvente convexa de un conjunto de puntos S es el [[Polígono|Polígono]] convexo P si para cada par de puntos x e y de S, el segmento xy siempre está contenido en P. | La envolvente convexa de un conjunto de puntos S es el [[Polígono|Polígono]] convexo P si para cada par de puntos x e y de S, el segmento xy siempre está contenido en P. | ||
| − | [[ | + | [[Archivo:envcon3.jpg|250px|thumb|right|Segmentos dentro de la envoltura]] |
| − | + | ||
== Propiedades == | == Propiedades == | ||
| − | + | === Propiedad 1 === | |
El cálculo de la envolvente convexa consiste en encontrar todos los puntos extremos del conjunto S. Un punto x de S es no extremo si existe un triángulo con vértices en S (distintos de x) de forma que x esté dentro del triángulo. | El cálculo de la envolvente convexa consiste en encontrar todos los puntos extremos del conjunto S. Un punto x de S es no extremo si existe un triángulo con vértices en S (distintos de x) de forma que x esté dentro del triángulo. | ||
| − | [[ | + | [[Archivo:envcon4.jpg|250px|thumb|left|Puntos dentro de triángulos]] |
| − | + | === Propiedad 2 === | |
Un punto x de S es extremo si existe una recta pasando por x que deje al resto de puntos de S hacia un lado de dicha recta. | Un punto x de S es extremo si existe una recta pasando por x que deje al resto de puntos de S hacia un lado de dicha recta. | ||
| − | [[ | + | [[Archivo:envcon5.jpg|250px|thumb|right|Puntos hacia un lado de la recta]] |
== Cálculo de la envoltura convexa == | == Cálculo de la envoltura convexa == | ||
| Línea 67: | Línea 66: | ||
Basado en la Propiedad 2 | Basado en la Propiedad 2 | ||
La mejora de Jarvis: si el segmento xy pertenece a la envolvente, el siguiente segmento será yz. | La mejora de Jarvis: si el segmento xy pertenece a la envolvente, el siguiente segmento será yz. | ||
| − | [[ | + | [[Archivo:envcon6.jpg|250px|thumb|left|Mejora de Jarvis]] |
Pasos del algoritmo: | Pasos del algoritmo: | ||
| Línea 82: | Línea 81: | ||
* [http://wwwdi.ujaen.es/asignaturas/gc/tema3.odp/ Envolvente convexa] | * [http://wwwdi.ujaen.es/asignaturas/gc/tema3.odp/ Envolvente convexa] | ||
| − | == | + | == Fuentes == |
*O´ROURKE Joseph. Computational Geometry in C. Cambridge. University Press. 1998 (capítulo 3). | *O´ROURKE Joseph. Computational Geometry in C. Cambridge. University Press. 1998 (capítulo 3). | ||
última versión al 19:56 8 ago 2019
| ||||
Envoltura convexa. Es uno de los cálculos más importantes en geometría computacional con aplicaciones en distintas áreas, dentro y fuera de la misma.
Sumario
Características
Envolvente convexa de objetos, o también conocido como cierre convexo consiste en recubrimiento o cobertura que encierra a todos los elementos de un conjunto, sin vértices cóncavos, de puntos, polígonos, círculos, objetos 3D.
La computación del cierre convexo de una nube finita de puntos, especialmente en el plano, ha sido exhaustivamente estudiada y tiene aplicaciones, como por ejemplo, en el procesado de imágenes y en localización.
Desafortunadamente, no es posible construir la definición intuitiva de cierre convexo citada anteriormente de forma natural, por lo que hay que identificar las nociones apropiadas que nos conduzcan a un algoritmo.
Definiciones
Definición intuitiva
Supongamos que cada punto del plano está representado como la cabeza de una puntilla hincada perpendicularmente sobre una superficie plana. Si tomamos una goma elástica que envuelva a todas las puntillas, el resultado en la envolvente convexa.
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 S con menor área (o perímetro) posible.
.
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, el segmento xy siempre está contenido en P.
Propiedades
Propiedad 1
El cálculo de la envolvente convexa consiste en encontrar todos los puntos extremos del conjunto S. Un punto x de S es no extremo si existe un triángulo con vértices en S (distintos de x) de forma que x esté dentro del triángulo.
Propiedad 2
Un punto x de S es extremo si existe una recta pasando por x que deje al resto de puntos de S hacia un lado de dicha recta.
Cálculo de la envoltura convexa
En geometría computacional existen numerosos algoritmos para calcular la envoltura convexa de un conjunto finito de puntos, con diversos grados de complejidad computacional. La complejidad del algoritmo de resolución se suele estimar en función del número n de puntos de entrada, y el número h de puntos de la correspondiente envoltura convexa. Jarvis march o gift wrapping algorithm. Propuesto por R. A. Jarvis en 1973. Es uno de los más simples y posee una complejidad computacional O(nh). En el peor de los casos su complejidad será O(n2). Basado en la Propiedad 2 La mejora de Jarvis: si el segmento xy pertenece a la envolvente, el siguiente segmento será yz.
Pasos del algoritmo:
- Encontrar el punto de menor ordenada. (pertenece a la envolvente).
- Encontrar el puntos S1 tal que S0S1 sea el segmento con menor ángulos partiendo de S0.
- Encontrar el puntos S2 tal que S1S2 sea el segmento con menor ángulo partiendo del ángulo de S0S1.
- Encontrar el puntos S(n-1) tal que S(n-2)S(n-1) sea el segmento con menor ángulo partiendo del ángulo de S(n-3)S(n-2).
Otros algoritmos: Graham Scan. Publicado en 1972, es mucho más eficiente y posee una complejidad computacional O(n log n). Si los puntos se encuentran ordenados por una de las coordenadas o por el ángulo a un vector fijo entonces la complejidad es O(n). Divide and vencerás. Otro algoritmo de complejidad O(n log n) publicado en 1977 por Franco P. Preparata y Hong. También es aplicable al caso tridimensional.
Enlaces externos
Fuentes
- 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).
