>>380
単に凸化するだけなら、
1. 凹点Aを探す
2. A-Bが他の辺と交わらないような点Bを探す
3. A-Bで分割、1に戻る
の繰り返しで出来る。

綺麗な分割にしようとすると、
・できれば分割数を最小にしたいとか、
・鈍角ができるだけ出ないようにしたいとか、
・切断する辺の長さを短くしたいとか、
いろいろあるけど、両立できるとはかぎらないので難しい
評価関数とヒューリスティックのさじ加減の問題になる…