寺田です．
> 私もこの問題については，おそらく5年以上悩んでいます(その後，
> 5年以上忘れていましたが)．そして，解が見つけられていません．
や，やっぱりそうですか・・・（涙）
私もそうなりそうです．
> ところで，XP 的に考えて，「どうせ全ケースのテストはできない
> から，アルゴリズムが正しいことだけでもテストしよう」という姿
> 勢に立てば，上記の誤差マップを安全サイドに単純化することが可
> 能だと思います．これなら，実用可能かも．たとえば，a, b を
> 1e-6 〜 1e+6 に限って，eps = min(a, b, 1e-6) でテストする，
> とか．
なるほど，そうですね．
この辺は，「幻覚剤としてのテストファースト」のスレッドとも絡みそうです．
「どうせ全ケースのテストは出来ない」というスタンスから，「テストはコンパ
イラの延長」程度に考えて，「テストによってコードが正しいことを証明しよう」
としないほうが良いのかもしれません．
> CAD でよく問題になる「近傍」の扱いも同じですよね．結局，ある
> 近傍を「等しい」と見なす，という考え方が，ブロークンコンセプ
> トなんだ，とも思います．つまり，近傍の近傍は近傍だ．という論
> 法を三段論法で重ねると，有限範囲のすべての点は，近傍になって
> しまう，ということ．
その通りです．
「近傍」の概念で同一判定をすると，同値関係の推移則が成立しなくなってしま
います．結局，浮動小数点は実数を模擬しているだけで，実数そのものではない
のです．従って，浮動小数点演算は数学とは良く似ていても実は異なるものだと
考えなくてはならないようです．
この辺りの，どうしても形状処理に紛れ込んでしまう「泥臭さ」が，オブジェク
ト指向や契約主導設計，ユニットテストといった技術の導入を阻んでいるような
気がしてなりません．
なんとかしたいという気持ちは強く持っているのですが・・・．
> また便乗質問になってしまいますが，そういえば，以前，こういう
> double と epsilon を使った形状処理ではなく，ディスクリートな
> 同一判定と多倍長数を使った形状処理の論文(本?)を読んだことが
> ありますが，失念しました．寺田さんご存知ないでしょうか? これ
> を使った形状処理アプリケーションは，世の中にないのでしょうか
> ね?
私が読んだのは，「4次元理論による図形・形状処理工学，山口富士夫」です．
この本では，「諸悪の根源は除算である」と主張しています．そして，幾何演算
を全て同次座標系で行うことにより，ベクトルや行列に対する除算を完全に取り
除くことを提案しています．除算を排除すると，加算/減算/掛算 だけになりま
すから，すべて（多倍精度の）整数演算で行うことが可能になります．
さて，この手法を実際に適用したアプリケーションがあるかどうかですが・・・．
残念ながら，私は聞いたことがありません．（あるのかなぁ・・・？）
・今までに作り込んできた形状処理ライブラリがすべて無駄になるのでは？
・既存の浮動小数で表現されたデータが読めないのでは？
・他のCADとのデータ交換が出来ないのでは？
などと考えていくと，ビジネスとして実際に作るにはシビアな部分もあるでしょ
うね．個人的には作ってみたいですが．
なお，他にも「計算幾何工学，杉原厚吉」にも幾何演算を頑健に行うための工夫
が解説されています．こちらはもうちょっと気軽に使える手法ですので，実用に
もなっていると思います．この本で紹介されているのは，
・整数帰着法 ・・・ 全部整数演算に置き換えてしまえ！
・記号摂動法 ・・・ 記号的な摂動により，面倒な特殊処理を減らそう！
・位相優先法 ・・・ 幾何データよりも位相データを信じろ！
です．
以上です．
--
Y.Terada <terada@....jp>