Изменения

-1 &\mbox{, if}\ (b c - a)\times(c b - a) < 0\\0 &\mbox{, if}\ (b c - a)\times(c b - a) = 0\\1 &\mbox{, if}\ (b c - a)\times(c b - a) > 0

<tex dpi = 120>(b c - a)\times(c b - a) = (b_x c_x - a_x)(c_y b_y - a_y) - (b_y c_y - a_y)(c_x b_x - a_x) = A - BV</tex>

<tex dpi = "150"> \delta (b c - a)\times(c b - a) = A \varepsilon \left(\frac{(b_x c_x + a_x)}{(b_x c_x \cdot a_x)} + \frac{(c_y b_y + a_y)}{(c_y b_y \cdot a_y)}\right) + B \varepsilon \left(\frac{(b_y c_y + a_y)}{(b_y c_y \cdot a_y)} + \frac{(c_x b_x + a_x)}{(c_x b_x \cdot a_x)}\right)</tex>

Именно поэтому, когда угол между отрезками АВ и АС ''крайне мал'', мы можем получить неверное значение предиката. [[Файл: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> <tex dpi = 130>= \big((c_x - a_x)(b_y - a_y)(1 + \delta_1)(1 + \delta_2)(1 + \delta_3)\ -</tex> <tex dpi = 130>-\ (c_y - a_y)(b_x - a_x)(1 + \delta_4)(1 + \delta_5)(1 + \delta_6)\big)(1 + \delta_7) = \tilde{V}</tex> <tex dpi = 130>\mid\delta_i\mid \le \varepsilon_m = 2^{-54}</tex>; Получим некую окрестность <tex dpi = 130>|V - \tilde{V}|</tex> судя по которой мы сможем точнее определить, не ошиблись ли мы знаком(если ноль не входит в нашу окрестность, тогда знак верен, иначе "we need go deeper") Найдем более точно нашу окрестность: <tex dpi = 130>|V - \tilde{V}| = |\big((1 + \delta_7)(1 + \delta_3)(1 + \delta_2)(1 + \delta_1) - 1 \big)(c_x - a_x)(b_y - a_y) -</tex>

<tex dpi = 140130>-\overbrace {\big((b - a1 + \delta_7)(1 + \times(c - adelta_6)}^{v} \approx \overbrace{(b_x 1 + \ominus a_xdelta_5)\otimes(c_y 1 + \ominus a_ydelta_4) - 1 \ominus big)(b_y \ominus c_y - a_y)\otimes(c_x \ominus b_x - a_x)}^{| \tilde{v}} =le </tex>

<tex dpi = 130>= \bigle |P(\delta_7, \delta_3, \delta_2, \delta_1)|\cdot|(b_x c_x - a_x)(c_y b_y - a_y)| + |Q(1 + \delta_1delta_7, \delta_6, \delta_5, \delta_4)|\cdot|(1 + \delta_2c_y - a_y)(1 + \delta_3b_x - a_x)|\ -le</tex>

<tex dpi = 130>-\ le ((b_y 1 + \varepsilon_m)^4 - a_y1)\cdot |(c_x - a_x)(1 + \delta_4b_y - a_y)(1 + \delta_5)(1 + \delta_6)\bigc_y - a_y)(1 + \delta_7b_x - a_x)|</tex>