Как правильно сравнить 2 пары? - PullRequest
Новая
       14

Как правильно сравнить 2 пары?

0 голосов
/ 01 ноября 2018

Я делаю вычисления с треугольниками. Но мне нужно знать, если три заданные точки не находятся на одной линии. Для этого я вычисляю площадь треугольника

area = (Ax * (By-Cy) + Bx * (Cy-Ay) + Cx * (Ay-By));

Если площадь равна нулю, то все три точки являются коллинеарными. Но проблема в том, что он никогда не равен нулю, поскольку удваивающие и поплавки очень неточны, поэтому 

if(area==0){
 printf("It's not a triangle");   
 }

не будет работать. Как правильно решить эту проблему?

Ответы [ 3 ]

0 голосов
/ 01 ноября 2018

Я бы попробовал что-то вроде этого:

#include <float.h> ... if ( (area < FLT_EPSILON) && (area > -FLT_EPSILON) ) { printf("It's not a triangle"); }

0 голосов
/ 01 ноября 2018

Позволяет нам прояснить некоторые причинно-следственные связи и копать глубже.

Неправильная формула для области

Площадь составляет 1/2 от формулы ОП, но это не делает различий при сравнении с 0.0. 

// area=(Ax* (By-Cy) + Bx* (Cy-Ay) + Cx* (Ay-By));
area=(Ax* (By-Cy) + Bx* (Cy-Ay) + Cx* (Ay-By))/2;

Неточность

«поскольку двойные и плавающие числа очень неточны», само по себе неточно. Все конечные значения FP точны , как целые числа. Именно при сравнении их операций с математическим делением они получают неправильное число «неточно». Как и целочисленное деление, деление FP и другие базовые математические операции FP, они определяются иначе, чем математические операции. 7/3 и 7.0 / 3.0 оба не приводят к математическому 2 1 / 3 , но имеют другое значение. Когда C использует математическую модель IEEE, этот «коэффициент» не является приблизительным, но точным.

Сравнивая сколько?

«сравнить 2 двойки» вводит в заблуждение, так как эффективно это сложное сравнение 6 double, которое должен выполнить код.

Обзор формулы теста

Ax* (By-Cy) + Bx* (Cy-Ay) + Cx* (Ay-By) с double операндами будет вести себя без округления, пока подэтапы не округляются. В general это невозможно. Обходные пути

  1. Используйте более высокую точность

Выполните тест, используя long double. Это не устраняет проблему, а только делает ее меньше / менее вероятной. Примечание long double необязательно иметь более высокую точность.

  1. Используйте какой-нибудь эпсилон

Наивный подход берет результат | вычисленная площадь | и сравнивается с эпсилон . Абсолютные области ниже, которые считаются "нулем". Это не очень хорошо масштабируется, так как epsilon действительно зависит от величины операндов относительно области. Необходим относительный эпсилон. Предложить fmax(|ax|,|bx|,|cx|) * fmax(|ay|,|by|,|cy|) * DBL_EPSILON. Это только приближение первого порядка.

  1. Искать смену знака

Формула площади - это область со знаком . Эффективно изменяя порядок a, b, c инвертирует знак области. Если небольшое возмущение любого из 8 операндов на operand_new=operand*(1 +/- DBL_EPSILON) приведет к изменению знака области, площадь можно оценить как "достаточно близкую к нулю".

  1. Переупорядочить формулу.

Это вычитание значений удаленных значений, которые убивают точность. Обмен x s на y s может помочь во внутренних вычитаниях термина. Повторный заказ вычитания 3 продуктов может помочь.

Более качественный повторный заказ может быть выполнен в форме формирования 6 продуктов: Ax By, -Ax Cy, Bx Cy, -Bx Ay, Cx Ay, -Cx Затем суммировать их.

Оба из этих преимуществ используют алгоритм суммирования Кахана SO , возможно, с использованием fma().

Для меня я бы исследовал # 4b или # 3. Если бы ОП опубликовал Минимальный, завершенный и проверяемый пример , данные образца и ожидаемые результаты образца, можно было бы получить истинный код. Не имея этого, рассмотрим эти исходные идеи для нечеткой задачи.

0 голосов
/ 01 ноября 2018

Вы выясните: сколько может быть ошибок округления? Если вы используете двойную точность, а результат одной операции равен x, тогда ошибка округления может составлять до abs (x) / 2 ^ 52. (Если вы не используете double, тогда используйте double.)

Вы делаете это и находите ошибку округления в By-Cy, Cy-Ay, Ay-By. Эти три ошибки умножаются на Ax, Bx и Cx. Три продукта имеют собственную ошибку округления. Тогда у вас есть ошибка при добавлении первых двух продуктов, а затем при добавлении третьего продукта. Вы складываете все эти ошибки и получаете максимальную суммарную ошибку e.

Так что, если площадь меньше чем e, то вы можете предположить, что они находятся на прямой линии.

Чтобы улучшить это: если Ax, Bx, Cx все положительные (скажем, 100, 101, 102.5), то вы вычисляете среднее значение и вычитаете из Ax, Bx и Cx. Это делает ваши числа меньше, а ошибки округления меньше.

...