[hasherfrog]

Я когда-то занимался похожим вопросом: отрезание маленьких "петелек" на невыпуклых самопересекающихся полигонах. Сразу могу сказать, что абсолютно весь алгоритм пришлось писать с нуля - в сети ничего нету :[

Могу "идею" предложить. Пару классов подкинуть. Но разобраться с моим кодом будет очень-очень сложно, там всё для автокада R2000. Даже скомпилить будет невозможно, если нет нужных библиотек/хидеров (у меня уже ддавно их нет) %[

[[mzd]]

В нете нашел такой алгоритм

Одновременное проведение операций проверки на выпуклость и разбиение простого невыпуклого многоугольника на выпуклые обеспечивается методом переноса и поворотов окна. Алгоритм метода при обходе вершин многоугольника против часовой стрелки состоит в следующем: 1. Для каждой i-й вершины многоугольник сдвигается для переноса упомянутой вершины в начало координат. 2. Многоугольник поворачивается против часовой стрелки для совмещения (i+1)-й вершины с положительной полуосью X. Вектор внутреннего перпендикуляра к ребру, образованному вершинами i-й и (i+1)-й, вычисляется поворотом ребра на -90° против часовой стрелки. 3. Анализируется знак Y-координаты (i+2)-й вершины. Если Yi+2 і 0, то в (i+1)-й вершине выпуклость. Если Yi+2 і 0, то в (i+1)-й вершине невыпуклость. Если имеется невыпуклость, то многоугольник разрезается на два вдоль положительной полуоси X. Для этого вычисляется пересечение положительной полуоси X с первой из сторон. Формируются два новых многоугольника: первый многоугольник - вершины с (i+1)-й до точки пересечения - вершины 2, 3, 4, 6, 7, [7\tilde], второй многоугольник - все остальные вершины - вершины [7\tilde], 8, 0, 1. Так как вновь полученные многоугольники могут в свою очередь оказаться невыпуклыми, алгоритм применяется к ним, пока все многоугольники не станут выпуклыми.

Погмогите загнать его в эту программу, а то с поворотами я совсем запутался.