Metode ..

Solo disponible en BuenasTareas
  • Páginas : 2 (369 palabras )
  • Descarga(s) : 0
  • Publicado : 20 de noviembre de 2011
Leer documento completo
Vista previa del texto
mEl 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 puntocon 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 serordenado 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, sepuede omitir el cálculo del ángulo ya que es suficiente con hallar su cotangente.

El algoritmo continúa tratando secuencia de puntos ordenados según el ángulo creciente. Para cada punto se calculasi 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 ydebe 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 alineadospertenecientes 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 aizquierda, pues puede conocerse ese dato con una sola operación aritmética. Para tres puntos (x1,y1), (x2,y2) y (x3,y3), se puede calcular el producto vectorial de los dos vectores definidos por lascoordenadas (x1,y1), (x2,y2) y (x1,y1), (x3,y3), de tal manera que el resultado se obtiene con la ecuación (x2 − x1)(y3 − y1) − (y2 − y1)(x3 − x1). Si el resultado es 0, los puntos está alineados, si espositivo, 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...
tracking img