最も正確なラインの交点座標計算と山車？

Question

Iは、与えられた横座標xでのライン上の点の縦座標yを算出しています。ラインは、その2点の端点座標（X0、Y0）、（X1、Y1）によって定義されます。終点座標は浮動小数点であり、GPUで使用するには浮動小数点精度で計算を行う必要があります。

数学、したがって素朴な実装は簡単です。 /（X1 - X0）、次いで、Y =（1 - t）は* Y0 + 1 T * Y1 = Y0 + T *（Y1 - Y0） -

は、T =（X0 X）をしましょう。 X0小さい - x1はとき

問題があります。その結果、キャンセルエラーが発生します。分裂の中でx - x0のものと組み合わせると、tの重大な誤差が予想されます。より良い精度でYを決定する別の方法が存在する場合

質問はありますか？

つまり、最初に（x - x0）*（y1 - y0）を計算し、その後に（x1 - x0）で除算する必要がありますか？

差Y1 - Y0は常にビッグになります。

Answer 1

大程度に、あなたの根本的な問題が基本です。 （X1-X0）が小さい場合には、異なるX1とX0の仮数でほんの数ビットがあることを意味します。そして、拡張によって、x0とx1との間には浮動小数点数しかない。例えば。仮数の下位4ビットのみが異なる場合、それらの間に最大14の値が存在する。

最高のアルゴリズムでは、tという用語はこれらの下位ビットを表します。また、x0とx1が4ビット異なる場合、tは16個の値しか取れません。これらの可能な値の計算はかなり堅牢です。 3E0/14E0または3E-12/14E-12の計算に関わらず、結果は3/14という数学的な値に近くなります。

あなたの式は、Y0 < = Y < = Y1を持つことのさらなる利点を有する、0 < = T < = 1

ので、（私は「あなたはフロート表現について十分に知っていると仮定し、そのためだ（X1 x0 = 1E3のときは1E-1の差が小さいが、x0 = 1E-6のときは大きくなる）

Answer 2

可能性がある場合、abs（x1-x0）< abs（y1-y0）に応じて、計算に2つのケースを導入できます。垂直ケースABS（X1-X0）< ABS（Y1-Y0）、yから計算Xの代わりに、XからYに。

EDIT。別の可能性は、二分探索の変形を使用してビットごとに結果を得ることであろう。これは遅くなりますが、極端な場合には結果を改善する可能性があります。

// Input is X 
xmin = min(x0,x1); 
xmax = max(x0,x1); 
ymin = min(y0,y1); 
ymax = max(y0,y1); 
for (int i=0;i<20;i++) // get 20 bits in result 
{ 
    xmid = (xmin+xmax)*0.5; 
    ymid = (ymin+ymax)*0.5; 
    if (x < xmid) { xmax = xmid; ymax = ymid; } // first half 
    else { xmin = xmid; ymin = ymid; } // second half 
} 
// Output is some value in [ymin,ymax] 
Y = ymin; 

Answer 3

ソース・データがすでに、あなたはすでに基本的な不正確さを持っているフロートである場合。

は、さらに説明あなたがグラフィカルにこれをやっていた場合を想像してください。あなたは2次元のグラフ紙を持ち、2点をマークしています。

ケース1：これらのポイントは非常に正確で、非常に鮮明な鉛筆でマークされています。そのそれらを結ぶ線を描きやすく、その後、yの特定のx（またはその逆）を取得するのは簡単。

ケース2：これらのポイントにはビンゴマーカーのような大きな脂肪のフェルトペンが付いています。明らかに描画する線はあまり正確ではありません。あなたはスポットの中心を通りますか？上端？下端？一番上、もう一本の底？明らかに多くの異なるオプションがあります。 2つのドットがお互いに近接していると、ばらつきはさらに大きくなります。

浮動小数点数は、数値を表現する方法のために、ある程度の不正確さを持っています。ケース2（ケース1（任意の精度の刻印を使用することと同等です）よりケース2に対応します）。世界のどのアルゴリズムもこれを補うことはできません。データが不正確である、不正確なデータがある

Answer 4

x0とx1の間の距離が小さいかどうか、つまりfabs（x1 - x0）< epsを確認します。次いで、ライン、すなわち、あなたがX上に応じてそのラインのY値をcalculuateことができない、座標系のy軸にparallellあります。無限のy値があるため、このケースを別に扱わなければなりません。

Answer 5

コンピューティングはどうですか次のようなもの：

t = sign * power2 (sqrt (abs(x - x0))/ sqrt (abs(x1 - x0))) 

考え方は、low（x1-x0）の影響が少ない数学的に等価な公式を使用することです。 （私がこの基準に一致するかどうかわからない場合）

Answer 6

私は、異なる表現の効果を比較するベンチマークプログラムを実装しました。

私はyを倍精度で計算してから、異なる精度の単精度を使ってyを計算しました。ここ

は、試験した式である：

inline double getYDbl(double x, double x0, double y0, double x1, double y1) 
{ 
    double const t = (x - x0)/(x1 - x0); 
    return y0 + t*(y1 - y0); 
} 

inline float getYFlt1(float x, float x0, float y0, float x1, float y1) 
{ 
    double const t = (x - x0)/(x1 - x0); 
    return y0 + t*(y1 - y0); 
} 

inline float getYFlt2(float x, float x0, float y0, float x1, float y1) 
{ 
    double const t = (x - x0)*(y1 - y0); 
    return y0 + t/(x1 - x0); 
} 

inline float getYFlt3(float x, float x0, float y0, float x1, float y1) 
{ 
    double const t = (y1 - y0)/(x1 - x0); 
    return y0 + t*(x - x0); 
} 

inline float getYFlt4(float x, float x0, float y0, float x1, float y1) 
{ 
    double const t = (x1 - x0)/(y1 - y0); 
    return y0 + (x - x0)/t; 
} 

Iは、倍精度の結果と単精度結果との差の平均値とSTDDEVを計算しました。

この結果、平均で1000個以上のランダム値セットが存在しないことになります。私はiccコンパイラを使用し、最適化せずにg ++を使用しました。

私は、偽の値をフィルタリングするためにisnan（）関数を使用しなければならないことに注意してください。私は、これらの結果が差異または部門のアンダーフローに起因すると考えています。

コンパイラが式を再配置するかどうかわかりません。とにかく、このテストからの結論は、式の上記の再編成が計算精度に影響を与えないということである。エラーは（平均して）同じままです。

Answer 7

Qtの "QLine"（私が正しく覚えていれば）のソースがあります。彼らは "Graphics Gems"の書籍（コードのコメントに参照が入っていなければならず、数年前にEDonkeyに書かれていた）から取った交差点決定アルゴリズムを実装しました。与えられたビット幅で計算が実行されるときに与えられたスクリーン解像度（私が間違っていなければ固定小数点演算を使用する）。

Answer 8

MSaltersが述べたように、この問題は既に元のデータにあります。

補間/外挿には、与えられた条件で精度が低い（傾きが原点から離れた非常に短い線分では最悪）スロープが必要です。

アルゴリズムの選択は、この精度の損失を取り戻すことができません。私の直感は、エラーがデビジョンではなく減算によって導入されるため、異なる評価順序では物事が変わらないということです。

---

アイデア：
あなたはより正確なデータを持っている場合はラインが生成されるとき、あなたは（X0、Y0に（（X0、Y0）、（X1、Y1））からの表現を変更することができ、角度、長さ）。あなたは角度や勾配を格納することができます、勾配はポールを持っていますが、角度は三角関数が必要...醜い。

もちろん、エンドポイントが頻繁に必要な場合や、追加のデータを保存できないほど多くの行がある場合はうまくいきません。わかりません。しかし、おそらくあなたのニーズに適した別の表現があります。

ほとんどの状況で2倍の解像度で十分な解像度が得られますが、これも作業セットの2倍になります。