Изменения

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

Распишем вещественное исчисление: <tex dpi = 140>\overbrace {V = (c - a)\times(b - a)}^{V} = \overbrace{approx (c_x \ominus a_x)\otimes(b_y \ominus a_y) \ominus (c_y \ominus a_y)\otimes(b_x \ominus a_x)}^{\tilde{V}} =</tex>

Получим некую окрестность <tex dpi = 130>|V - \tilde{V}|\le 8 \varepsilon_m</tex> судя по которой мы сможем точнее определить, не ошиблись ли мы знаком(если ноль не входит попадает в нашу окрестностьнаш интервал, тогда знак веренто приходится пользоваться более тяжелой артиллерией, иначе "we need go deeper") Найдем более точно нашу окрестность: <tex dpi = 130>такими как [[Adaptive precision arithmetic|V - \tilde{V}| = |\big((1 + \delta_7)(1 + \delta_3)(1 + \delta_2)(1 + \delta_1) - 1 \big)(c_x - a_x)(b_y - a_y) -</tex> <tex dpi = 130>-\ \big((1 + \delta_7)(1 + \delta_6)(1 + \delta_5)(1 + \delta_4) - 1 \big)(c_y - a_y)(b_x - a_x)| \le </tex> <tex dpi = 130>\le ''adaptive precision arithmetic'']], либо [[Интервальная арифметика |P(\delta_7''интервальная арифметика'']]. Во второй, \delta_3, \delta_2, \delta_1)|\cdot|(c_x - a_x)(b_y исходные переменные будут вырожденными интервалами. Из- a_y)| + |Q(\delta_7за погрешностей, \delta_6возникающих при округлении вещественных чисел, \delta_5истинные значения операций нам будут неизвестны, \delta_4)|\cdot|(c_y - a_y)(b_x - a_x)|\le</tex> <tex dpi = 130>\le ((1 + \varepsilon_m)^4 - 1) \cdot |(c_x - a_x)(b_y - a_y) + (c_y - a_y)(b_x - a_x)|</tex> Далее для пущей точности добавим floating point ariphmetics:но они обязательно будет содержаться в посчитанных интервалах.

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