いぬおさんのおもしろ数学実験室

おいしい紅茶でも飲みながら数学、物理、工学、プログラミング、そして読書を楽しみましょう

任意に与えられた点が凸多面体の内部にあるかどうか判定する

 与えられた点が空間内のこんな立体の内部にあるかどうか判定したいとします。立体は、与えられた頂点、8点で決まっています。

 シューティングゲームなどで、ゲームを展開する空間のスクリーンに見えない部分では、基本的に戦闘機などを飛ばす必要はありません。その空間が例えば下のような図で表されるわけです。この立体の外に出た戦闘機はプログラムで削除しなければなりません。PCのリソースは有限なのですから、見えない部分まで面倒見てられないよ、ということです。ここをいったん出てすぐ戻るようなケースは別ですが、とにかく戦闘機がこの立体内にあるかどうか、判定することは必要なのです。Unityならひょっとしてこういう形の立体を作って、当たり判定でいけるかも知れません。でもそんなこと、するまでもありません。高校数学で解決です!

f:id:Inuosann:20210303193615p:plain

 例えば立体内に原点が含まれているとしましょう。このとき、与えられた点が平面に関して原点と同じ側にあるかどうか判定できれば解決です。それを6枚の平面について繰り返せばよいからです。

 立体の上面を作る4点のうちの3点で平面の式は決まります。この上面の縁に沿うベクトルを図のようにおきます。また平面の通過点を (p, q, r) とし、外積×=(a, b, c)とします。

f:id:Inuosann:20210303194242p:plain

このとき、平面の式は

a(x - p) + b(y - q) + c(z - r) = 0

と書けるのでした。(a, b, c)は法線ベクトルになります。ここで a(x - p) + b(y - q) + c(z - r) = f(x, y, z) とおくと、この f(x, y, z) の符号は平面の片側では一定です。平面上では0、反対側ではさっきと符号が変わります。

 この辺は2次元のときと事情は同じです。3x-y+1 = 0 は直線を表します。このとき左辺を f(x, y) とおくと、f(x, y) の符号は直線の上側では一定、下側ではそれと違う符号で一定になるのでした。もちろん直線上では f(x, y) = 0 です。

 空間の話に戻りましょう。f(x, y, z) の符号が原点を代入したときと与えられた点を代入したときとで一致していれば、この2点は平面に関して同じ側にあります。これで解決です。このやり方ならプログラミングもしやすいでしょう。

 

 高校生のとき、矢野健太郎先生の『解法の手引き』(科学振興社)に、平面で、上の f(x, y) の符号は直線の片側では一定であることの説明が載っていました。直線より上側に点があるとしましょう。f(x, y) の符号は正か負です。直線上ではないからです。ここからジワジワと点を動かしてみます。ただし直線に触れてはいけません。このとき符号は変わりません。なぜでしょうか。もしも符号が変わったのなら、途中で f(x, y)  = 0 になる瞬間があります。それは点が直線上に乗ったときで、直線に触れずに動かしているならそういうことはないはずだからです。……とまあ、こんな説明でした。面白い話だ……と高校生だったぼくは思いました。厳密にはツッコミどころはありますが、高校生ならいいでしょう。ちなみに……教科書にはこういう説明は載っていません。授業では「こんな説明もあるよ」といきたいところです。