Как обрабатывать ошибку с плавающей запятой в линейном сегменте, содержащем алгоритм точки

Question

Я работаю над некоторыми геометрическими c алгоритмами и какое-то время борюсь с устранением ошибок с плавающей запятой.

Более конкретно, я написал метод для проверки, содержит ли линейный сегмент точку, сравнивая сумму расстояния от этой точки до двух конечных точек сегмента с длиной линейного сегмента.

В настоящее время я использую фиксированное значение 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 < ε

(по неравенству tri angular, абсолютное значение не требуется) находится внутри эллипса с длинной осью

L + ε/2

и короткая ось

√(2Lε + ε²).

Может содержать точки, которых вы не ожидаете. Я бы не оценил этот тест как хороший на «внутренность отрезка линии». Сомневаюсь, что ваша проблема связана с неточностью чисел с плавающей запятой.