Quick Hull



Universidad de Guanajuato. Implementación de ConvexHull. 1

Implementación de Convex Hull (Gift Wrapping and divide and conquer)

Arriaga García Edgar Fernando, Barrón Hernández Linda, Chávez Ruiz Josué Israel, García Martínez Maricruz, Macías Meza Juan José, Martínez Rodríguez Diana, Rodríguez Meave Josué Rolando eferagarox@gmail.com, linda_barronn@hotmail.com, betty.boop-13@live.com,josuemeave@gmail.com, diana.mr91@gmail.com,

Existen muchas formas para llegar a la

Resumen- El método de convex hull trata sobre el implementación de un convex Hull como ha sido

rellenado de un conjunto de puntos en un espacio de dos, tres los comandos ya definidos en MATLAB, MAPLE

o más dimensiones de tal manera que los puntos mas

entre otros, y diferentes formas de llegar a la

extremos envuelvan todo el conjunto. Utilizando un espacio

solución por medio de implementación de métodos

de dos dimensiones se implementaran los algoritmos de Gift

Wrapping y Divide and Conquer. como vecinos cercanos, Gift Wrapping, divide and

conquer, KNN, fuzzy C-Means, HCM, método de

Valles, etc.

I. INTRODUCCIÓN Para nuestra implementación tomamos en cuentas

lenguajes como C, C++ y la librería grafica de

Conjunto Convexo: Una parte C de un espacio OpenGL para poder llegar a resolver por los

vectorial real es convexa si para cada par de puntos métodos Gift Wrapping and divide and conquer.

de C, el segmento que los une está totalmente

incluido en C; es decir, un conjunto es convexo si se

puede ir de cualquier punto a cualquier otro en línea II. OBJETIVOS

recta, sin salir del mismo. Tenemos como objetivo al realizar esta practica

Definición formal: C es convexo si y solo si para comprender el funcionamiento los métodos Gift

todo Wrapping y divide and conquer para

implementarlos y crear un Convex Hull.

(1) III. METODOLOGÍA

La manera de resolver el problema de divide and

La envolvente convexa, también denominada conquer fue

cierre convexo o convex hull, es uno de los más La filosofía que sigue este algoritmo es

fundamentales constructores geométricos. dividir el problema en casos más simples que son

Una idea intuitiva del significado del cierre más fáciles de resolver, después ir uniendo para

convexo es el contenido de la figura que formaría encontrar el resultado total.

una banda elástica que rodeara a una nube de puntos Para realizar la implementación de este

una vez que la soltáramos. algoritmo se utilizará una función recursiva, por lo

que lo primero que se tiene que analizar es la

condición de término, analizando el problema los

casos más simples a los que se puede llegar son:

• Un punto

• Dos puntos

• Tres puntos

La división se hace en base al eje x, cada una basándose en el punto medio entre el punto con la x

Universidad de Guanajuato. Implementación de ConvexHull. 2

mínima y la x máxima formando dos clusters, así sucesivamente hasta llegar a los casos más simples.

También hay un caso especial en el más de 3 puntos se encuentran en la misma coordenada x. Ya que ya no se pueden hacer más subdivisiones basadas en el eje pues se encuentran en la misma coordenada. Para este caso el criterio de división es dejar la mitad de los puntos en un cluster y el resto en el segundo.

Al hacer la unión entre los dos clusters generados en cada iteración se encontraran el punto con la Ymax y Ymin para cada uno.

Después de realizar la unión entre los cluster se deben eliminar los puntos que quedan dentro. Para este proceso se calcula el ángulo formado entre el punto Ymin y Ymax de cada cluster. En el caso del cluster de la izquierda se eliminan los puntos que formen un ángulo menor con respecto al punto de Ymin. En el caso del cluster de la derecha se eliminan los puntos que tengan el ángulo mayor con respecto al punto de la Y min.

Pseudocódigo

1. generar numeros aleatorios

2. Encontrar xmin, xmax, ymin, ymax

3. Sea S el conjunto de puntos dados en forma

aleatoria

Dividir S en dos clouster tomando como referencia xmin y xmax.

si hay un punto en algun clouster o, entonces lo tomamos como ymin y ymax

Si hay dos puntos en algun clouster, entonces los unimos y encontramos ymax y ymin

Si hay tres puntos en algun clouster, entonces formamos un triangulo y encontramos ymax y ymin.

Si hay más de tres puntos volvemos a dividir en 2.

4. Graficar los puntos y unirlos.

Y la manera en que resolvimos el de Gift Wrapping fue definiendo una estructura Point con valores enteros (x, y). Creamos una función para generar los puntos aleatoriamente. Tenemos cuatro funciones que nos sirven para encontrar xmin, ymin, xmax, ymax y otras cuatro funciones en las que definimos reglas para resolver el problema. También tenemos otras funciones para graficar como son display y reshape.

Pseudocódigo (Gift Wrapping)

1. Generar puntos aleatorios

2. Encontrar xmin, ymin, xmax, ymax.

3. Definir políticas (reglas)

3.1 Comenzamos en ymin, respecto a ymin agrupamos todos los puntos x<ymin.x y y>=ymin.y, después de agrupar volvemos a encontrar ymin hasta llegar al punto xmin.

3.2 Comenzamos en xmin, respecto a xmin agrupamos todos los puntos x>ymax.x y y>=ymax.y después de agrupar

Universidad de Guanajuato. Implementación de ConvexHull.

volvemos a encontrar xmin hasta llegar al punto ymax.

3.3 Comenzamos en ymax, respecto a ymax agrupamos todos los puntos x>ymax.x y y<=ymax.y después de agrupar volvemos a encontrar ymax hasta llegar al punto xmax.

3.4 Comenzamos en xmax, respecto a xmax

...