189
правок
Изменения
Нет описания правки
Даны два отрезка, которые задаются начальной и конечной точками <tex>a,b\ \mathcal{2}\ \mathbb R^2</tex> и определяются как множества точек <tex>s\ =\ \{(1-t)a + tb,\ t\ \mathcal{2}\ [0;1]\}</tex>. Требуется проверить существование множества их общих точек. Для определения этого факта в вычислительной геометрии используется предикат "левый поворот" (или "по часовой стрелке").
Рассмотрим возможные расположения точек и самих отрезков относительно друг друга:
}}
Распишем подробнее:
<tex dpi = 130>(b - a)\times(c - a) = (b_x - a_x)\cdot(c_y - a_y) - (b_y - a_y)\cdot(c_x - a_x) = A - B</tex>
Какие при этом у нас будут погрешности?
NB: при сложении складываются абс. погрешности,при умножении складываются отн. погрешности.
<tex dpi = "150"> \delta (b - a)\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)}) + 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>
Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Точно определить знак нашего выражения поможет вычисление с [[Интервальная арифметика |"интервальной арифметикой"]]. Все исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах.
