Metode ..
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...
Regístrate para leer el documento completo.