Предикат "левый поворот" — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 3 промежуточные версии 3 участников) | |||
Строка 37: | Строка 37: | ||
Заметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Распишем вещественное исчисление: | Заметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Распишем вещественное исчисление: | ||
− | <tex dpi = 140> | + | <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>= \big((c_x - a_x)(b_y - a_y)(1 + \delta_1)(1 + \delta_2)(1 + \delta_3)\ -</tex> | ||
Строка 45: | Строка 45: | ||
<tex dpi = 130>\mid\delta_i\mid \le \varepsilon_m = 2^{-54}</tex>; | <tex dpi = 130>\mid\delta_i\mid \le \varepsilon_m = 2^{-54}</tex>; | ||
− | Получим некую окрестность <tex dpi = 130>|V - \tilde{V}|</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= | =Bounding box= | ||
− | Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай рассматривается отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют ''проверкой на 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). Но отметим, что чаще всего данный предикат используют для трех точек, где одна из них относится сразу к двум отрезкам.