Я застрял с этой маленькой проблемой, и мой алгоритм для ее решения подходит не для всех случаев. У кого-нибудь есть идеи, как это решить?

Вот пример многоугольника:

пример http://img148.imageshack.us/img148/8804/poly.png

Формальное описание

У нас есть список точек в CW-порядке, определяющих многоугольник. Мы также можем запросить, является ли точка режущей точкой сis_cut(p), гдеp это заданная точка. Теперь мы хотим вычислить новые полигоны, вызванные этим «разрезом».

Алгоритм должен сделать это:

Входные данные:{a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}

Выход:{a, c1, c2}, {b, c4, c3, f, c2, c1}, {d, c6, c5}, {e, c3, c4, c, c5, c6}

Вот мой текущий алгоритм:

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

Этот алгоритм не работает, если вы начнете сc или жеf.