スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

計算誤差

計算幾何の問題 (AOJ1267) を解いていて、はまった点があったのでメモ。
原因を特定するのに 2 日もかかった。

Tag : アルゴリズム

原因は計算誤差。

プログラム中では、点 P が直線 AB 上にあるかどうかの判定を
abs( cross( A-P, B-P ) ) < EPS
としていた。
( cross(a, b) = |a|・|b| sinθ の意味 )

点の実装には double 型を使っているので、精度は 15 桁程度。
上の問題の場合は、点の座標値が 103 オーダーになるため、10-12 程度の精度になる。

cross(a, b) の実装は ax by - ay bx としていた。
2 数の乗算をした段階で精度は 10-9 に落ちる。
なので、A-P と B-P が平行のときに cross(A-P,B-P) を計算すると、たとえ理論値がジャスト 0 でも、計算結果は 10-9 程度になりうる。

これらの事情をよく考えずに
const double EPS=1e-9;
としていたので、ここの判定で間違ってしまっていたということ。

結局、EPS=1e-7 として Accepted をもらったが、すべての関数で共通の EPS を使うのは本当はよくないんだなと思った。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。