Convex hull

Lo primero que hay que tener en cuenta para poder realizar la tarea son los conceptos de cóncavo y convexo.
Cuando vemos la línea de la circunferencia desde el interior de la misma se trata de una curva cóncava, lo que se ve desde el exterior es una curva convexa.

http://prendetuneurona.blogspot.mx/2010/04/formulario-de-poligonos.html

El algoritmo que utilicé se llama jarvis, o también se le llama envoltura de regalo, ya que lo que hace es tomar un polígono cóncavo y envolverlo para hacerlo convexo.
El algoritmo de jarvis es un algoritmo que "envuelve" un conjunto de puntos en un "papel de regalo", empieza y termina en el mismo punto.
Así funciona el algoritmo:

• Teniendo un conjunto de puntos S, se agarra el putno P que tiene menor ordenada y mayor abscisa se traza una recta r que pasa por P y que sea paralela a las abscisa.
• Para cada punto de S se trazan lineas que los unan con P. El siguiente vértice del cierre convexo es el punto Q que forma el mínimo ángulo respecto a la recta r pasada.
• Si Q no es el punto inicial, se repite dos veces tomando P=Q y r como la recta formada por P y Q.

La idea básica del algoritmo consiste en pensar en una recta que esta siendo desplaza desde menos infinito hacia arriba hasta que toque un punto del conjunto de puntos. Después, la recta va redondeando la nube de puntos del lado positivo, gira en cada vértice hasta que toque el siguiente, de modo que al último la envuelve por completo.

Estos son algunos pequeños ejemplo de mi implementación con su tiempo de ejecución promediado de 30 repeticiones:

Tiempo de ejecución: 2.75483306198

Tiempo de ejecución: 1.9832565532

Código

Donde se manda llamar al método de convex hull:

Algoritmo:



Otro ejemplo

Tiempo de ejecución: 2.704533443

Código completo:


Repositorio