Предикат "левый поворот" — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 44 промежуточные версии 8 участников) | |||
Строка 1: | Строка 1: | ||
− | + | Даны два отрезка, которые задаются начальной и конечной точками <tex>a,b\ \mathcal{2}\ \mathbb R^2</tex> и определяются как множества точек <tex>s\ =\ \{(1-t)a + tb,\ t\ \in [0;1]\}</tex>. Требуется проверить существование множества их общих точек. Для определения этого факта в вычислительной геометрии используется предикат ''левый поворот'' (или ''по часовой стрелке''). | |
− | + | Рассмотрим возможные расположения точек и самих отрезков относительно друг друга: | |
+ | |||
+ | [[Файл:Cross.png]] | ||
+ | [[Файл:Two_segments.png]] | ||
+ | [[Файл:Touch.jpg]] | ||
+ | |||
+ | Определим, лежат ли точки концов отрезков по разные стороны от другого отрезка. | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | + | <tex dpi = "120"> | |
+ | $$ | ||
+ | \operatorname{LeftTurn}(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 - a_y)(b_x - a_x)(1 + \delta_4)(1 + \delta_5)(1 + \delta_6)\big)(1 + \delta_7) = \tilde{V}</tex> | ||
+ | |||
+ | <tex dpi = 130>\mid\delta_i\mid \le \varepsilon_m = 2^{-54}</tex>; | ||
− | - | + | Получим некую окрестность <tex dpi = 130>|V - \tilde{V}| \le 8 \varepsilon_m</tex>, если ноль попадает в наш интервал, то приходится пользоваться более тяжелой артиллерией, такими как [[Adaptive precision arithmetic|''adaptive precision arithmetic'']], либо [[Интервальная арифметика |''интервальная арифметика'']]. Во второй, исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах. |
− | + | '''Замечание:''' расписанное неравенство смотрите в [[Представление_чисел_с_плавающей_точкой#.D0.A0.D0.B0.D1.81.D1.87.D0.B5.D1.82|''другом конспекте'']] | |
+ | =Bounding box= | ||
+ | Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай рассматривается отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют ''проверкой на bounding box''). Но отметим, что чаще всего данный предикат используют для трех точек, где одна из них относится сразу к двум отрезкам. | ||
− | + | [[Файл:Bounting_box().png]] | |
− | + | [[Файл:Bounting_box_.png]] | |
− | + | [[Категория: Вычислительная геометрия]] |
Текущая версия на 19:12, 4 сентября 2022
Даны два отрезка, которые задаются начальной и конечной точками
и определяются как множества точек . Требуется проверить существование множества их общих точек. Для определения этого факта в вычислительной геометрии используется предикат левый поворот (или по часовой стрелке). Рассмотрим возможные расположения точек и самих отрезков относительно друг друга:Определим, лежат ли точки концов отрезков по разные стороны от другого отрезка.
Определение: |
Распишем подробнее:
Какие при этом у нас будут погрешности? Допустим, что все числа положительные и будем писать без модулей:
Замечание: при сложении складываются абсолютные погрешности, при умножении складываются относительные погрешности.
Именно поэтому, когда угол между отрезками АВ и АС крайне мал, мы можем получить неверное значение предиката.
Заметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Распишем вещественное исчисление:
;
Получим некую окрестность adaptive precision arithmetic, либо интервальная арифметика. Во второй, исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах.
, если ноль попадает в наш интервал, то приходится пользоваться более тяжелой артиллерией, такими какЗамечание: расписанное неравенство смотрите в другом конспекте
Bounding box
Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай рассматривается отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют проверкой на bounding box). Но отметим, что чаще всего данный предикат используют для трех точек, где одна из них относится сразу к двум отрезкам.