1. 三次元空間上で「良い Bounding Box」を算出する手法について
久々に「純粋なブログ」というものを始めてみました。
最近は無為に時間を過ごすことも多く、仕事でもプログラムを書くことが中心なので、言語野が劣化してきた感覚があります。その対策や、日々何か成長していきたいという思いから「ただのブログ」を立ち上げました。
ジャンルや質は問わず、「その日一番考えたこと」を適当に書いていきます。よろしくお願いします。
さて、今日はこんな問題を考えていました。
三次元空間上に、たくさんの人がいます。この人たちを取り囲む「なるべく体積の小さな」直方体（＝Bounding Box）の姿勢を求めたい、という問題です。
事前情報は「各人の3次元座標」のみです。
3次元だと考えにくいので2次元平面上で考えてみます。黒点が人だと思ってください。
このような状態で、「すべての黒点を囲む」かつ「なるべく面積が小さい」長方形を求めたいです。
単純な解はAABBです。xy軸それぞれについて最大値・最小値を調べれば求められます。
しかし、この問題では「なるべく面積が小さい」を満たせていないように思えます。実際、人の目で点の分布を見れば以下のような長方形が最適であることはすぐ分かります。
これをどうやって計算するか？という問題です。
結論から言うと、私は主成分分析を利用しました。
主成分分析は統計や機械学習の文脈で使われることが多いですが、今回のような問題にも応用できます。
数学的な解説は、こちらが比較的分かりやすいと思います。
余談ですが、主成分分析は「次元を圧縮する手法」と端的に説明する記事をよく見かけます。ただ、これは応用先の一つに過ぎず、本質が見えにくくなって悪い説明のように思います。
主成分分析の本質は、「データの分散が大きくなるように新しい軸を見つける」点にあります。
今回の問題でいうと、以下のような軸を見つけられます。
軸さえ分かれば、あとはAABBで行った処理と同じものを適用すれば良いです。
ちなみにC#で実装していたのですが、最近だと ML.NET という機械学習フレームワークがあるみたいで、割と簡単に組み込めました。.NET も色々充実してきて、良い時代ですね。ただ、ML.NET はネット上にサンプルが（英語含めて）あまり見当たらず、手探りで使い方を学んでいく必要がありました。とは言え、今回のように用途がはっきりしている場合は、半日もあれば普通に組み込めました。
