NO_WAIT

主にプログラミング

Book Stacking ProblemのJavaScriptによるシミュレーション(Box2DWeb,D3)

Book Stacking Problemという数学の問題があることを知り、 調べたついでにJavaScriptで可視化してみました。 本をどこまで遠くまで積むことができるか、簡単に言えばそういう問題のようです。

Box2DWebを用いた物理シミュレーション

物理シミュレーションエンジンBox2DのJavaScript移植版、Box2dWebを使用したシミュレーションです。 左側には本を別々に落とした場合、 右側には本をすべてくっつけて落とした場合の運動が表示されます。

D3.jsによる可視化

データ可視化に便利なJavaScriptライブラリD3を使用したプログラムです。 テーブル(青い矩形)と本(赤い矩形)が置いてあります。枠内をクリックすると本を積んでいきます。 積まれた本の形状と位置を示すのみが目的ですので、当然物理シミュレーションはしていません。

問題の概要

テーブルの上に本を何冊も積み上げることを考えます。本はすべて形状も大きさも重さも同じであり、密度が一様であるとします。 このとき、バランスを崩してテーブルから落下する本があってはなりません。 Book Stacking Problemは最大でどれだけテーブルの端から水平方向に離れた位置に、本を落下させずに置くことができるかという問題です。

積み上げた本の束が落下しないためには、それらの重心がテーブルの上にあることが必要です。 テーブルの端から本の端までの距離が最大となるのは、本たちの重心がちょうどテーブルの端に重なっているときであると考えられます。

今、本の長さを1単位長さとします。

f:id:shinaisan:20140112161553p:plain

図のように1冊の本を置くとき、突出部分の最大長さ \(d_1\) は明らかに

\[ d_1 = \frac{1}{2} \]

です。

2冊の本を置くとき、上の本の重心は下の本の端を超えることはできないので、両者を重ねます。 2冊の本の重心は2冊が重なった部分の中点ですので、これを図のようにテーブルの端に合わせます。

f:id:shinaisan:20140112161611p:plain

本の端までの距離 \(d_2\) は

\[ d_2 = \frac{1}{2} + \frac{1}{4} = \frac{3}{4} \]

となります。

3冊積む場合は、上記のように積んだ2冊の重心を、もう1冊の端に重ねます。

f:id:shinaisan:20140112161617p:plain

最下段の本の右端が上2冊の重心の位置となります。 最下段の本の重心は、上2冊の重心から\(\frac{1}{2}\)だけ離れています。 よって最下段の本の右端から見た場合、3冊の重心はそこから \(\left(1\times\frac{1}{2} + 2\times 0\right)\times\frac{1}{3} = \frac{1}{6} \) だけ離れた位置にあることになります。 よってテーブルから

\[ d_3 = d_2 + \frac{1}{6} = \frac{3}{4} + \frac{1}{6} = \frac{11}{12} \]

だけ離れた位置に本の端が来ます。

繰り返すと、 \(n\) 冊積む場合は、 \(n-1\) 冊の重心を下の本の端に重ねることになります。 最下段の本の右端から\(n\)冊の重心までの距離は \(\left(1\times\frac{1}{2} + {(n - 1)}\times 0\right)\times\frac{1}{n} = \frac{1}{2n} \) となるので、

\[ d_n = d_{n - 1} + \frac{1}{2n} \]

となりますが、この式は調和級数の第\(n\)部分和\(H_n\)を用いて

\[ d_n = \frac{1}{2}\sum_{i=1}^n{\frac{1}{k}} = \frac{1}{2}H_n \]

と書くことができます。

Box2dWebによるシミュレーション結果

Box2dWebによるシミュレーションでは画面の左右において、2通りの方法で本を積んでいます。 右側はすべての本をくっつけてしまい、下にある(薄緑色の)床(テーブル)に落としています。 複数の本が1体になっており、本相互の反発がありません。 この例では、本は床の上で安定し、落下することはありません。 ただし、床の座標を1pixelでも本の反対側へずらせば、ゆっくりと落下を始めます。

対して、左側では本を少しずつ離して、1冊1冊床に落としていきます。 落下の衝撃のせいなのかは不明ですが、残念ながら崩れてしまいます。 ゆっくり本を置けばいいのでしょうか?

残念ながら落下(左)、安定(右)

f:id:shinaisan:20140904211420p:plain

床をすこしずらせば落下(右)

f:id:shinaisan:20140904211424p:plain

プログラム(Box2dWeb)について

Webで最も簡単そうなBox2dWebのサンプルを探してきて改変することで作成しました。 そのため凝ったことは何もやっていません。 物体はb2BodyDefに定義し、b2World内に作成(CreateBody)します。 各b2Bodyの形状(ここではb2PolygonShapeのみ)やら 物理的特性(摩擦係数 friction、反発係数 restitution)はb2FixtureDefとして定義し、 b2Bodyに関連づけ(CreateFixture)します。 この際、Bodyに複数のFixtureを登録すれば、複数の基本的形状を組み合わせた単一の物体を表せるようです。

所感

初めて見たときは「どこの誰がどんな動機でこんな問題を考えたのか?」という感想しかありませんでした。 おそらく知っていても何の役にも立ちませんが、本を積み上げるという平凡な日常動作(?)に対する考察のうちに、 調和級数(の部分和)が顔を見せるというのが素人目に面白く映りました。 調和級数は発散するので理論上は本をいくらでもテーブルから遠くまで積むことができるはずです。

Webを検索してみると、調和級数の部分和による解は最適解ではない、本をもっと離れた位置に置くことができるという 主張をしている人を見つけることもできます。 よく読んでいないので真相は不明です。皆さんよく研究されますね…

可視化プログラムについては、D3.jsのビジュアル要素(ここではSVG)に対するデータバインディング方法がなかなか巧妙に思えました。 慣れるまでに時間がかかりましたが。

Block Stacking Problemと呼ばれることもあるようです。

TODO

ほかの物理シミュレーションエンジンでもっと簡単にこの手のシミュレーションができないか調べてみたいです。時間があれば…

参考