Loading article…
幾何学において、N次元の点集合Sの最小境界ボックスまたは最小境界ボックス(最小外接ボックスまたは最小外接ボックスとも呼ばれる) は、すべての点が含まれる最小の測定値(面積、体積、または高次元の超体積) を持つボックスです。他の種類の測定値が使用される場合、最小ボックスは通常、それに応じて呼び出されます (例: 「最小周囲境界ボックス」)。
点集合の最小境界ボックスは、その凸包の最小境界ボックスと同じであり、この事実は計算を高速化するために経験的に使用される可能性がある。 [1]
2次元の場合、これは最小外接矩形と呼ばれます。
軸に沿った最小境界ボックス
与えられた点集合の軸に沿った最小境界ボックス（またはAABB）は、ボックスの辺が（直交）座標軸に平行であるという制約を受ける最小境界ボックスです。これは、S内の点の対応する座標の最小値と最大値によって定義されるN個の区間の直交積です。
軸に沿った最小境界ボックスは、問題のオブジェクトのおおよその位置として、またその形状の非常に単純な記述子として使用されます。たとえば、計算幾何学とその応用において、オブジェクトの集合内で交差を見つける必要がある場合、最初にチェックするのはそれらの MBB 間の交差です。これは通常、実際の交差のチェックよりもはるかにコストのかからない操作であるため (座標の比較のみが必要なため)、離れたペアのチェックをすばやく除外できます。
任意の方向の最小境界ボックス
任意方向の最小境界ボックスは、結果の方向に関する制約なしに計算される最小境界ボックスです。回転キャリパー法に基づく最小境界ボックス アルゴリズムを使用すると、2 次元凸多角形の最小面積または最小周囲の境界ボックスを線形時間で見つけることができ、3 次元点集合の最小面積または最小周囲の境界ボックスを凸包の構築とそれに続く線形時間の計算にかかる時間で見つけることができます。[1] 3 次元回転キャリパー アルゴリズムは、3 次元点集合の最小体積の任意方向境界ボックスを 3 次時間で見つけることができます。[2]後者の Matlab 実装と、精度と CPU 時間の間の最適な妥協点が利用可能です。[3]
オブジェクト指向の最小境界ボックス
オブジェクトが独自のローカル座標系を持っている場合、これらの軸を基準とした境界ボックスを保存すると便利です。これにより、オブジェクト自体の変換が変化しても変換する必要がなくなります。
デジタル画像処理
デジタル画像処理において、境界ボックスとは、ページ、キャンバス、画面、またはその他の同様の二次元背景上にデジタル画像を配置したときに、その画像を完全に囲む長方形の境界の座標にすぎません。
参照
参考文献
- ^ ab Toussaint, GT (1983). 「回転キャリパーによる幾何学的問題の解決」(PDF)。 Proc. MELECON '83、アテネ。
- ^ Joseph O'Rourke (1985)、「最小囲みボックスの検索」、Parallel Programming、Springer Netherlands
- ^ Chang, Chia-Tche; Gorissen, Bastien; Melchior, Samuel (2018). 「いくつかの最小体積バウンディングボックスアルゴリズムの Matlab 実装」. GitHub .。