Envoltura convexa - Historial de revisiones

Josefina: Texto reemplazado: «
» por «»

2019-08-09T00:56:26Z

Texto reemplazado: «<div align="justify">» por «»

Edeliochajc en 02:31 22 jun 2014

2014-06-22T02:31:56Z

Wendy idict en 15:44 25 jun 2012

2012-06-25T15:44:44Z

Yasielcm 93: /* Definiciones */

2011-08-21T20:13:37Z

‎Definiciones

Yasielcm 93: /* Definiciones */

2011-08-21T20:13:02Z

‎Definiciones

Yasielcm 93 en 20:12 21 ago 2011

2011-08-21T20:12:01Z

Yasielcm 93 en 20:09 21 ago 2011

2011-08-21T20:09:03Z

Candelaria2 jc en 21:54 18 ago 2011

2011-08-18T21:54:20Z

Juliogd ssp.jc en 15:59 16 ago 2011

2011-08-16T15:59:41Z

Juliogd ssp.jc: Página creada con '{{Ficha Software |nombre= Envoltura convexa |familia= |imagen= envolturac.jpg |tamaño= |descripción= Aplicación importante en el campo de la Geometría Computacional. |imagen...'

2011-08-16T15:13:39Z

Página creada con '{{Ficha Software |nombre= Envoltura convexa |familia= |imagen= envolturac.jpg |tamaño= |descripción= Aplicación importante en el campo de la Geometría Computacional. |imagen...'

Página nueva

{{Ficha Software
|nombre= Envoltura convexa
|familia=
|imagen= envolturac.jpg
|tamaño=
|descripción= Aplicación importante en el campo de la Geometría Computacional.
|imagen2=
|tamaño2=
|descripción2=
|creador=
|desarrollador=
|diseñador=
|modelo de desarrollo=
|fecha de creación=
|lanzamiento inicial=
|versiones=
|última versión estable=
|núcleo=
|tipo de núcleo=
|plataformas soportadas=
|género=
|sistemas operativos=
|idioma=
|licencia=
|premios=
|web=
}}
Es uno de los cálculos más importantes en Geometría Computacional con aplicaciones en distintas áreas, dentro y fuera de la Geometría Computacional.
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, etc.

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. [[Image:envcon1.jpg|thumb|left|Goma elástica]]

'''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. [[Image:envcon2.jpg|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.
[[Image:envcon3.jpg|thumb|left|Segmentos dentro de la envoltura]]

== 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.
[[Image:envcon4.jpg|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.
[[Image:envcon5.jpg|thumb|left|Puntos hacia un lado de la 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.
[[Image:envcon6.jpg|thumb|left|Mejora de Jarvis]]

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 ==
* [http://wwwdi.ujaen.es/asignaturas/gc/tema3.odp/ Envolvente convexa]

== Fuente ==
*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).

[[Category:Programación]]

@@ Línea 25: / Línea 25: @@
 |premios=
 |web=
-}}<div align="justify">
+}}
 '''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==

@@ Línea 37: / Línea 37: @@
 === Definición intuitiva ===
 [[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.
+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.

← Revisión anterior		Revisión del 21:54 18 ago 2011
Línea 1:		Línea 1:
		+	{{Normalizar}}
	{{Ficha Software		{{Ficha Software
	\|nombre= Envoltura convexa		\|nombre= Envoltura convexa

@@ Línea 25: / Línea 25: @@
 |premios=
 |web=
-}}
+}}<div align="justify">
 '''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==
 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]], etc.
+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.
@@ 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.
 == Definiciones ==
-'''Definición intuitiva:'''
+=== Definición intuitiva ===
 [[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:'''
+==== 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.
 [[Archivo:envcon2.jpg|250px|thumb|left|Polígono que contiene a todos los elementos]].
-'''Definición 2:'''
+==== 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.
@@ Línea 52: / Línea 51: @@
 == Propiedades ==
-'''Propiedad 1:'''
+=== 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.
 [[Archivo:envcon4.jpg|250px|thumb|left|Puntos dentro de triángulos]]
-'''Propiedad 2:'''
+=== 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.
@@ Línea 82: / Línea 81: @@
 * [http://wwwdi.ujaen.es/asignaturas/gc/tema3.odp/ Envolvente convexa]
-== Fuente ==
+== Fuentes ==
 *O´ROURKE Joseph. Computational Geometry in C. Cambridge. University Press. 1998 (capítulo 3).

@@ Línea 38: / Línea 38: @@
 '''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.
-[[Image:envcon1.jpg|200px|Goma elástica]]
+[[Archivo:envcon1.jpg|250px|thumb|right|Goma elástica]]
 '''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.
-[[Image:envcon2.jpg|200px|Polígono que contiene a todos los elementos]].
+[[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.
-[[Image:envcon3.jpg|200px|Segmentos dentro de la envoltura]]
+[[Archivo:envcon3.jpg|250px|thumb|right|Segmentos dentro de la envoltura]]
 == Propiedades ==
@@ Línea 55: / Línea 54: @@
 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.
-[[Image:envcon4.jpg|200px|Puntos dentro de triángulos]]
+[[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.
-[[Image:envcon5.jpg|200px|Puntos hacia un lado de la recta]]
+[[Archivo:envcon5.jpg|250px|thumb|right|Puntos hacia un lado de la recta]]
 == Cálculo de la envoltura convexa ==
@@ Línea 67: / Línea 66: @@
 Basado en la Propiedad 2
 La mejora de Jarvis: si el segmento xy pertenece a la envolvente, el siguiente segmento será yz.
-[[Image:envcon6.jpg|200px|Mejora de Jarvis]]
+[[Archivo:envcon6.jpg|250px|thumb|left|Mejora de Jarvis]]
 Pasos del algoritmo:

@@ Línea 1: / Línea 1: @@
 {{Ficha Software
 |nombre= Envoltura convexa
@@ Línea 5: / Línea 4: @@
 |imagen= envolturac.jpg
 |tamaño=
-|descripción= Aplicación importante en el campo de la Geometría Computacional.
+|descripción= Aplicación importante en el campo de la geometría computacional.
 |imagen2=
 |tamaño2=
@@ Línea 27: / Línea 26: @@
 |web=
 }}
-Es uno de los cálculos más importantes en Geometría Computacional con aplicaciones en distintas áreas, dentro y fuera de la Geometría Computacional.
+'''<div align="justify">'''
-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, etc.
+'''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.
 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:'''
@@ Línea 82: / Línea 83: @@
 == Fuente ==
 *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).
 [[Category:Programación]]

Envoltura convexa - Historial de revisiones

Josefina: Texto reemplazado: «» por «»

Edeliochajc en 02:31 22 jun 2014

Wendy idict en 15:44 25 jun 2012

Yasielcm 93: /* Definiciones */

Yasielcm 93: /* Definiciones */

Yasielcm 93 en 20:12 21 ago 2011

Yasielcm 93 en 20:09 21 ago 2011

Candelaria2 jc en 21:54 18 ago 2011

Juliogd ssp.jc en 15:59 16 ago 2011

Juliogd ssp.jc: Página creada con '{{Ficha Software |nombre= Envoltura convexa |familia= |imagen= envolturac.jpg |tamaño= |descripción= Aplicación importante en el campo de la Geometría Computacional. |imagen...'

Josefina: Texto reemplazado: «
» por «»