Изменения

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

Одно из решений - определитьОпределим, лежат ли точки концов отрезков по разные стороны от другого отрезка. Вот тут нам и поможет наш предикат, где два из трех аргументов (например a и b) это точки концов одного отрезка, а последний - один из концов другого отрезка.

Left_Turn<tex dpi = "120">$$\operatorname{LeftTurn}(a, b, c) = true\left\{\begin{array}{rl}-1 &\mbox{, если if}\ (c - a)\times(b - a) <tex>0\\0 &\mbox{, if}\ (c - a)\times(b - a)</tex>х<tex>= 0\\1 &\mbox{, if}\ (c - a)\times(b - a) > 0\end{array}\right.$$</tex>

Распишем поподробнееподробнее:<texdpi = 120>(b c - a)</tex> х <tex>\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>

NB: при сложении складываются абс. погрешностиЗаметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит,что при умножении складываются отн. погрешностивычислениях мы можем допустить ошибку.Распишем вещественное исчисление:

<texdpi = 140>\delta V = (b c - a)</tex>х<tex>\times(c b - a) = |A|*\epsilon*approx ((|b_x|+|c_x \ominus a_x|)/\otimes(|b_x|*|a_x|b_y \ominus a_y)+\ominus (|c_y|+|\ominus a_y|)/\otimes(|c_y|*|a_y|b_x \ominus a_x)) + =</tex>

<texdpi = 130> + |B|*= \epsilon*big((|b_y|+|a_y|c_x - a_x)/(|b_y|*|- a_y|)(1 +\delta_1)(|c_x|1 +|a_x|\delta_2)/(|c_x|*|a_x|)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}| \le 8 \varepsilon_m</tex>, если ноль попадает в наш интервал, то приходится пользоваться более тяжелой артиллерией, такими как [[ФайлAdaptive precision arithmetic|''adaptive precision arithmetic'']], либо [[Интервальная арифметика |''интервальная арифметика'']]. Во второй, исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах. '''Замечание:Tiny_angle''' расписанное неравенство смотрите в [[Представление_чисел_с_плавающей_точкой#.D0.A0.D0.B0.D1.81.D1.87.D0.B5.D1.jpg82|''другом конспекте'']]

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