如何处理线段包含点算法中的浮点错误

Question

我正在研究一些几何算法，并且我一直在努力缓解浮点错误。

更具体地说，我写了一个方法来检查线段是否包含一个点，通过将这个点到线段两个端点的距离之和与线段的长度进行比较。

我目前使用固定的 epsilon 值，但当点离端点太近或线段太长时，它似乎返回无效输出。

下面Java中的示例代码：

public boolean lineSegmentContainsPoint(Vec3D line, Vec3D point) {
        final float eps = 0.001f;
        final float lineLength = line.startPt.distanceTo(line.endPt);
        final float distanceToStart = point.distanceTo(line.startPt);
        final float distanceToEnd = point.distanceTo(line.endPt);
        return Math.abs(lineLength - (distanceToStart + distanceToEnd)) < eps;
    }

我知道问题是由累积的浮点错误引起的，但我不太清楚如何解决它。我尝试使用 double 而不是 float，但它在上述边缘情况下并没有真正帮助。非常感谢任何建议或帮助！

Answer 1

这样的点的轨迹

D0 + D1 - L < ε

(由三角不等式，不用取绝对值)是长轴椭圆的内部

L + ε/2

和短轴

√(2Lε + ε²).

它可能包含您意想不到的要点。我不会认为此测试对 "line segment insideness" 有好处。我怀疑你的问题与浮点数不准确有关。

如何处理线段包含点算法中的浮点错误

How to handle floating point error in line segment contains point algorithm

floating-point

precision

computational-geometry