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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Bounding box)
Строка 1: Строка 1:
Даны два отрезка AB и CD (они могут вырождаться в точки). Требуется проверить, пересекаются они на плоскости или нет. Для упрощения определения этого факта в вычислительной геометрии используется предикат "левый поворот" (или "по часовой стрелке").
+
Даны два отрезка, которые задаются начальной и конечной точками <tex>a,b\ \mathcal{2}\ R^2</tex> и определяются как множества точек <tex>s\ =\ \{(1-t)a + tb,\ t\ \mathcal{2}\ [0;1]\}</tex>. Требуется проверить существование множества их общих точек. Для определения этого факта в вычислительной геометрии используется предикат "левый поворот" (или "по часовой стрелке").
 
Рассмотрим возможные расположения точек и самих отрезков относительно друг друга:
 
Рассмотрим возможные расположения точек и самих отрезков относительно друг друга:
  
Строка 6: Строка 6:
 
[[Файл:Touch.jpg]]
 
[[Файл:Touch.jpg]]
  
Одно из решений - определить, лежат ли точки концов отрезков по разные стороны от другого отрезка.
+
Определим, лежат ли точки концов отрезков по разные стороны от другого отрезка.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 22: Строка 22:
 
}}
 
}}
 
Распишем подробнее:
 
Распишем подробнее:
<tex>(b - a)\times(c - a) = (b_x - a_x)\cdot(c_y - a_y) - (b_y - a_y)\cdot(c_x - a_x) = A - B</tex>
+
<tex dpi = 130>(b - a)\times(c - a) = (b_x - a_x)\cdot(c_y - a_y) - (b_y - a_y)\cdot(c_x - a_x) = A - B</tex>
  
 
Какие при этом у нас будут погрешности?  
 
Какие при этом у нас будут погрешности?  
Строка 33: Строка 33:
 
Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Точно определить знак нашего выражения поможет вычисление с [[Интервальная арифметика |"интервальной арифметикой"]]. Все исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут  неизвестны, но они обязательно будет содержаться в посчитанных интервалах.
 
Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Точно определить знак нашего выражения поможет вычисление с [[Интервальная арифметика |"интервальной арифметикой"]]. Все исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут  неизвестны, но они обязательно будет содержаться в посчитанных интервалах.
  
TODO: тут еще чего-то написать...
+
<tex dpi = 140>\overbrace {(b - a)\times(c - a)}^{v} \approx \overbrace{(b_x \ominus a_x)\otimes(c_y \ominus a_y) \ominus (b_y \ominus a_y)\otimes(c_x \ominus a_x)}^{\tilde{v}} =</tex>
 +
 
 +
<tex dpi = 130>= \big((b_x - a_x)(c_y - a_y)(1 + \delta_1)(1 + \delta_2)(1 + \delta_3)\ -</tex>
 +
 
 +
<tex dpi = 130>-\ (b_y - a_y)(c_x - a_x)(1 + \delta_4)(1 + \delta_5)(1 + \delta_6)\big)(1 + \delta_7)</tex>
 +
 
 +
<tex dpi = 130>\mid\delta_i\mid \le \epsilon</tex>;
  
 
Посмотрим внимательнее на наш предикат. Ошибка раскрывается тогда, когда угол между отрезками АВ и АС крайне мал.
 
Посмотрим внимательнее на наш предикат. Ошибка раскрывается тогда, когда угол между отрезками АВ и АС крайне мал.

Версия 03:09, 2 ноября 2011

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

Cross.png Two segments.png Touch.jpg

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

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

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

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

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

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

Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Точно определить знак нашего выражения поможет вычисление с "интервальной арифметикой". Все исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах.

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

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

[math]-\ (b_y - a_y)(c_x - a_x)(1 + \delta_4)(1 + \delta_5)(1 + \delta_6)\big)(1 + \delta_7)[/math]

[math]\mid\delta_i\mid \le \epsilon[/math];

Посмотрим внимательнее на наш предикат. Ошибка раскрывается тогда, когда угол между отрезками АВ и АС крайне мал.

Tiny angle.jpg

Bounding box

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

Bounting box().png Bounting box .png

Псевдокод:

boolean Bounding_Box(точка A, точка B, точка C)
if (((A.xx >= C.xx && C.xx >= B.xx) || (A.xx <= C.xx && C.xx <= B.xx))
 && ((A.yy >= C.yy && C.yy >= B.yy) || (A.yy <= C.yy && C.yy <= B.yy)))
	вернуть true
вернуть false

или

boolean Bounding_Box(точка A, точка B, точка C, точка D)
if (((A.xx > C.xx && A.xx > D.xx && B.xx > C.xx && B.xx > D.xx) || (A.xx < C.xx && A.xx < D.xx && B.xx < C.xx && B.xx < D.xx)) 
 || ((A.yy > C.yy && A.yy > D.yy && B.yy > C.yy && B.yy > D.yy) || (A.yy < C.yy && A.yy < D.yy && B.yy < C.yy && B.yy < D.yy)))
	return false;
return true;