Изменения

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

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

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

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

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

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

<tex dpi = "150"> \delta (b c - a)\times(c b - a) = A \cdot varepsilon \epsilon \cdot 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 \cdot \epsilon varepsilon \cdot 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>

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

TODO[[Файл: тут еще чего-то написать.Tiny_angle.jpg]] Заметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку.Распишем вещественное исчисление: <tex dpi = 140>V = (c - a)\times(b - a) \approx (c_x \ominus a_x)\otimes(b_y \ominus a_y) \ominus (c_y \ominus a_y)\otimes(b_x \ominus a_x) =</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}| \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|''другом конспекте'']]

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

Псевдокод[[Категория:  boolean Bounding_Box(точка A, точка B, точка C) if ((A.xx >= C.xx && C.xx >= B.xx || A.xx <= C.xx && C.xx <= B.xx) && (A.yy >= C.yy && C.yy >= B.yy || A.yy <= C.yy && C.yy <= B.yy)) вернуть true вернуть false или  boolean Bounding_Box(точка A, точка B, точка C, точка D) 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)) return false; return true;Вычислительная геометрия]]