Изменения
Нет описания правки
[[Файл:Tiny_angle.jpg]]
Заметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Более точно, определить знак нашего выражения поможет вычисление с [[Интервальная арифметика |''интервальной арифметикой'']]. Все исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах. Для точного вычисления необходимо фильтрованное вычисление предикатов. Распишем вещественное исчисление:
<tex dpi = 140>\overbrace {(c - a)\times(b - a)}^{V} = \overbrace{(c_x \ominus a_x)\otimes(b_y \ominus a_y) \ominus (c_y \ominus a_y)\otimes(b_x \ominus a_x)}^{\tilde{V}} =</tex>
Далее для пущей точности добавим floating point ariphmetics:
<tex dpi = 130>((1 + \varepsilon_m)^4 - 1) \cdot |(c_x \ominus a_x)\otimes(b_y \ominus a_y) \oplus (c_y \ominus a_y)\otimes(b_x \ominus a_x)| =</tex>
<tex dpi = 130>= \frac{(1 + \varepsilon_m)^4 - 1}{(1 + \varepsilon_m)^3} \cdot |(c_x - a_x)(b_y - a_y) \oplus (c_y - a_y)(b_x - a_x)| =</tex>
<tex dpi = 130>= \frac{(1 + \varepsilon_m)^4 - 1}{(1 + \varepsilon_m)^4} \cdot |(c_x - a_x)(b_y - a_y) + (c_y - a_y)(b_x - a_x)| </tex>
Замаксимизируем первый множитель:
<tex dpi = 130> \frac{(1 + \varepsilon_m)^4 - 1}{(1 + \varepsilon_m)^4} = \frac{4 \varepsilon_m - 6 \varepsilon^2_m + 4 \varepsilon^3_m + \varepsilon^4_m}{1 - 4 \varepsilon_m + 6 \varepsilon^2_m - 4 \varepsilon^3_m - \varepsilon^4_m} \le</tex>
<tex dpi = 130>\le frac{5 \varepsilon_m}{1 - 4 \varepsilon_m} \le 8 \varepsilon_m</tex>
'''Замечание:''' последнее неравенство верно, т.к. <tex dpi = 130>1 - 4 \varepsilon_m \le frac{5}{8}</tex>
Таким образом мы получили радиус нашей окрестности <tex dpi = 130>|V - \tilde{V}|</tex>, если же ноль таки попал в наш интервал, то приходится пользоваться более тяжелой артиллерией, такими как [[Adaptive precision arithmetic|''adaptive precision arithmetic'']], либо [[Интервальная арифметика |''интервальная арифметика'']]. Во второй, исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах.
=Bounding box=
Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай надо рассмотреть рассматривается отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют ''проверкой на bounding box'').
[[Файл:Bounting_box().png]]
