Изменения

Даны два отрезка, которые задаются начальной и конечной точками <tex>a,b\ \mathcal{2}\ \mathbb R^2</tex> и определяются как множества точек <tex>s\ =\ \{(1-t)a + tb,\ t\ \mathcal{2}\ in [0;1]\}</tex>. Требуется проверить существование множества их общих точек. Для определения этого факта в вычислительной геометрии используется предикат "''левый поворот" '' (или "''по часовой стрелке"'').

Left\_Turnoperatorname{LeftTurn}(a, b, c) =\left\{

'''Замечание:''' при сложении складываются абс. абсолютные погрешности,при умножении складываются отн. относительные погрешности.

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

Заметим, что все координаты (а , значит , и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Более точно , определить знак нашего выражения поможет вычисление с [[Интервальная арифметика |"''интервальной арифметикой"'']]. Все исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах. Для точного вычисления необходимо

Именно поэтому, когда угол между отрезками АВ и АС КРАЙНЕ МАЛ''крайне мал'', мы можем получить неверное значение предиката.

Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай надо рассмотреть отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют "''проверкой на bounding box"'').