189
правок
Изменения
Нет описания правки
}}
Распишем подробнее:
<tex dpi = 130120>(b - a)\times(c - a) = (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x) = A - B</tex>
Какие при этом у нас будут погрешности?
Допустим, что все числа положительные и будем писать без модулей:
<tex dpi = "150"> \delta (b - a)\times(c - a) = A \epsilon (\frac{(b_x + a_x)}{(b_x \cdot a_x)} + \frac{(c_y + a_y)}{(c_y \cdot a_y)}) + B \epsilon (\frac{(b_y + a_y)}{(b_y \cdot a_y)} + \frac{(c_x + a_x)}{(c_x \cdot a_x)})</tex>
Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Точно Более точно определить знак нашего выражения поможет вычисление с [[Интервальная арифметика |"интервальной арифметикой"]]. Все исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах. Для точного вычисления необходимофильтрованное вычисление предикатов.
<tex dpi = 140>\overbrace {(b - a)\times(c - a)}^{v} \approx \overbrace{(b_x \ominus a_x)\otimes(c_y \ominus a_y) \ominus (b_y \ominus a_y)\otimes(c_x \ominus a_x)}^{\tilde{v}} =</tex>
if (((A.xx > C.xx && A.xx > D.xx && B.xx > C.xx && B.xx > D.xx) || (A.xx < C.xx && A.xx < D.xx && B.xx < C.xx && B.xx < D.xx))
|| ((A.yy > C.yy && A.yy > D.yy && B.yy > C.yy && B.yy > D.yy) || (A.yy < C.yy && A.yy < D.yy && B.yy < C.yy && B.yy < D.yy)))
