Предикат "левый поворот" — различия между версиями
Строка 69: | Строка 69: | ||
<tex dpi = 130> \frac{(1 + \varepsilon_m)^4 - 1}{(1 + \varepsilon_m)^4} = \frac{4 \varepsilon_m - 6 \varepsilon^2_m + 4 \varepsilon^3_m + \varepsilon^4_m}{1 - 4 \varepsilon_m + 6 \varepsilon^2_m - 4 \varepsilon^3_m - \varepsilon^4_m} \le</tex> | <tex dpi = 130> \frac{(1 + \varepsilon_m)^4 - 1}{(1 + \varepsilon_m)^4} = \frac{4 \varepsilon_m - 6 \varepsilon^2_m + 4 \varepsilon^3_m + \varepsilon^4_m}{1 - 4 \varepsilon_m + 6 \varepsilon^2_m - 4 \varepsilon^3_m - \varepsilon^4_m} \le</tex> | ||
− | <tex dpi = 130>\le frac{5 \varepsilon_m}{1 - 4 \varepsilon_m} \le 8 \varepsilon_m</tex> | + | <tex dpi = 130>\le \frac{5 \varepsilon_m}{1 - 4 \varepsilon_m} \le 8 \varepsilon_m</tex> |
− | '''Замечание:''' последнее неравенство верно, т.к. <tex dpi = 130>1 - 4 \varepsilon_m \le frac{5}{8}</tex> | + | '''Замечание:''' последнее неравенство верно, т.к. <tex dpi = 130>1 - 4 \varepsilon_m \le \frac{5}{8}</tex> |
Таким образом мы получили радиус нашей окрестности <tex dpi = 130>|V - \tilde{V}|</tex>, если же ноль таки попал в наш интервал, то приходится пользоваться более тяжелой артиллерией, такими как [[Adaptive precision arithmetic|''adaptive precision arithmetic'']], либо [[Интервальная арифметика |''интервальная арифметика'']]. Во второй, исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах. | Таким образом мы получили радиус нашей окрестности <tex dpi = 130>|V - \tilde{V}|</tex>, если же ноль таки попал в наш интервал, то приходится пользоваться более тяжелой артиллерией, такими как [[Adaptive precision arithmetic|''adaptive precision arithmetic'']], либо [[Интервальная арифметика |''интервальная арифметика'']]. Во второй, исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах. |
Версия 01:34, 8 апреля 2012
Даны два отрезка, которые задаются начальной и конечной точками
и определяются как множества точек . Требуется проверить существование множества их общих точек. Для определения этого факта в вычислительной геометрии используется предикат левый поворот (или по часовой стрелке). Рассмотрим возможные расположения точек и самих отрезков относительно друг друга:Определим, лежат ли точки концов отрезков по разные стороны от другого отрезка.
Определение: |
Распишем подробнее:
Какие при этом у нас будут погрешности? Допустим, что все числа положительные и будем писать без модулей:
Замечание: при сложении складываются абсолютные погрешности, при умножении складываются относительные погрешности.
Именно поэтому, когда угол между отрезками АВ и АС крайне мал, мы можем получить неверное значение предиката.
Заметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Распишем вещественное исчисление:
;
Получим некую окрестность
судя по которой мы сможем точнее определить, не ошиблись ли мы знаком(если ноль не входит в нашу окрестность, тогда знак верен, иначе "we need go deeper")Найдем более точно нашу окрестность:
Далее для пущей точности добавим floating point ariphmetics:
Замаксимизируем первый множитель:
Замечание: последнее неравенство верно, т.к.
Таким образом мы получили радиус нашей окрестности adaptive precision arithmetic, либо интервальная арифметика. Во второй, исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах.
, если же ноль таки попал в наш интервал, то приходится пользоваться более тяжелой артиллерией, такими какBounding box
Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай рассматривается отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют проверкой на bounding box).