189
правок
Изменения
Нет описания правки
Допустим нам дана задача: Даны два отрезка AB и CD (они могут вырождаться в точки). Требуется проверить, пересекаются они на плоскости или нет. Для упрощения определения этого факта в вычислительной геометрии используется предикат "левый поворот" (или "по часовой стрелке").
Итак, у нас есть задача, с чего начнем её решать? Какие вообще могут быть расположения точек и самих отрезков относительно друг друга?
{{Определение
|definition =
Left_Turn(a, b, c) = true, если <tex>(b - a)</tex>х<tex>\times(c - a) > 0</tex>
}}
Распишем поподробнее:
<tex>(b - a)</tex> х <tex>\times(c - a) = (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x) = A - B</tex>
Какие при этом у нас будут погрешности?
Нам нужно точно определить знак нашего выражения. Будем использовать для его вычисления [[Интервальная арифметика |"интервальную арифметику"]]. Все исходные переменные, входящие в него, будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам неизвестны, но они обязательно будет содержаться в посчитанных интервалах.
Допустим, что все числа положительные и будем писать без модулей:
NB: при сложении складываются абс. погрешности,при умножении складываются отн. погрешности.
<texdpi = "150">\delta (b - a)</tex>х<tex>\times(c - a) = |A|*\cdot \epsilon*\cdot (\frac{(|b_x|+|a_x|)/}{(|b_x|*|\cdot a_x|)} +\frac{(|c_y|+|a_y|)/}{(|c_y|*|\cdot a_y|)}) + </tex> <tex> + |B|*\cdot \epsilon*\cdot (\frac{(|b_y|+|a_y|)/}{(|b_y|*|\cdot a_y|)} +\frac{(|c_x|+|a_x|)/}{(|c_x|*|\cdot a_x|)})</tex>
Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Какую? Посмотрим внимательнее на наш предикат. Ошибка раскрывается тогда, когда угол между отрезками АВ и АС крайне мал.
