Envoltura convexa

Envoltura convexa Aplicación importante en el campo de la Geometría Computacional.

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.

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:

1. Encontrar el punto de menor ordenada. (pertenece a la envolvente).
2. Encontrar el puntos S1 tal que S0S1 sea el segmento con menor ángulos partiendo de S0.
3. Encontrar el puntos S2 tal que S1S2 sea el segmento con menor ángulo partiendo del ángulo de S0S1.
4. 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

• 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).