數值不準確計算交點

我想計算光線和線段之間的交點。爲此我形成線性方程並尋找交點。現在我遇到一個例子的數值問題。我的代碼的縮寫：數值不準確計算交點

public class Test { 
    public static void main(String[] args) { 
     double rayAX = 443.19661703858895d; 
     double rayAY = 666.3485960845833d; 

     double rayBX = 443.196744279195d; 
     double rayBY = 103.21654864924565d; 

     double segAX = 450.0d; 
     double segAY = 114.42801992127828d; 

     double segBX = 443.196744279195d; 
     double segBY = 103.21654864924565d; 


     double a1 = (rayBY - rayAY)/(rayBX - rayAX); 
     double t1 = rayAY - rayAX * a1; 

     double a2 = (segBY - segAY)/(segBX - segAX); 
     double t2 = segAY - segAX * a2; 

     double x = (t2 - t1)/(a1 - a2); 
     double y = a1 * x + t1; 

     System.out.println(x); 
     System.out.println(y); 
    } 
}

顯然回報應該是（443.196744279195，103.21654864924565），因爲這點是在光線和段都相同。但實際回報是在我的情況（443.19674427919506,103.21654844284058）

在第二個數字中有一個錯誤已經在小數點後六位。我想這個錯誤是因爲rayAX和rayBX的值非常接近。我的問題是：計算交叉點時可以得到更精確的結果嗎？

來源

2014-11-22 Geminus

當你的方程組接近[單數]（http://en.wikipedia.org/wiki/Invertible_matrix）時，數值問題總是可能的。 – 2014-11-22 22:12:19

這裏得到相交點的數值上更穩定的方式（請注意，它實際上是兩條線的交叉點......好像你原來的代碼沒有檢查是否是路口段內任一）：

double rX = rayBX - rayAX;                                   
double rY = rayBY - rayAY;                                   

double sAX = segAX - rayAX;                                   
double sAY = segAY - rayAY;                                   
double areaA = sAX * rY - sAY * rX;                                 

double sBX = segBX - rayAX;                                   
double sBY = segBY - rayAY;                                   
double areaB = sBX * rY - sBY * rX;                                 

double t = areaA/(areaA - areaB); 
// if t is not between 0 and 1, intersection is not in segment                         
double x = (1 - t) * segAX + t * segBX;                                
double y = (1 - t) * segAY + t * segBY;

粗糙的解釋：讓A和B是光線的終點，並讓X和Y是線段的端點。讓P成爲我們正在尋找的交點。然後，PX與PY的比率等於ABX的面積與ABY的面積的比率。您可以使用交叉產品來計算區域，這就是上面的代碼所做的。請注意該過程如何僅使用一個分區，這有助於將數字不穩定性降至最低。

來源

2014-11-22 22:26:59 arghbleargh

這肯定更準確！你有鏈接，我可以得到關於這方面的更多信息？ – Geminus 2014-11-22 22:50:39

如果我想交叉兩段，我想我可以找出另一個噸，如果我通過在計算過程中切換「seg」和「ray」來計算新的areaA和新的areaB？對於這個新的t我也可以檢查它是否在0和1之間。 – Geminus 2014-11-22 23:40:22

是的，那可行。 – arghbleargh 2014-11-22 23:42:32

據我所知，通過高斯或高斯 - 喬丹方法獲得最佳的數值穩定性，並具有總旋轉。

您需要解決這個線性2x2系統R和S。

(Brx - Arx).R - (Bsx - Asx).S = Asx - Arx 
(Bxy - Ary).R - (Bsx - Asx).S = Asy - Ary

總樞告訴你選擇與最大的模塊LHS係數。有四種可能的選擇，因此你將不得不實現算法的四個版本。

例如，假設左上方係數是在系統

A.X + B.Y = C 
D.X + E.Y = F

然後

X + (B/A).Y = (C/A) 
D.X + E .Y = F

主導，

(E - D.(B/A)) Y = F - D.(C/A)

和

Y = (F - D.(C/A))/(E - D.(B/A)) 
X = (C/A) - (B/A).Y

使用精確算術，這實際上等同於克拉默的規則，但從數值的角度來看可能更好。

其他案件均對稱處理。

來源

2014-11-23 09:48:54

數值不準確計算交點

回答

相關問題