當浮動精度問題出現時，您如何能夠實際解決凸包問題？

假設曲線上有100000個點y = x^2。你想找到這些點的凸包。所有的座標都是浮點數。當浮動精度問題出現時，您如何能夠實際解決凸包問題？

在我的格雷厄姆掃描實現中，我操作浮點數的唯一地方是當我最初按座標對所有點進行排序，然後我有一個函數確定三點是左轉還是右轉。

點：

struct point { 
    double x; 
    double y; 
};

排序比較：

inline bool operator() (const point &p1, const point &p2) { 
    return (p1.x < p2.x) || (p1.x == p2.x && p1.y > p2.y); 
}

左/右轉：

inline int ccw(point *p1, point *p2, point *p3) { 
    double left = (p1->x - p3->x)*(p2->y - p3->y); 
    double right = (p1->y - p3->y)*(p2->x - p3->x); 
    double res = left - right; 
    return res > 0; 
}

我的計劃說出來的100萬點僅68894的部分凸包。但是因爲它們在曲線上，它們都應該是凸包的一部分。

對你的眼睛不會有任何區別。見下圖。紅點是凸包的一部分。

image http://oi57.tinypic.com/t8lsvs.jpg

但如果你看看足夠接近，並放大到分，你會看到，他們中的一些是藍色的，所以它們並不包括在該凸包。現在

image http://oi61.tinypic.com/2eol37a.jpg

我最初的假設是，浮點錯誤導致此問題。

我想我可以使用具有浮點數任意精度的外部庫，但我更感興趣的是，我們有例如C++中的簡單數據類型。

我該如何提高準確度？我讀過關於epsilon的內容，但是如何在這裏使用epsilon幫助？我仍然會假設一些接近彼此的點是相同的，所以我不會得到接近100％的準確度。

解決此問題的最佳方法是什麼？

來源

2014-09-30 jsguy

你試過'長雙'嗎？ – mch 2014-09-30 14:16:12

您的凸包算法可能是正確的，但是當您最初評估y = x^2時會發生舍入？ – ajclinto 2014-09-30 14:17:14

首先，沒有有限的精度會讓你表示實數。其次，你繪製的點是近似值。第三，真正的建設性實在（無限精確）無法與你想比較的方式進行比較。第五，你爲什麼在意？（你有什麼目的，因此重要的船體） – Yakk 2014-09-30 14:19:05

你是正確的，所有的點應該是凸包，如果你確實使用形式(x, x^2)點。但是，三點可能是共線的。如果你正在轉移他們或者做其他奇怪的事情，這會消失。

如果你可以選擇你的10萬點，我建議在[-50000,49999]使用整數。你ccw功能將計算left和right是整數絕對值在2.5e14 < 2^53小，所以不會發生舍入。

無論輸入如何，基於座標的排序都可以正常工作。

對於一般的輸入，下面ccw謂詞是越野車：

inline int ccw(point *p1, point *p2, point *p3) { 
    double left = (p1->x - p3->x)*(p2->y - p3->y); 
    double right = (p1->y - p3->y)*(p2->x - p3->x); 
    double res = left - right; 
    return res > 0; 
}

可以有舍入二者在減法和在乘法。如果所有的點都位於H * W邊界框中，那麼將使用H * eps/2附近的絕對誤差來計算x座標差，並且計算y座標差的絕對誤差爲W * eps/2。因此產品將以H * W * eps/2左右的絕對誤差進行計算。如果fabs(left - right) < 3*H*W*eps/2，則需要更精確地評估left和right。 eps這裏是2 ^-52。

我可能會建議只使用MPFR如果double比較沒有告訴你任何東西。不過，你可以不用。來自Kahan總結的技巧會讓您獲得差異的低位，並且+1技巧可以幫助您準確計算產品。

來源

2014-09-30 16:26:16 tmyklebu

很多時候與浮點運算，你需要引入的「寬容」，也可能用小量的概念。在你的情況下，你可以讓你的ccw()函數三值化：true/false/indeterminate。然後，當你試圖發現一個新點是否可以成爲凸包的一部分時，你會問「這是ccw = true還是不確定」，並且你接受這一點。當斜率太接近於要確定的直線時，會發生不確定的結果。

來源

2014-09-30 14:29:01

當浮動精度問題出現時，您如何能夠實際解決凸包問題？

回答

相關問題