Cubic UFO

Google Code Jam 2018 の予選、D問題の考察です。あくまで個人的な解法の紹介ですので、正確を期すためには、主催者の解説ページを参照してください。

問題

X Y Z の3軸からなる3次元空間の原点に、辺の長さが1の立方体があります。この立方体を自由に回転させて、y = -3 に位置する XZ 平面上に落とす影の面積がちょうど A になるようにしてください。なお、光源は Y 軸方向の無限遠方にあるものとします。

考察

出ました、3D 問題です。3D 問題と見せかけて本質的にはそうでない問題も結構あったりしますが、今回に関しては 3D の基礎知識がないと手も足も出ない問題でした。

結論

まず結論から述べると、1~$\sqrt{2}$ の面積は Z 軸を中心に0~45度回転させることで作れます。$\sqrt{2}$~$\sqrt{3}$ の面積は Z 軸を中心に45度回転させたのち、そこからさらに X 軸を中心に0~35.2度回転させることで作れます(ちなみにこの35.2度は、$\arcsin \frac{1}{\sqrt{3}}$ から来ています)。

それぞれの区間において、面積は回転角に対して単調増加の関係にありますから、0~45度、0~35.2度といった区間さえわかれば、目指す面積に対して選ぶべき回転角は二分探索法で求めることができます。

影の面積

立方体は常に光源に対して3つの面を向けています。実際は1つや2つの場合もありますが、このときも面積0の面を向けていると捉えれば、常に3つの面を向けていると考えて差し支えありません。求めたいのは、この3面の XZ 平面への投影面積です。

ところで XZ 平面に投影される図形を考えることは、xyz 座標から y を取り除いた xz 座標を2次元座標とみなして考えるのと同じことです。つまり、ある1面が XZ 平面に落とす影とは、4点の xyz 座標から y を取り除いた、4点の xz 座標がなす四角形のことです。

光源に向けている3面がどれなのかは角度によって異なりますが、面積を求めるという目的に照らすと厳密に考える必要はなく、平行する2面を含まない3面であればどれを選んでも構いません。たとえば上の図で見えている3面を選んでおき、それを回転中にずっと追跡しておくことで面積を知る手掛かりになります。なぜかというと、選んだ面の一部が裏に回ったとしても、代わりに選んでいない面が表に現れ、結局同じ面積を作るからです。

四角形の面積

まず四角形を構成する4点を x 座標の昇順にソートします。同一の x 座標が含まれていても構いません。これらの点をそれぞれ p1 p2 p3 p4 とすると、四角形の面積は、三角形 p1-p2-p3 の面積と 三角形 p2-p3-p4 の面積の和と考えることができます。三角形の面積はググれば出てくるので割愛します。

回転

軸を中心とした回転にはアフィン変換を使います。たとえばある点を、X 軸を中心に Θ[rad] 回転させる操作は次のように表現できます。
$$\begin{bmatrix} x’ & y’ & z’ \end{bmatrix} = \begin{bmatrix} x & y & z \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & \cos \theta & \sin \theta \\ 0 & -\sin \theta & \cos \theta \end{bmatrix}$$
Z軸中心のアフィン変換も存在しますが、これもどこにでもあるので省略します。というか、私もこのあたりはググりながら必死に実装しました。

今回の問題では、特定の3点の回転後の座標を答えなければならないので、影の計算だけでなく、この3点についても同じくアフィン変換で追跡する必要があります。

注意

冒頭で述べた結論は、私が回転処理と面積計算を実装した後、プログラム上で立方体をこねくり回して実験的に得たものです。このことを解析的に述べることは私の技量では到底できないので、Google の公式解答を見てください。

ソフトウェアの設計・実装がうまく行かなくてお困りではありませんか? 組込屋にお任せください。リモート案件は、常駐の半額でお受けしています。

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)