Предикат "левый поворот" — различия между версиями
| Строка 1: | Строка 1: | ||
| − | |||
Допустим нам дана задача: Даны два отрезка AB и CD (они могут вырождаться в точки). Требуется проверить, пересекаются они на плоскости или нет. Для упрощения определения этого факта в вычислительной геометрии используется предикат "левый поворот" (или "по часовой стрелке"). | Допустим нам дана задача: Даны два отрезка AB и CD (они могут вырождаться в точки). Требуется проверить, пересекаются они на плоскости или нет. Для упрощения определения этого факта в вычислительной геометрии используется предикат "левый поворот" (или "по часовой стрелке"). | ||
| − | |||
Итак, у нас есть задача, с чего начнем её решать? Какие вообще могут быть расположения точек и самих отрезков относительно друг друга? | Итак, у нас есть задача, с чего начнем её решать? Какие вообще могут быть расположения точек и самих отрезков относительно друг друга? | ||
| Строка 11: | Строка 9: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | Left_Turn(a, b, c) = true, если <tex>(b - a) | + | Left_Turn(a, b, c) = true, если <tex>(b - a)\times(c - a) > 0</tex> |
}} | }} | ||
Распишем поподробнее: | Распишем поподробнее: | ||
| − | <tex>(b - a) | + | <tex>(b - a)\times(c - a) = (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x) = A - B</tex> |
Какие при этом у нас будут погрешности? | Какие при этом у нас будут погрешности? | ||
| + | Нам нужно точно определить знак нашего выражения. Будем использовать для его вычисления [[Интервальная арифметика |"интервальную арифметику"]]. Все исходные переменные, входящие в него, будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам неизвестны, но они обязательно будет содержаться в посчитанных интервалах. | ||
| + | Допустим, что все числа положительные и будем писать без модулей: | ||
NB: при сложении складываются абс. погрешности,при умножении складываются отн. погрешности. | NB: при сложении складываются абс. погрешности,при умножении складываются отн. погрешности. | ||
| − | <tex>\delta (b - a) | + | <tex dpi = "150"> \delta (b - a)\times(c - a) = A \cdot \epsilon \cdot (\frac{(b_x + a_x)}{(b_x \cdot a_x)} + \frac{(c_y + a_y)}{(c_y \cdot a_y)}) + B \cdot \epsilon \cdot (\frac{(b_y + a_y)}{(b_y \cdot a_y)} + \frac{(c_x + a_x)}{(c_x \cdot a_x)})</tex> |
| − | |||
| − | |||
Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Какую? Посмотрим внимательнее на наш предикат. Ошибка раскрывается тогда, когда угол между отрезками АВ и АС крайне мал. | Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Какую? Посмотрим внимательнее на наш предикат. Ошибка раскрывается тогда, когда угол между отрезками АВ и АС крайне мал. | ||
Версия 20:23, 19 октября 2011
Допустим нам дана задача: Даны два отрезка AB и CD (они могут вырождаться в точки). Требуется проверить, пересекаются они на плоскости или нет. Для упрощения определения этого факта в вычислительной геометрии используется предикат "левый поворот" (или "по часовой стрелке"). Итак, у нас есть задача, с чего начнем её решать? Какие вообще могут быть расположения точек и самих отрезков относительно друг друга?
Одно из решений - определить, лежат ли точки концов отрезков по разные стороны от другого отрезка. Вот тут нам и поможет наш предикат, где два из трех аргументов (например a и b) это точки концов одного отрезка, а последний - один из концов другого отрезка.
| Определение: |
| Left_Turn(a, b, c) = true, если |
Распишем поподробнее:
Какие при этом у нас будут погрешности? Нам нужно точно определить знак нашего выражения. Будем использовать для его вычисления "интервальную арифметику". Все исходные переменные, входящие в него, будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам неизвестны, но они обязательно будет содержаться в посчитанных интервалах. Допустим, что все числа положительные и будем писать без модулей:
NB: при сложении складываются абс. погрешности,при умножении складываются отн. погрешности.
Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Какую? Посмотрим внимательнее на наш предикат. Ошибка раскрывается тогда, когда угол между отрезками АВ и АС крайне мал.
Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай надо рассмотреть отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют "проверкой на bounding box").
.png)
