Algoritmo de Sklansky



 
  Sea P={p1,,pn} un polígono simple de n vértices, orientado en sentido positivo (contrario a las agujas del reloj). El algoritmo procesa secuencialmente cada uno de los vértices, construyendo incrementalmente el cierre Q.

Los pasos que sigue el algoritmo son:

      1. Se parte de un polígono P={p1,,pn, p1}. Como puede apreciarse el vértice p1 está tanto al inicio como al final del polígono.
      2. Se insertan en el cierre Q los dos primeros vértices del polígono.
      3. Mientras queden vértices en P, se trata cada vértice v de la siguiente manera: se borra la cima de la pila, hasta que el vértice que está por debajo de la cima, la cima y el vértice v no sean un vértice a derecha, entonces se inserta v en la pila.
Aunque es muy simple, este algoritmo falla para polígonos con bolsillos. Este es el caso del polígono ejemplo.


 

Retroceso Programa