Предикат "левый поворот" — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 35: Строка 35:
 
[[Файл:Tiny_angle.jpg]]
 
[[Файл:Tiny_angle.jpg]]
  
Заметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Более точно, определить знак нашего выражения поможет вычисление с [[Интервальная арифметика |''интервальной арифметикой'']]. Все исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут  неизвестны, но они обязательно будет содержаться в посчитанных интервалах. Для точного вычисления необходимо фильтрованное вычисление предикатов.
+
Заметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Распишем вещественное исчисление:
 
 
Распишем вещественное исчисление:
 
  
 
<tex dpi = 140>\overbrace {(c - a)\times(b - a)}^{V} = \overbrace{(c_x \ominus a_x)\otimes(b_y \ominus a_y) \ominus (c_y \ominus a_y)\otimes(b_x \ominus a_x)}^{\tilde{V}} =</tex>
 
<tex dpi = 140>\overbrace {(c - a)\times(b - a)}^{V} = \overbrace{(c_x \ominus a_x)\otimes(b_y \ominus a_y) \ominus (c_y \ominus a_y)\otimes(b_x \ominus a_x)}^{\tilde{V}} =</tex>
Строка 61: Строка 59:
 
Далее для пущей точности добавим floating point ariphmetics:
 
Далее для пущей точности добавим floating point ariphmetics:
  
 +
<tex dpi = 130>((1 + \varepsilon_m)^4 - 1) \cdot |(c_x \ominus a_x)\otimes(b_y \ominus a_y) \oplus (c_y \ominus a_y)\otimes(b_x \ominus a_x)| =</tex>
 +
 +
<tex dpi = 130>= \frac{(1 + \varepsilon_m)^4 - 1}{(1 + \varepsilon_m)^3} \cdot |(c_x - a_x)(b_y - a_y) \oplus (c_y - a_y)(b_x - a_x)| =</tex>
 +
 +
<tex dpi = 130>= \frac{(1 + \varepsilon_m)^4 - 1}{(1 + \varepsilon_m)^4} \cdot |(c_x - a_x)(b_y - a_y) + (c_y - a_y)(b_x - a_x)| </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>1 - 4 \varepsilon_m \le frac{5}{8}</tex>
  
 +
Таким образом мы получили радиус нашей окрестности <tex dpi = 130>|V - \tilde{V}|</tex>, если же ноль таки попал в наш интервал, то приходится пользоваться более тяжелой артиллерией, такими как [[Adaptive precision arithmetic|''adaptive precision arithmetic'']], либо [[Интервальная арифметика |''интервальная арифметика'']]. Во второй, исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах.
  
 
=Bounding box=
 
=Bounding box=
Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай надо рассмотреть отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют ''проверкой на bounding box'').
+
Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай рассматривается отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют ''проверкой на bounding box'').
  
 
[[Файл:Bounting_box().png]]
 
[[Файл:Bounting_box().png]]

Версия 01:33, 8 апреля 2012

Даны два отрезка, которые задаются начальной и конечной точками [math]a,b\ \mathcal{2}\ \mathbb R^2[/math] и определяются как множества точек [math]s\ =\ \{(1-t)a + tb,\ t\ \in [0;1]\}[/math]. Требуется проверить существование множества их общих точек. Для определения этого факта в вычислительной геометрии используется предикат левый поворот (или по часовой стрелке). Рассмотрим возможные расположения точек и самих отрезков относительно друг друга:

Cross.png Two segments.png Touch.jpg

Определим, лежат ли точки концов отрезков по разные стороны от другого отрезка.

Определение:
[math] $$ \operatorname{LeftTurn}(a, b, c) =\left\{ \begin{array}{rl} -1 &\mbox{, if}\ (c - a)\times(b - a) \lt 0\\ 0 &\mbox{, if}\ (c - a)\times(b - a) = 0\\ 1 &\mbox{, if}\ (c - a)\times(b - a) \gt 0 \end{array} \right. $$ [/math]

Распишем подробнее: [math](c - a)\times(b - a) = (c_x - a_x)(b_y - a_y) - (c_y - a_y)(b_x - a_x) = V[/math]

Какие при этом у нас будут погрешности? Допустим, что все числа положительные и будем писать без модулей:

Замечание: при сложении складываются абсолютные погрешности, при умножении складываются относительные погрешности.

[math] \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)[/math]

Именно поэтому, когда угол между отрезками АВ и АС крайне мал, мы можем получить неверное значение предиката.

Tiny angle.jpg

Заметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Распишем вещественное исчисление:

[math]\overbrace {(c - a)\times(b - a)}^{V} = \overbrace{(c_x \ominus a_x)\otimes(b_y \ominus a_y) \ominus (c_y \ominus a_y)\otimes(b_x \ominus a_x)}^{\tilde{V}} =[/math]

[math]= \big((c_x - a_x)(b_y - a_y)(1 + \delta_1)(1 + \delta_2)(1 + \delta_3)\ -[/math]

[math]-\ (c_y - a_y)(b_x - a_x)(1 + \delta_4)(1 + \delta_5)(1 + \delta_6)\big)(1 + \delta_7) = \tilde{V}[/math]

[math]\mid\delta_i\mid \le \varepsilon_m = 2^{-54}[/math];

Получим некую окрестность [math]|V - \tilde{V}|[/math] судя по которой мы сможем точнее определить, не ошиблись ли мы знаком(если ноль не входит в нашу окрестность, тогда знак верен, иначе "we need go deeper")

Найдем более точно нашу окрестность:

[math]|V - \tilde{V}| = |\big((1 + \delta_7)(1 + \delta_3)(1 + \delta_2)(1 + \delta_1) - 1 \big)(c_x - a_x)(b_y - a_y) -[/math]

[math]-\ \big((1 + \delta_7)(1 + \delta_6)(1 + \delta_5)(1 + \delta_4) - 1 \big)(c_y - a_y)(b_x - a_x)| \le [/math]

[math]\le |P(\delta_7, \delta_3, \delta_2, \delta_1)|\cdot|(c_x - a_x)(b_y - a_y)| + |Q(\delta_7, \delta_6, \delta_5, \delta_4)|\cdot|(c_y - a_y)(b_x - a_x)|\le[/math]

[math]\le ((1 + \varepsilon_m)^4 - 1) \cdot |(c_x - a_x)(b_y - a_y) + (c_y - a_y)(b_x - a_x)|[/math]

Далее для пущей точности добавим floating point ariphmetics:

[math]((1 + \varepsilon_m)^4 - 1) \cdot |(c_x \ominus a_x)\otimes(b_y \ominus a_y) \oplus (c_y \ominus a_y)\otimes(b_x \ominus a_x)| =[/math]

[math]= \frac{(1 + \varepsilon_m)^4 - 1}{(1 + \varepsilon_m)^3} \cdot |(c_x - a_x)(b_y - a_y) \oplus (c_y - a_y)(b_x - a_x)| =[/math]

[math]= \frac{(1 + \varepsilon_m)^4 - 1}{(1 + \varepsilon_m)^4} \cdot |(c_x - a_x)(b_y - a_y) + (c_y - a_y)(b_x - a_x)| [/math]

Замаксимизируем первый множитель:

[math] \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[/math]

[math]\le frac{5 \varepsilon_m}{1 - 4 \varepsilon_m} \le 8 \varepsilon_m[/math]

Замечание: последнее неравенство верно, т.к. [math]1 - 4 \varepsilon_m \le frac{5}{8}[/math]

Таким образом мы получили радиус нашей окрестности [math]|V - \tilde{V}|[/math], если же ноль таки попал в наш интервал, то приходится пользоваться более тяжелой артиллерией, такими как adaptive precision arithmetic, либо интервальная арифметика. Во второй, исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах.

Bounding box

Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай рассматривается отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют проверкой на bounding box).

Bounting box().png Bounting box .png