189
правок
Изменения
Нет описания правки
[[Файл:Cross.png]]
[[Файл:Touch.jpg]]
Одно из решений - определить, лежат ли точки концов отрезков по разные стороны от другого отрезка. Вот тут нам и поможет наш предикат, где два из трех аргументов (например a и b) это точки концов одного отрезка, а последний - один из концов другого отрезка.
{{Определение
|definition =
</tex>
}}
Распишем поподробнееподробнее:
<tex>(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>
Какие при этом у нас будут погрешности?
Допустим, что все числа положительные и будем писать без модулей:
<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>
Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Какую? Точно определить знак нашего выражения поможет вычисление с [[Интервальная арифметика |"интервальной арифметикой"]]. Все исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах. TODO: тут еще чего-то написать... Посмотрим внимательнее на наш предикат. Ошибка раскрывается тогда, когда угол между отрезками АВ и АС крайне мал.
[[Файл:Tiny_angle.jpg]]
=Bounding box=
Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай надо рассмотреть отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют "проверкой на bounding box").
[[Файл:Bounting_box().png]]
[[Файл:Bounting_box_.png]]
Псевдокод:
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 (TODO:)
вернуть true
вернуть false
