当浮动精度问题出现时，您如何能够实际解决凸包问题？

假设曲线上有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

当浮动精度问题出现时，您如何能够实际解决凸包问题？

回答

相关问题