2008-03-01から1日間の記事一覧

凸包を求める

前回のようなランダムな点があったとき、その点を全部含んでへこみのない多角形を作成するという問題。 アルゴリズムとしては、「他の点でできる三角形に含まれてたら凸包上の点じゃない」という考え方で、全部の組み合わせの三角形について全部の点を走査し…