得到奇怪的結果與獲得點內三角形的方法

Question

我正在使用一種方法，我在互聯網上找到了在cpp中，我改變了一下java。它似乎只工作了一半時間。這是一個Java的錯誤？因爲它會根據三角形內的位置返回真或假。任何人都可以幫助我解決它或找到一個更好的方法來測試三角形內的一個點嗎？繼承人的方法。對不起，如果它很難理解的問題

public static float area(float x1, float y1, float x2, float y2, float x3, float y3) 
{ 
    return (float) Math.abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0); 
} 

/* A function to check whether point P(x, y) lies inside the triangle formed 
    by A(x1, y1), B(x2, y2) and C(x3, y3) */ 
public static boolean isInside(float x1, float y1, float x2, float y2, float x3, float y3, float x, float y) 
{ 
    /* Calculate area of triangle ABC */ 
    float A = area (x1, y1, x2, y2, x3, y3); 

    /* Calculate area of triangle PBC */ 
    float A1 = area (x, y, x2, y2, x3, y3); 

    /* Calculate area of triangle PAC */ 
    float A2 = area (x1, y1, x, y, x3, y3); 

    /* Calculate area of triangle PAB */ 
    float A3 = area (x1, y1, x2, y2, x, y); 

    /* Check if sum of A1, A2 and A3 is same as A */ 
    return (A == A1 + A2 + A3); 
} 

Answer 1

這是一個浮點精度的問題。請記住，浮點計算是以有限的精度執行的。因此，如果您進行的數學計算應該產生相同的結果，則計算機生成的實際結果通常不會相同。

問題因此是與這個測試：

return (A == A1 + A2 + A3); 

如果該點位於三角形內，A和A1 + A2 + A3將具有非常類似的值，但是計算過程中，由於有限的浮點精度不一定相同值。

最直接的方式來解決這將是允許在比較一些不精確：

return Math.abs(A - (A1 + A2 + A3) < eps); 

其中eps是一個小浮點常量。爲這些類型的容差選擇合適的值總是很棘手，因此最好避免使用這種必要的算法（請參閱下面的建議解決方案）。如果容差太小，三角形內部的測試點將失敗。如果你做得太大，你會允許更多的誤報，因爲稍微偏離三角形的點將通過測試。

如果您真的想要使用這種測試，測試相對差異而不是絕對差異會更穩定，因爲絕對誤差通常會隨着數值本身變大而增加。測試相對差應該是這樣的：

return Math.abs((A - A1 - A2 - A3)/A) < eps; 

然後爲eps的價值，我會的東西是安全比float值，這大約是7位數的相對精度更大的啓動。像1.0e-5f似乎是合理的。

有更好的方法做一個「三角點」測試。其實，我認爲你可以使用你已有的大部分數學。我還沒有測試過以下內容，所以沒有任何保修，但我相信它應該可以工作。

這個想法是，你並不需要關心所有的局部區域總和三角形的面積。我相信他們都是積極的就足夠了。您可以更改area功能通過移除abs()調用返回簽署面積：

public static float area(float x1, float y1, float x2, float y2, float x3, float y3) 
{ 
    return 0.5f * (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)); 
} 

然後像以前一樣計算A1，A2和A3，並檢查他們都是正面的：

return A1 >= 0.0f && A2 >= 0.0f && A3 >= 0.0f; 

這假設三角形有逆時針方向。如果您希望它也適用於順時針方向，則需要檢查所有三個值的符號是否相同。