Algoritmo de Melkman



 
  Sea P={p1,,pn} un polígono simple de n vértices, orientado en sentido positivo (contrario a las agujas del reloj). El cierre convexo se va construyendo en una lista de vértices D=(db,,dt), donde la variable b apunta a la base de la lista y t es la cima. El vértice v es el vértice del polígono que se está considerando.

Los pasos que sigue el algoritmo son:

      1. La semilla de la lista del cierre D, se construye en función de la situación de los tres primeros vértices del polígono. Si (p1,p2,p3) es un giro a la derecha, la semilla de partida es D=( p3, p2, p1,p3). En caso contrario, la semilla es D=( p3,p1,p2,p3).
      2. Mientras queden vértices en P, se busca el primer vértice v que intervenga en el cierre. La condición que debe cumplir v es que (v,pb,pb+1) y/o (pt-1,pt,v) sean giros a izquierda. El algoritmo termina cuando se han tratado todos los vértices de P.
      3. Mientras (pt-1,pt,v) sea un giro a derecha se saca de la lista del cierre D el vértice pt. Tras organizar convenientemente la lista D, se le inserta en su inicio el vértice v.
      4. Mientras (pb,pb+1,v) sea un giro a derecha se saca de la lista del cierre D el vértice pb. Tras organizar la lista D, se inserta el vértice v al final.

 
 



Retroceso Programa