Estoy atascado con este pequeño problema y mi algoritmo para resolver esto no es válido para todos los casos. ¿Alguien tiene una idea de cómo resolver esto?

Aquí hay un ejemplo de polígono:

ejemplo http://img148.imageshack.us/img148/8804/poly.png

Descripción formal

Tenemos una lista de puntos en orden CW que define el polígono. También podemos consultar si un punto es un punto de corte conis_cut(p), dóndep Es un punto dado. Ahora queremos calcular nuevos polígonos causados ​​por este "corte".

El algoritmo debería hacer esto:

Entrada:{a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}

Salida:{a, c1, c2}, {b, c4, c3, f, c2, c1}, {d, c6, c5}, {e, c3, c4, c, c5, c6}

Aquí mi algoritmo actual:

follow your points, CW
if the point is a cut point
-> go back trough the list looking for cut points
--- if next cut point is connected to the current cut point 
    and not part of the current poly, follow it
--- else keep searching
else
-> continue until you hit your starting point.
that's a poly
do this for every non-cut-point

Este algoritmo no se mantiene si se inicia enc of.