凸包

点集合の凸包

この計算機について

凸包の計算機は、Andrewのモノトーンチェーンアルゴリズムを使って、2Dの点集合を囲む最小の凸多角形を求めます。凸包の角の頂点を反時計回りに列挙し、凸包上にある点と内部にある点の数を数え、正確な面積と周囲長を報告し、結果を輪郭で示す散布図を描きます。重複する点や同一直線上の点も正しく処理します。

凸包の求め方

  1. 点をカンマで区切った x,y のペアで入力します — 順序は問いません。
  2. 計算機が重複を統合し、点を左から右へソートします。
  3. ソートした点を掃引して下側と上側の境界を構築し、輪郭が左に曲がる角の頂点だけを残します。
  4. 凸包の頂点、面積、周囲長を読み取り、点の上に描かれた輪郭を確認します。

一般的な例

  • 正方形の角 0,0 6,0 6,4 0,4 と内部の点 3,2 と 2,1 → 凸包の頂点4個、面積 24、周囲長 20
  • 三角形 0,0 4,0 0,3 → 凸包の頂点3個、面積 6、周囲長 12
  • 同一直線上の点 0,0 1,1 2,2 3,3 → 退化した凸包 (線分)、面積 0
  • 正方形 0,0 4,0 4,4 0,4 に頂点 2,5 を追加 → 頂点が上辺を伸ばして凸包の頂点は5個

よくある質問

凸包とは何ですか?

点集合の凸包とは、それらすべてを含む最小の凸多角形のことです。最も外側の点の周りに輪ゴムをかけてピンと縮めるようなものです。

どの点が凸包の頂点になりますか?

最も外側の角の点だけが凸包上にあります。図形の厳密に内部にある点や、凸包の辺のちょうど上にある点は、頂点として列挙されません。

重複する点や同一直線上の点はどう扱われますか?

同一の点はまず統合されます。すべての点が1本の直線上にある場合、凸包は面積ゼロの線分に退化し、計算機はこれを退化した凸包として報告します。

点はいくつ必要ですか?

正の面積をもつ凸包を作るには、異なり、かつ同一直線上にない3点以上が必要です。