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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры)
(Bounding box)
(не показано 28 промежуточных версий 7 участников)
Строка 1: Строка 1:
{{В разработке}}
+
Даны два отрезка, которые задаются начальной и конечной точками <tex>a,b\ \mathcal{2}\ \mathbb R^2</tex> и определяются как множества точек <tex>s\ =\ \{(1-t)a + tb,\ t\ \in [0;1]\}</tex>. Требуется проверить существование множества их общих точек. Для определения этого факта в вычислительной геометрии используется предикат ''левый поворот'' (или ''по часовой стрелке'').
Допустим нам дана задача: Даны два отрезка AB и CD (они могут вырождаться в точки). Требуется проверить, пересекаются они на плоскости или нет. Для упрощения определения этого факта в вычислительной геометрии используется предикат "левый поворот" (или "по часовой стрелке"). Для начала разберемся, что за зверь такой - Предикат.
+
Рассмотрим возможные расположения точек и самих отрезков относительно друг друга:
 +
 
 +
[[Файл:Cross.png]]
 +
[[Файл:Two_segments.png]]
 +
[[Файл:Touch.jpg]]
 +
 
 +
Определим, лежат ли точки концов отрезков по разные стороны от другого отрезка.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Предикат''' (лат. '''praedicatum''' — заявленное, упомянутое, сказанное) — любое математическое высказывание, в котором есть, по меньшей мере, одна переменная
+
<tex dpi = "120">
 +
$$
 +
\operatorname{LeftTurn}(a, b, c) =\left\{
 +
\begin{array}{rl}
 +
-1 &\mbox{, if}\ (c - a)\times(b - a) < 0\\
 +
0 &\mbox{, if}\ (c - a)\times(b - a) = 0\\
 +
1 &\mbox{, if}\ (c - a)\times(b - a) > 0
 +
\end{array}
 +
\right.
 +
$$
 +
</tex>
 
}}
 
}}
== Примеры ==
+
Распишем подробнее:
 +
<tex dpi = 120>(c - a)\times(b - a) = (c_x - a_x)(b_y - a_y) - (c_y - a_y)(b_x - a_x) = V</tex>
 +
 
 +
Какие при этом у нас будут погрешности?
 +
Допустим, что все числа положительные и будем писать без модулей:
 +
 
 +
'''Замечание:''' при сложении складываются абсолютные погрешности, при умножении складываются относительные погрешности.
 +
 
 +
<tex dpi = "150"> \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)</tex>
  
- Например, обозначим предикатом EQ(x, y) отношение равенства («x = y»), где ''x'' и ''y'' принадлежат множеству вещественных чисел. В этом случае предикат EQ будет принимать истинное значение для всех равных x и y.
+
Именно поэтому, когда угол между отрезками АВ и АС ''крайне мал'', мы можем получить неверное значение предиката.
  
- Более житейским примером может служить предикат ПРОЖИВАЕТ(x, y, z) для отношения «x проживает в городе y на улице z» или ЛЮБИТ(x, y) для «x любит y».
+
[[Файл:Tiny_angle.jpg]]
  
 +
Заметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Распишем вещественное исчисление:
  
Итак, у нас есть задача, с чего начнем её решать? Какие вообще могут быть расположения точек и самих отрезков относительно друг друга?
+
<tex dpi = 140>V = (c - a)\times(b - a) \approx (c_x \ominus a_x)\otimes(b_y \ominus a_y) \ominus (c_y \ominus a_y)\otimes(b_x \ominus a_x) =</tex>
  
[[Файл:Cross.png]]
+
<tex dpi = 130>= \big((c_x - a_x)(b_y - a_y)(1 + \delta_1)(1 + \delta_2)(1 + \delta_3)\ -</tex>
[[Файл:Two_segments.png]]
 
[[Файл:Touch.jpg]]
 
  
Одно из решений - определить, лежат ли точки концов отрезков по разные стороны от другого отрезка. Вот тут нам и поможет наш предикат, где два из трех аргументов (например a и b) это точки концов одного отрезка, а последний - один из концов другого отрезка.
+
<tex dpi = 130>-\ (c_y - a_y)(b_x - a_x)(1 + \delta_4)(1 + \delta_5)(1 + \delta_6)\big)(1 + \delta_7) = \tilde{V}</tex>
{{Определение
 
|definition =
 
Left_Turn(a, b, c) = true, если (b - a)*(c - a) > 0
 
}}
 
  
Заметим, что все координаты (а значит и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Какую? Посмотрим внимательнее на наш предикат. Ошибка раскрывается тогда, когда угол между отрезками АВ и АС крайне мал.
+
<tex dpi = 130>\mid\delta_i\mid \le \varepsilon_m = 2^{-54}</tex>;
  
[[Файл:Tiny_angle.jpg]]
+
Получим некую окрестность <tex dpi = 130>|V - \tilde{V}| \le 8 \varepsilon_m</tex>, если ноль попадает в наш интервал, то приходится пользоваться более тяжелой артиллерией, такими как [[Adaptive precision arithmetic|''adaptive precision arithmetic'']], либо [[Интервальная арифметика |''интервальная арифметика'']]. Во второй, исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах.
  
Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай надо рассмотреть отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют "проверкой на bounding box").
+
'''Замечание:''' расписанное неравенство смотрите в [[Представление_чисел_с_плавающей_точкой#.D0.A0.D0.B0.D1.81.D1.87.D0.B5.D1.82|''другом конспекте'']]
  
[[Файл:Bounting_box.png]]
+
=Bounding box=
[[Файл:Bounting_box.png_]]
+
Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай рассматривается отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют ''проверкой на bounding box''). Но отметим, что чаще всего данный предикат используют для трех точек, где одна из них относится сразу к двум отрезкам.
  
== Ссылки ==
+
[[Файл:Bounting_box().png]]
 +
[[Файл:Bounting_box_.png]]
  
* [http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%B4%D0%B8%D0%BA%D0%B0%D1%82 wikipedia.ru - Предикат]
+
[[Категория: Вычислительная геометрия]]
* [http://e-maxx.ru/algo/segments_intersection_checking e-maxx.ru/algo - Проверка двух отрезков на пересечение]
 

Версия 11:28, 18 июня 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]V = (c - a)\times(b - a) \approx (c_x \ominus a_x)\otimes(b_y \ominus a_y) \ominus (c_y \ominus a_y)\otimes(b_x \ominus a_x) =[/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}| \le 8 \varepsilon_m[/math], если ноль попадает в наш интервал, то приходится пользоваться более тяжелой артиллерией, такими как adaptive precision arithmetic, либо интервальная арифметика. Во второй, исходные переменные будут вырожденными интервалами. Из-за погрешностей, возникающих при округлении вещественных чисел, истинные значения операций нам будут неизвестны, но они обязательно будет содержаться в посчитанных интервалах.

Замечание: расписанное неравенство смотрите в другом конспекте

Bounding box

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

Bounting box().png Bounting box .png