Algoritmo de Lee



Sea P={p1,,pn} un polígono simple de n vértices, orientado en sentido positivo (contrario a las agujas del reloj). Tanto p1 (vértice de abcisa máxima) como pm (vértice de abcisa mínima) son puntos del cierre convexo CC(P). Además p1 y pm dividen P en dos subcadenas, superior (p1,p2,,pm) e inferior (pm,pm+1,,p1). Para determinar el cierre convexo CC(P), se aplicará el algoritmo de Lee sobre Pi y Ps para obtener sus respectivas cadenas convexas, siendo el cierre convexo total la conjunción de ambas. Consideraremos el cierre de la subcadena superior (p1,p2,,pm), que acorde con la terminología llamaremos cierre superior. El cierre inferior se construiría de forma análoga.

La subcadena (q1,q2,,qr), con q1=p1 y qr=pm, de (p1,p2,,pm) es el deseado cierre superior del polígono. Cada uno de los lados qiqi+1 (i=1,,r-1) puede verse intuitivamente como una "tapa del bolsillo" ki , donde ki es una subcadena de (p1,p2,,pm) cuyos primer y último vértices son respectivamente qi y qi+1.

El algoritmo va a lo largo de (p1,p2,,pm) y, en este proceso construye sucesivamente cada una de las "tapas" de todos los "bolsillos". Supongamos que la frontera ha sido tratada desde pi hasta pi+1 y que ps=qi-1 es un vértice que forma "tapa" con el último qi encontrado. La situación es la de la figura, donde el bolsillo ki-1 debe ser cerrado por la tapa qi-1qi. Llamaremos u al vértice que antecede a qi y v al vértice que sigue a qi en la frontera de P. Seguidamente, analizaremos cómo varía la cadena convexa en función de la posición de v, distinguiéndose 4 posibles regiones.

Si v está en la región 1, la frontera cae dentro del bolsillo. Avanzamos por la frontera de P hasta encontrar el primer vértice w fuera del bolsillo. En el siguiente paso, dicho vértice w encontrado será tratado como un punto en la región 2.

Si v está en la región 2, es un vértice del cierre convexo. Trazamos la línea que va desde v hasta la cadena (q1,,qi-1). Si la línea pasa por qr (r < i), entonces se borran los vértices qr+1,,qi y v pasa a ser qr+1.

Si v está en la región 3, es un vértice del cierre y se convierte en qi+1.

Si v está en la región 4, la frontera de P entra en el interior del cierre convexo. Con lo que habrá que seguir por el polígono hasta encontrar un lado que cumpla que uno de sus vértices no está en la región 4 o coincide con qm. Si coincide con pm, termina el algoritmo. En caso contrario, el extremo está en la región 3 ó en la 2 (casos anteriores).




Retroceso Programa