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

Вот'Пример полигона:

пример 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