ax + by + cz + d の符号を求める計算

質問

式 ax + bx + cz + d = 0 (d>0) であらわされる平面があります。任意の点P(x,y,z)が与えられたとき、点Pと原点O(0,0,0)をつなぐ線分OPがこの平面と交わるかどうかを判断するプログラムを書いています。

a,b,c,dは８ビットの符号つきの整数です。つまり、-129 < a,b,c < 128、　0 < d < 128 です。
点ｐの座標x,y,z は32ビットの符号付整数です。
単純にax + bx + cz + dを計算すると、途中の計算は最大32+8+2=42ビットの値になるのはわかりますが、答えは１ビット（交わるか交わらないか）なので、32ビットの範囲内での計算で済ますことを考えてみました。そのようなアルゴリズムってありますか？

回答No.3

R_Earl

この一週間考えてみたのですが、あまり良い案が思いつきませんでした。

> 一応私なりに、32ビットの(x,y,z)を上位16ビット、下位16ビットの2つの数(x1,y1,z1) と(x2,y2,z2)に分けて、

32ビットの範囲に押さえるには、やはり分割しかないのかもしれないです。

あるいは、擬似的にもっとビット数の多い変数を作るという方法もありますが、
計算規則も自分で定義する必要があるので、大変になってしまいます。

お礼

回答ありがとうございます。
やっぱり、巧妙な裏技、なさそうですね。
何度も、お付き合い下さり、ありがとうございました。

回答No.2

R_Earl

ANo.1です。
よくよく質問タイトルを見たら『ax + by + cz + d の符号を求める計算』でしたね。
ax + by + cz + dの符号で判定できることは既知なのですね。申し訳ありません。

42ビットの方も理解しました。

> なので、32ビットの範囲内での計算で済ますことを考えてみました。そのようなアルゴリズムってありますか？

32ビット以内の浮動小数点数を使ってもいいなら、
x,y,zのうちの最大値で、ax + by + cz + dを割るという方法も考えられます。
ax + by + cz + dの計算前にx,y,z,dを割ってしまえば、
axやbyやczの計算で40ビットになるということもなくなります。
ただ、誤差が出てしまうので正確には判定できなくなってしまいますね。

ax + by + cz + d以外の方法は私には思いつきません。
お役に立てず、すみません。

お礼

回答ありがとうございます。
＞お役に立てず、すみません。
気になさらないでください。回答感謝してます。

一応私なりに、32ビットの(x,y,z)を上位16ビット、下位16ビットの2つの数(x1,y1,z1) と(x2,y2,z2)に分けて、
d1 = ax1 + by1 + cz1 を計算し、d1 が1以上なら交わらない、-1以下なら交わる、-1と１の間なら今度は
d2 = ax2 + by2 + cz2 + d + d1＊2^16 を計算して、d2の正負で判断する
というアルゴリズムは思いついたのですが、もっと他の賢い方法がないのか、引き続き回答お待ちしています。

回答No.1

R_Earl

点Pの座標を(p,q,r)とします。
D(x,y,z) = ax + bx + cz + dという関数Dを作り、
D(0,0,0)とD(p,q,r)を計算します。

D(0,0,0)とD(p,q,r)が異符号か、片方が0であれば
線分OPは平面ax + bx + cz + d = 0と交わります。

D(x,y,z)は、点(x,y,z)が平面ax + bx + cz + d = 0で分けられた領域の
上(下)にあるのか下(上)にあるのかを判断する関数です。
D(x,y,z) < 0なら、点(x,y,z)は平面の上側（又は下側に）、
D(x,y,z) > 0なら、点(x,y,z)は平面の下側（又は上側に）に存在します。
（D(x,y,z) = 0なら、点(x,y,z)は平面内に存在します。）

元となる考え方は、高校数学の領域の分野です。
y > ax + bなら、y = ax + bより上の領域、
y < ax + bなら、y = ax + bより下の領域というのがありましたよね？
この二つの式の左辺を右辺に移項すると

0 > ax - y + b
0 < ax - y + b

となります。両方とも右辺はax - y + bです。
なのでこのax - y + bをD(x,y)という関数にしてしまえば、
D(x,y) < 0なら、点(x,y)は直線ax - y + b = 0より上の領域に、
D(x,y) > 0なら、点(x,y)は直線ax - y + b = 0より下の領域にあるということになります。
今回はそれを三次元空間に応用しました。
ちなみにyの係数が-1で固定されていますが、別にyに自由な係数をつけても問題ないです。
ただ、そうするとD(x,y)の正負のみで、点(x,y)が直線よりも上なのか下なのかを判断できなくなります。
ただ、D(x,y)とD(u,v)が異符号であれば、
2点(x,y)と(u,v)が同じ領域にいないと判断することはできるはずです。
（同符号なら、同じ領域内に2点が存在することになります。）

> 単純にax + bx + cz + dを計算すると、途中の計算は最大32+8+2=42ビットの値になるのはわかりますが、

ここがちょっと分からなかったので、逆に質問させてもらいます。
どうやって計算して、42ビットという答えが出たのでしょうか？