convex hull

convex hullは、計算幾何学やデータ解析において非常に重要な概念です。直感的には、平面上に散らばった釘の集合を、一本の大きなゴムバンドでぐるりと囲ったときにできる形状を想像すると分かりやすいでしょう。このゴムバンドが形作る最小の凸多角形が、その点集合の凸包となります。

数学的特性と応用

この概念の最大の特徴は、集合内のあらゆる2点を結ぶ線分が、必ずその集合の内部に含まれるという点にあります。実用的な場面では、以下のような用途で頻繁に利用されます。

物体の衝突判定：複雑な形状の物体を単純な凸包で近似することで、計算負荷を下げて衝突検知を行います。

クラスタリング：データ点群の広がりや境界を特定し、データの分布範囲を視覚化します。

パスプランニング：ロボットなどが障害物を避けて移動する際、障害物の周囲に凸包を設定して安全な経路を計算します。

類似概念との違い

bounding box（境界ボックス）との違いに注意してください。bounding boxは通常、軸に平行な最小の長方形で囲むため、計算は非常に高速ですが、物体の形状を大まかにしか捉えられません。一方でconvex hullは、点集合にぴったりと沿った最小の凸形状を求めるため、より精密に物体の境界を表現できます。ただし、その分計算コストはbounding boxよりも高くなります。