Предикат "левый поворот" — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
| (не показаны 2 промежуточные версии 2 участников) | |||
| Строка 50: | Строка 50: | ||
=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). Но отметим, что чаще всего данный предикат используют для трех точек, где одна из них относится сразу к двум отрезкам.
.png)
