Имеется полигон, заданный набором точек a(1), a(2), ... a(n) (последняя точка не совпадает с первой)
В полигоне имеются самопересечения отрезков (из которых состоит полигон).
Необходимо переставить точки a(i) и добавить новые точки так, чтобы самопересечений не было.
В аттаче находится картинка, поясняющая пример

Присоединённый файл ( Кол-во скачиваний: 16 )
 ______.JPG 14,90 Kb

Ничего более умного, чем определение пересечения отрезков попарно, в голову не приходит. Можно, впрочем, попробовать поиграться с заливкой областей.

Ищем точку пересечения отрезков, удаляем старую, добавляем две новых, немного из "раздвигая" или  "не раздвигая". В чём проблема?

Проблема в том, чтобы верно учесть порядок добавленных точек. И еще больше проблем возникает, когда пересечений становится много - приходится много всего учитывать.
Rickert, я пробовал предложенный способ, но это приводит к большой техническое проблеме (во всяком случае для меня). 

Никакой проблемы тут нет. Точки являются односвязным или двусвязным кольцевым списком (как построишь). Введение пары точек, устраняющей пересечение, состоит из разрыва списка на 2 незамкнутых цепи и собсно введения двух новых точек (с одинаковыми координатами!) в список, соединяющих эти цепи обратно в кольцо. Какие пары сцеплять каждой из точек, определяется легко - во-первых, список не должен развалиться на два несвязанных кольца, во-вторых, соединяемые точкой отрезки должны быть соседними при обходе вокруг точки по (или против) часовой стрелки.

vasmt, можно тупо спозиционировать полигон в начало координат и обойти точки почасовой/против часовой стрелки, тем самым размечая.

Rickert, ты не забыл, что полигон самопересекающийся?