189
правок
Изменения
Нет описания правки
Даны два отрезка AB , которые задаются начальной и CD конечной точками <tex>a,b\ \mathcal{2}\ R^2</tex> и определяются как множества точек <tex>s\ =\ \{(они могут вырождаться в точки1-t)a + tb,\ t\ \mathcal{2}\ [0;1]\}</tex>. Требуется проверить, пересекаются они на плоскости или нетсуществование множества их общих точек. Для упрощения определения этого факта в вычислительной геометрии используется предикат "левый поворот" (или "по часовой стрелке").
Рассмотрим возможные расположения точек и самих отрезков относительно друг друга:
[[Файл:Touch.jpg]]
{{Определение
|definition =
}}
Распишем подробнее:
<texdpi = 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>
Какие при этом у нас будут погрешности?
Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Точно определить знак нашего выражения поможет вычисление с [[Интервальная арифметика |"интервальной арифметикой"]]. Все исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах.
Посмотрим внимательнее на наш предикат. Ошибка раскрывается тогда, когда угол между отрезками АВ и АС крайне мал.
