enchant.jsの当たり判定不足を補う その3
2014 年 11 月 13 日 by 山平引き続き、前回から持ち越した問題である「傾いた矩形の4点がもう一方の傾いた矩形の内側にあるか」を考えます。
enchant.jsでは、見た目上傾いている矩形も、内部的には傾いていない状態の座標で管理されています。
これを回転させて、見えている状態と内部状態をあわせます。
さて、傾いた矩形の中にもう一方の傾いた矩形の4点のいずれかが含まれているかを調べるにはどうすればいいのでしょうか。
全然思いつかないので「点が傾いた矩形の中にあるかどうか」で検索して見たところ、そのものズバリの質問（と答え）がありました。
外積を使えば求めることができる、とのことです。
高校生ぐらいの時に聞いたことがある気がします。
ナルホド…ナルホド…。
なんだか面倒臭いナアと思っていたその時、「回転軸を変えればいいんだ！」と閃きました。
どういうことか説明します。
先の図では2つの傾いた矩形を両方とも「画面の座標系」で正しく回転させようとしています。
こうすると、どちらの矩形も傾いているので、点が矩形に含まれるかどうかの判断のために「外積」を求める必要が出てきます。
そうではなく次のように回転させるとどうでしょうか？
ここで2つの傾いた矩形をそれぞれ「矩形A」「矩形B」とします。
- 「矩形A」を先ほどと同じように、「矩形A」の中心を軸にして「矩形A」の傾きぶん回転します。
- 今度は「矩形A」を「矩形B」の中心を軸にして「矩形B」の傾きぶん「逆回転」します。
お分かりでしょうか？
つまり軸を変えて「矩形A」を2回回転させることにより、「矩形B」を回転せずに2つの矩形の位置関係を（相対的に）保ったのです。
「矩形B」が回転していないということは、「矩形B」の座標は（絶対的に）傾いていないので、点が「矩形B」に含まれているかどうかの判定は「傾いていない矩形の中に点が含まれているかどうか」を見るだけで済むことになります。
この計算は、3Dグラフィックでは右手系・左手系などと呼ばれる一般的な考え方です。
少し考え方を変えればシンプルに実装できる、という良い例となりました。
タグ: HTML5, JavaScript, アルゴリズム, オープンソース
