凸包を求める - きしだのHatena前回のようなランダムな点があったとき、その点を全部含んでへこみのない多角形を作成するという問題。 アルゴリズムとしては、「他の点でできる三角形に含まれてたら凸包上の点じゃない」という考え方で、全部の組み合わせの三角形について全部の点を走査します。最適なアルゴリズムではないですが、とりあえず今回はこれで。 で、点Pが三角形ABCに含まれるかどうかは、三角形ABCが時計周りだとしたら、三角形ABP、BCP、CAPも時計回りだということを使います。 点Pが三角形ABCの外にある場合は、三角形ABP、BCP、CAPのどれかが三角形ABCと逆周りになります。 三角形の向きは符号付面積を使うのですが、三角形の座標をそれぞれ(x1, y1)(x2, y2)(x3, y3)とすると(x1 - x2)(y1-y3)-(x1-x3)(y1-y2)で得られます。 そうやって凸包上に乗らない点を削除したら、隣り合
