6:凸包を求める

凸包とは、 Google検索：凸包 板の上に幾つも釘を打ち、外周から輪ゴムをかけて、 ゴムと接している釘で構成される多角形。 グラハムスキャン まず、端にある点を基準として、それに対する角度の順に点を並び替える。 並び替えた順に点を見ていき、 一つ前の点H 現在の点I 次点J の角度∠HIJ が マイナスの場合、凹みであると判断して、点Ｉを削除する。 そして、その次の点Kとの ∠HJK を見る。 //凸包を得る static public Vec2D[] convex_hull(Vec2D[] points) { List<KeyValuePair<double, Vec2D>> dict = new List<KeyValuePair<double, Vec2D>>(); //Y最小値を見つける int max = 0; for (int i = 1; i < points.Leng

[masahirox374]

グラハムスキャン 凸包を求める