c++ - 出现 float 精度问题时，如何实际解决凸包？

假设曲线y = x^2上有100000点。您想找到这些点的凸包。所有坐标均为浮点数。

在我的graham扫描实现中，我对浮点数进行操作的唯一地方是最初按它们的坐标对所有点进行排序，然后使用一个函数来确定三个点是向左还是向右转。

要点:

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;
}

我的程序说，在10万个点中，只有68894个是凸包的一部分。但是，由于它们在曲线上，因此它们都应该是凸包的一部分。

对您而言，这没有任何区别。参见下图。红点是凸包的一部分。



但是，如果您看起来足够近，并放大这些点，您会发现其中一些是蓝色的，因此它们不包含在凸包中。



现在，我最初的假设是浮点错误导致了此问题。

我想我可以使用对浮点数具有任意精度的外部库，但是我对例如C++中的简单数据类型更感兴趣。

如何提高准确性？我已经读过关于epsilon的信息，但是在这里使用epsilon会有什么帮助？我仍然会假设一些彼此接近的点是相同的，因此我不会获得接近100％的精度。

解决此问题的最佳方法是什么？

最佳答案

如果确实使用(x, x^2)形式的点，则所有点都应该在凸包上是正确的。但是，三个点可能是共线的。如果您要转移它们或进行其他任何奇怪的操作，则此操作不可用。

如果您可以选择100000点，我建议使用[-50000,49999]中的整数。您的ccw函数会将left和right计算为绝对值小于2.5e14
无论输入如何，基于坐标的排序都将正常工作。

对于常规输入，以下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边界框中，则x坐标差将以H * eps / 2的绝对误差计算，y坐标差将以W * eps /的绝对误差计算。 2。因此，将以大约H * W * eps / 2的绝对误差计算乘积。如果是fabs(left - right) < 3*H*W*eps/2，则需要更精确地评​​估left和right。 eps是2-52。

如果double比较不能告诉您任何信息，我可能会建议仅使用MPFR。但是，您可以不这样做。 Kahan求和的技巧将为您提供差值的低位，而227 + 1技巧可以帮助您准确地计算乘积。

关于c++ - 出现 float 精度问题时，如何实际解决凸包？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26122961/