Нужно сделать выпуклую триангуляцию многоугольника можно на основе - этого (
http://www.opita.net/node/29) только чтобы все вершины соединялись.+ оценка сложности кода подробнее. На основе второй картинки нужно сделать чтобы она была всегда выпуклая а не как в программе.