🎄teratailクリスマスプレゼントキャンペーン2024🎄』開催中!

\teratail特別グッズやAmazonギフトカード最大2,000円分が当たる!/

詳細はこちら
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

4回答

4107閲覧

直交するベクトルを求める方法の良し悪し

fana

総合スコア11985

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

1グッド

0クリップ

投稿2021/03/05 12:14

編集2021/03/09 06:51

ある3次元ベクトルVが与えられたとき,それに直交する3次元ベクトルを求めるための関数を作る.

関数の仕様:

  • Vが零ベクトルでない場合,解も零ベクトルでないものとする
  • 解は無限に存在しますが,そのうちのいずれか1つを結果とする

……という話に対して,解を求める方法として後述する2つ{(A)と(B)}の話を考えました.

…のですが,(A)と(B)の2つは考えの出発点がちょっと違っていただけで,結局,(B)は(A)の縮小版みたいな話でした.
実際,後述の2つのコードを見比べれば,(B)は(A)の処理を簡略化した形の内容になっています.

質問の内容は,「実用上(?),(B)で問題ないのだろうか?」ということです.

計算量の観点では(B)の方がちょっとだけ良いだろうと思いますが,
「(B)は,(A)が返し得る3種類の解のうちの1つ((A)のコード内の末尾の解)を返さない」という点が気になっています.

「(B)では足りてなくて,(A)でなくてはならない」とか,
「(B)の方が(A)よりも(何らかの意味で)良くない」といったことがあるものでしょうか?

(A)

Vの要素のうち最も絶対値が小さい要素を捨てて(=0にして),あとは残りの2次元の平面上で90度回転すれば解が得られる.
…という考えを愚直に実装したのが↓のコードです.

C++

1//Vに直交するベクトルを計算して,結果をPVに入れる. 2//(A)Version 3void Perpendicular_A( const double (&V)[3], double (&PV)[3] ) 4{ 5 const double ABS[]{ fabs(V[0]), fabs(V[1]), fabs(V[2]) }; 6 7 if( ABS[0] < ABS[1] ) 8 { 9 if( ABS[0] < ABS[2] ) 10 { 11 PV[0] = 0; 12 PV[1] = -V[2]; 13 PV[2] = V[1]; 14 return; 15 } 16 } 17 else if( ABS[1] < ABS[2] ) 18 { 19 PV[0] = V[2]; 20 PV[1] = 0; 21 PV[2] = -V[0]; 22 return; 23 } 24 25 //※この解は,後述の方法(B)の実装には現れない 26 PV[0] = -V[1]; 27 PV[1] = V[0]; 28 PV[2] = 0; 29}

(B)

何か適当なベクトルaを持ってきたとき,aV と平行でなければ,aV の外積が解である.

適当に決めたベクトルaと,それに直交するベクトルbの2つを用意しておいて,

  • aV の外積
  • bV の外積

のうち,ノルムが大きい側を解とすれば,Vに平行な(あるいは非常に平行に近い)ベクトルを用いてしまうことへ対策できる.

この話を
a = { 1,0,0 }
b = { 0,1,0 }
として実装したのが↓のコードです.

C++

1//Vに直交するベクトルを計算して,結果をPVに入れる. 2//(B)Version 3void Perpendicular_B( const double (&V)[3], double (&PV)[3] ) 4{ 5 //CrossProd( {1,0,0}, V ) = { 0, -V[2], V[1] } 6 //CrossProd( {0,1,0}, V ) = { V[2], 0, -V[0] } 7 //ノルムが大きい側を採用するとしたら,V[0]とV[1]の絶対値を見て判定すればよい 8 9 const double ABS[]{ fabs(V[0]), fabs(V[1]) /*, fabs(V[2])*/ }; 10 11 //※解の種類が2種類だけだが,これで「十分」であろうか? 12 if( ABS[0] < ABS[1] ) 13 { 14 PV[0] = 0; 15 PV[1] = -V[2]; 16 PV[2] = V[1]; 17 } 18 else 19 { 20 PV[0] = V[2]; 21 PV[1] = 0; 22 PV[2] = -V[0]; 23 } 24}

※補足:

(B)は(A)の縮小版みたいな話でした

という言い方は少し違うかもしれない.

(B)の話において,ab に単位ベクトルを選ぶことで,abも同様)と V との外積というのは,
Va 方向成分を除去したものを, a を回転軸として90度回したもの」という話になる.
で, その単位ベクトルとして,a = {1,0,0} としたことによって,(A)の話と全く同じことになっている.
…という感じか.


[追記]

いくつかの回答やコメントにおいて,「非0」という概念が述べられていますが,
この質問内に示した実装では,「値が0かどうか」を直接的に判定するのではなく,(要素のABSを比較することによって)「より0から遠いものを用いる」という方法を採っています.

「値が0かどうか」という判定を用いた場合,その判定で0でないとされた「0にとても近い値」だけで結果が構成されるかもしれず,
そのような結果は{精度が?,利用のし易さが?}良くないものになる可能性があるのではないだろうか? と考えています.(←この考え自体が間違い?)

K_3578👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

maisumakun

2021/03/08 02:22

> 解は無限に存在しますが,そのうちのいずれか1つを結果とする その解をどのような目的に使いたいのでしょうか?それによって、「より良い解」の基準が決まってくると考えます。
fana

2021/03/08 03:44

用途は不明…というか,特別な用途を想定しているものではなく, 「単位ベクトルを求める」等のような,一般的操作として提供される関数 と考えています. 用途に応じた良さを考えることができる場合,「このような目的に使う場合においては…」といったお話をいただければ,と思います.
fana

2021/03/08 07:40 編集

あえて用途を考えるとすれば… 何かベクトルが1つ(動的に)定まったときに「その方向を基底ベクトルの1つとする直交基底の上で物事を考えたい」といった場合に使うかもしれません. (残りの2方向に関して,どっちに向いているのかはどうでもいい場合.)
guest

回答4

0

「解は無限に存在しますが,そのうちのいずれか1つを結果とする」としている以上、特定の結果が出ようが出まいがどうでもいいように思います。
結果に何かしらの評価基準をつけると言うなら話は変わりますが、もしそうならそもそもこの要件自体に問題ありです。
そもそも、要素の絶対値を比較する意味はあるのでしょうか?結果の要素で、確定の0としているもの以外の2つの要素がどちらも0になることさえ避ければ、絶対値の評価なんて不要です。

投稿2021/03/05 13:22

swordone

総合スコア20669

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2021/03/06 03:50 編集

> そもそも、要素の絶対値を比較する意味はあるのでしょうか? 要は,「Vの要素のうち最も絶対値の小さい要素を選ぶ」ことによって, > 2つの要素がどちらも0になること を避けようとしているのですが,より良い選択方法はありますでしょうか? ーーー > 特定の結果が出ようが出まいがどうでもいいように思います。 例えば,入力のVが何らかの演算の結果得られたベクトルであるような場合, 意味的に0であって欲しい要素が ==0 では判定できない極めて微小な値になっているような場面はあるのではないかと思います. V = { εくらいの値(≒0), 5000, 0 } とかいう場合に, 「非0の要素を残す」を達成するための方法次第では, { 0,0, εくらいの値} みたいな結果にもなり得ます. その場合,それはどうなんだろう? と. 確かに,「いずれか1つを結果とする」という話の上では,これも「有り」となってしまいますが, {0,0,5000くらい} という結果が得られる別の方法があるならば,きっとそちらの方が「何らかの意味で」良い のではないか,と.漠然としていますが.
fana

2021/03/06 03:43

うまく言えませんが,(A)も(B)も要件を満たす実装の1つの形なのだとして, 実用上の何らかの良し悪し(←ここが不明瞭なのですが)を考える場合の > 評価基準 のようなもの に照らし合わせたら,どうなのか? という. e.g. 要素の絶対値比較をしない方法の実装 があるならば,「軽量さの観点」でその分だけより優れている,と言えると思います.
fana

2021/03/08 07:27

現実装にfabsや条件分岐があることには,私自身,いまいち感のようなものを感じており… 絶対値比較が不要という話に大変興味があるのですが,ご教授いただくことは叶わぬ夢でしょうか?
swordone

2021/03/08 09:52

> 意味的に0であって欲しい要素が ==0 では判定できない極めて微小な値になっているような場面はあるのではないかと思います. このような要件は重要です。質問に追記しておいたほうが良いでしょう。 私の主張は、単に「0か0でないか」を判断すれば良い、というものだったため、ご提示のような「0じゃないけど0」という数がある場合は通じません。
maisumakun

2021/03/09 07:03

> { 0,0, εくらいの値} みたいな結果にもなり得ます.(中略){0,0,5000くらい} という結果が得られる別の方法があるならば 方向が同じなので本質的に変わらないように見えるのですが…
fana

2021/03/09 07:22

> 方向が同じなので 例が良くないのか,私の頭が良くないのか,どちらかあるいは両方です. (演算の誤差に起因するかもしれない程度の)2つの非常に小さな値s1,s2 と,小さくない値L を要素とするベクトル V={s1, s2, L } とかで示すべきだったように思います. 主たる成分であるLを捨ててしまい,残りの微小値s1,s2から構成された {-s1,s2,0 } のようなかなり零ベクトルに近い結果と, Lを残す選択による { 0,L,-s2 } のような結果とを比較した際に,どうなのだろう? という.
guest

0

解のうち一つだけでいいなら簡単です。

入力ベクトルを(x, y, z)とすれば、以下の6つのベクトルはこれに直交します。

(y, -x, 0)
(-y, x, 0)
(z, 0, -x)
(-z, 0, x)
(0, z, -y)
(0, -z, y)

あとは題意を満たさない場合(0ベクトルになる場合又は外積0の場合)を条件分岐で取り除けばOKです。6つ全てが除外されるとは考えられません。

※ちなみに、6つのうち、半分は残りの逆向きベクトルなので、3つと考えても同じです。

以下追記(コメント後の追記)

はい。パターンBで問題ないと思います。簡単のため、絶対値最小のものをxと仮定します。このとき、入力(x, y, z)に対し、出力は(0, -z, y)となります。

  1. 例外パターン1(ゼロベクトルの可能性)

 出力がゼロベクトルになるときはz, yがともにゼロです。このとき仮定からxもゼロとなり、入力もゼロベクトルとなります。したがって、題意に矛盾しません。

  1. 例外パターン2(外積0の可能性、入出力が平行又は直線上に出現する可能性)

 入出力ベクトルの外積を計算すると(yy + zz, -xy, -xz)となります。外積ゼロは、この各要素がゼロであることを意味しますが、第一要素が平方和なので、y, zがともにゼロを意味します。やはり、仮定からxもゼロとなり入力もゼロベクトルになります。結局、題意に矛盾しません。

なお、プログラム上の記述から実数を想定しましたが、複素数が関与する場合は例外パターン2に引っかかる可能性が残ります。

投稿2021/03/09 05:56

編集2021/03/09 08:13
HogeAnimalLover

総合スコア4830

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2021/03/09 06:13 編集

> 3つと考えても同じです その3つを考えているのが,質問内で言うところの(A)の側の話であり, 3つのうちの2つしか考えていないのが,(B)の側の話です. それら 3つ or 2つ の候補のうち,「最も零ベクトルから遠いもの」を選択しています.
guest

0

ベストアンサー

(B)で十分安定しています。

(B)は
(x, y, z)に対して
|x| < |y| ? (0, -z, y) : (z, 0 -x)
となります。

求めたベクトルの長さが0ないし非常に小さくなる可能性があれば、解法として不安定となりますが、
|x| < |y| である場合、(0, -z, y)の長さは|x|, |y|, |z|それぞれより長くなります。
そうでない場合でも、(z, 0, -x)の長さは|x|, |y|, |z|それぞれより長くなります。

どの場合でも求まるベクトルの長さは元のベクトルの各成分の絶対値以上ではあるので
(B)で十分かと思います。

質問の答にはなってませんが、

V = (x, y, z)に対して W = (y-z, z-x, x-y)とすれば

内積 dot(V, W) = xy - zx + yz - xy + zx - yz = 0

投稿2021/03/08 01:17

編集2021/03/08 02:46
ozwk

総合スコア13551

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2021/03/08 01:23

あ、でもこれだと(1,1,1)に平行なやつアウトだ
ozwk

2021/03/08 01:25

あっ...
fana

2021/03/08 01:40 編集

V=(1,1,1) のときに,結果が零ベクトルになってしまいそうです. (こんな感じの「条件分岐が無い方法」が存在するならばそれが最も好ましいように思います)
ozwk

2021/03/08 01:48

まあこんな単純な方法があったらグラムシュミット法なんてめんどくさい計算しませんよね
fana

2021/03/08 03:55

絶対値が最小の要素を探し出すことまでしなくとも, 絶対値が最大の要素が(結果のどこかの成分として)残る保証があるならば十分であろう, …といった感じでしょうか.
ozwk

2021/03/08 03:59

そうなりますね。
HogeAnimalLover

2021/03/09 08:36

?入力が(1,1,1)ならば出力は(1,0,-1)では?
fana

2021/03/09 10:03

2021/03/08 10:48 以前の(1,1,1)に関するコメントのことであれば,これは現在では解答欄末尾にて打消し線がなされている > W = (y-z, z-x, x-y) に関する話になっています. (それより後のコメントは現回答に関しての話になっています.)
fana

2021/03/09 13:54

私が漠然と捉えていた事柄を,結果に保証されるノルムという形で明確に示していただいたという点で,この回答をBAに選択しました. 現回答をいただいてから1日以上考えましたが, (B)による保証では不足(で(A)側ならばそこがOKになる)というような明確な例はなさそうに思えました.
guest

0

回答ではありませんが、全部を知りたければ、数式で考えた方が速いです。

aの成分が(p, q, r)として、wの成分が(x, y, z)とすると
直交するのは a と w の内積がゼロ、つまり
px +qy + rz = 0 が成立するときです。
この式は平面を表していて、r がゼロでないなら
z = -(p
x +qy)/r
と書くことが出来ます。
結局、(x, y, -(p
x +qy)/r)がaと直交するベクトルの全てです。
rがゼロの時は、(x, -(p
x +rz)/q, z)か(-(qy +r*z)/p, y, z)を使います。

投稿2021/03/08 00:35

ppaul

総合スコア24670

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2021/03/08 02:10 編集

申し訳ありません.趣旨を捉えられません. 「r がゼロでないなら」というのは,どのように判定するのでしょう? 結局,話の内容としては,3種類の式から解をどうにかして選択する必要があるのだと思いますが, 具体的にどのようにして選択することになりますでしょうか? --- |r|が他と比較して非常に小さい(0に近い)ような場合に, > -(p*x +q*y)/r のような計算処理をしても(精度的な面で?)問題を生じないものでしょうか? 問題があるとしたら,きっと他の(より良い)解を選択するのだと思いますが,その選択基準は…? 的な.
ppaul

2021/03/09 03:28

aがゼロベクトルつまり(0, 0, 0)であれば、直交するベクトルを求めるという問題自体が無意味です。 aがゼロベクトルでないなら p, q, r のどれかはゼロではないので、ゼロでないものを使えばできるという意味です。 気になるなら、p, q, rの絶対値の一番大きいものを使えばよいでしょう。
fana

2021/03/09 04:57 編集

話を把握しました. これを実装するとしたら,例えば > (x, y, -(p*x +q*y)/r) を用いる場合,xとyとして「(x,y)≠(0,0) な何らかの値のペア」を用いることになると思いますが, その値はどのように選択なされますか? (その選択基準/理由 みたいなものが,私が引っかかっている事柄なのだろうと思います) 私の実装というのは,(x,y)の一方にrを, 他方に0を選択することに相当すると見えます.
ppaul
ozwk

2021/03/09 05:27

> ppaulさん グラム・シュミットの正規直交化法は(3次元であれば)線形独立な3つのベクトルから正規直交基底を作る方法ですが、この質問は1つしかベクトルがない場合どうするか? なので趣旨がちょっと違うかなと思います
fana

2021/03/09 05:30

どのみち得られたベクトルは正規化して用いることになるだろうから,正規化前のベクトルを得るために与える(x,y)の選択については(方向の精度さえ十分担保されるならば)わりとどうでもいい …という趣旨でしょうか?
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.36%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問