• Author / Uploaded
• Ruth Rojas Ramirez

Citation preview

ALGORITMO DE UN CASCO CONVEXO Introducción El tema escogido para el trabajo de investigación se basa en algoritmo de un casco convexo este algoritmo tiene como función principal envolver una serie de puntos, presentes en un plano a lo largo de los ejes x, y, Z en una envoltura o casco convexo lo cual encierra la mayor cantidad de puntos utilizando el menos número de líneas posibles para unirlas entre sí. El casco convexo se puede definir de diferentes maneras, todas son equivalentes entre sí: 

Conjunto convexo mínimo que contiene x, donde x representa el conjunto acotado de los puntos en el espacio.



La intersección de todos los conjuntos convexos que contienen a x.



El conjunto de todas las combinaciones convexas de puntos en X.



La unión de todos los simplex con vértices en x.

El casco convexo tiene aplicaciones en muchas áreas, que incluyen estadística, gráficas por computadora y procesamiento de imágenes. Por ejemplo, en estadística, los puntos de un conjunto de datos que determinan su casco convexo pueden ser puntos extremos que en realidad no son representativos de los datos y se pueden descartar. En esta sección se presenta el algoritmo de Graham para calcular el casco convexo. En toda la sección, “conjunto de puntos” significa un “conjunto de puntos distintos”. El primer paso de este algoritmo consiste en encontrar el punto con la menor coordenada ordenada (menor coordenada en el eje y). Si hay más de un punto que cumpla esta condición, se escoge el punto con menor coordenada en el eje x. A este punto se lo nombra por la letra P. Este paso es de complejidad O(n), donde n es el número de puntos del problema. Después, el conjunto de puntos debe ser ordenado en orden creciente de ángulo abarcado entre el segmento que los une con el punto P y el eje ordenado. Para ello se pude utilizar cualquier algoritmo de ordenamiento. Para agilizar el proceso, se puede omitir el cálculo del ángulo ya que es suficiente con hallar sucotangente.

El algoritmo continúa tratando secuencia de puntos ordenados según el ángulo creciente. Para

cada punto se calcula si el movimiento desde los dos anteriores es un "giro a derecha" o un "giro a izquierda". Si el movimiento es dextrógiro, indica que el segundo punto de la terna no es parte de la envolvente convexa y debe dejar de considerarse en los cálculos y tomar el siguiente. Cuando se halla un giro a izquierda, el algoritmo pasa a calcular el siguiente punto. En caso de que existan puntos alineados pertenecientes a la envolvente, los centrales pueden ser descartados o considerados como parte de la misma. No es necesario calcular el ángulo entre tres puntos para saber si es un giro a derecha o a izquierda, pues puede conocerse ese dato con una sola operación aritmética. Para tres puntos

,

y

, se puede calcular el producto vectorial de los dos

vectores definidos por las coordenadas

,

y

,

, e tal manera

que el resultado se obtiene con la ecuación . Si el resultado es 0, los puntos están alineados, si es positivo, el giro es a izquierdas y, si es negativo, el giro es a derecha. Finalmente, con este proceso se vuelve al punto P de partida, momento en el que el algoritmo está completado y sólo quedan los puntos pertenecientes a la envolvente convexa correctamente ordenados.