Изменения

{{В разработке}}Допустим нам дана задача: Даны два отрезка AB , которые задаются начальной и конечной точками <tex>a,b\ \mathcal{2}\ \mathbb R^2</tex> и CD определяются как множества точек <tex>s\ =\ \{(они могут вырождаться в точки1-t)a + tb,\ t\ \in [0;1]\}</tex>. Требуется проверить, пересекаются они на плоскости или нетсуществование множества их общих точек. Для упрощения определения этого факта в вычислительной геометрии используется предикат "''левый поворот" '' (или "''по часовой стрелке"''). Для начала разберемсяРассмотрим возможные расположения точек и самих отрезков относительно друг друга: [[Файл:Cross.png]][[Файл:Two_segments.png]][[Файл:Touch.jpg]] Определим, что за зверь такой - Предикатлежат ли точки концов отрезков по разные стороны от другого отрезка.

'''Предикат''' <tex dpi = "120">$$\operatorname{LeftTurn}(лат. '''praedicatum''' — заявленноеa, упомянутоеb, сказанноеc) — любое математическое высказывание=\left\{\begin{array}{rl}-1 &\mbox{, в котором естьif}\ (c - a)\times(b - a) < 0\\0 &\mbox{, по меньшей мереif}\ (c - a)\times(b - a) = 0\\1 &\mbox{, одна переменнаяif}\ (c - a)\times(b - a) > 0\end{array}\right.$$</tex>

Распишем подробнее:<tex dpi =120>(c - a)\times(b - a) = Примеры (c_x - a_x)(b_y - a_y) - (c_y - a_y)(b_x - a_x) =V</tex> Какие при этом у нас будут погрешности? Допустим, что все числа положительные и будем писать без модулей: '''Замечание:''' при сложении складываются абсолютные погрешности, при умножении складываются относительные погрешности. <tex dpi ="150"> \delta (c - a)\times(b - a) = A \varepsilon \left(\frac{(c_x + a_x)}{(c_x \cdot a_x)} + \frac{(b_y + a_y)}{(b_y \cdot a_y)}\right) + B \varepsilon \left(\frac{(c_y + a_y)}{(c_y \cdot a_y)} + \frac{(b_x + a_x)}{(b_x \cdot a_x)}\right)</tex> Именно поэтому, когда угол между отрезками АВ и АС ''крайне мал'', мы можем получить неверное значение предиката. [[Файл:Tiny_angle.jpg]] Заметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Распишем вещественное исчисление: <tex dpi = 140>V = (c - a)\times(b - a) \approx (c_x \ominus a_x)\otimes(b_y \ominus a_y) \ominus (c_y \ominus a_y)\otimes(b_x \ominus a_x) =</tex> <tex dpi = 130>= \big((c_x - a_x)(b_y - a_y)(1 + \delta_1)(1 + \delta_2)(1 + \delta_3)\ -</tex>

<tex dpi = 130>-\ (c_y - Например, обозначим предикатом EQa_y)(b_x - a_x)(1 + \delta_4)(x, y1 + \delta_5) отношение равенства («x 1 + \delta_6)\big)(1 + \delta_7) = y»), где ''x'' и ''y'' принадлежат множеству вещественных чисел. В этом случае предикат EQ будет принимать истинное значение для всех равных x и y.\tilde{V}</tex>

<tex dpi = 130>\mid\delta_i\mid \le \varepsilon_m = 2^{- Более житейским примером может служить предикат ПРОЖИВАЕТ(x, y, z) для отношения «x проживает в городе y на улице z» или ЛЮБИТ(x, y) для «x любит y», где множество ''M'' — это множество всех людей.54}</tex>;

Итак, у нас есть задача, с чего начнем её решать? Одно из решений - определить, лежат ли точки концов отрезков по разные стороны от другого отрезка'''Замечание:''' расписанное неравенство смотрите в [[Представление_чисел_с_плавающей_точкой#.D0.A0.D0.B0.D1.81.D1.87.D0. Вот тут нам и поможет предикатB5. Два из трех аргументов это точки концов одного отрезка, а последний - один из концов другого отрезкаD1.82|''другом конспекте'']]{{Определение|definition =Bounding box=Left_Turn(aЕщё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, bкогда вышеописанные проверки ничего не дадут — случай, c) = trueкогда оба отрезка лежат на одной прямой. Этот случай рассматривается отдельно. Для этого достаточно проверить, если что проекции этих двух отрезков на оси X и Y пересекаются (b - aчасто эту проверку называют ''проверкой на bounding box'')*(c - a) > 0}}. Но отметим, что чаще всего данный предикат используют для трех точек, где одна из них относится сразу к двум отрезкам.

Единственное, на что следует обратить внимание — граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай надо рассмотреть отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются [[Файл:Bounting_box(часто эту проверку называют "проверкой на bounding box").png]]== Ссылки ==[[Файл:Bounting_box_.png]]

* [http[Категория://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%B4%D0%B8%D0%BA%D0%B0%D1%82 wikipedia.ru - ПредикатВычислительная геометрия]* [http://e-maxx.ru/algo/segments_intersection_checking e-maxx.ru/algo - Проверка двух отрезков на пересечение]