189
правок
Изменения
→Bounding box
Даны два отрезка, которые задаются начальной и конечной точками <tex>a,b\ \mathcal{2}\ \mathbb R^2</tex> и определяются как множества точек <tex>s\ =\ \{(1-t)a + tb,\ t\ \mathcal{2}\ in [0;1]\}</tex>. Требуется проверить существование множества их общих точек. Для определения этого факта в вычислительной геометрии используется предикат "''левый поворот" '' (или "''по часовой стрелке"'').
Рассмотрим возможные расположения точек и самих отрезков относительно друг друга:
<tex dpi = "120">
$$
\begin{array}{rl}
-1 &\mbox{, forif}\ (b c - a)\times(c b - a) < 0\\0 &\mbox{, forif}\ (b c - a)\times(c b - a) = 0\\1 &\mbox{, forif}\ (b c - a)\times(c b - a) > 0
\end{array}
\right.
}}
Распишем подробнее:
<tex dpi = 130120>(b c - a)\times(c b - a) = (b_x c_x - a_x)\cdot(c_y b_y - a_y) - (b_y c_y - a_y)\cdot(c_x b_x - a_x) = A - BV</tex>
Какие при этом у нас будут погрешности?
Допустим, что все числа положительные и будем писать без модулей:
<tex dpi = "150"> \delta (b c - a)\times(c b - a) = A \cdot varepsilon \epsilon \cdot left(\frac{(b_x c_x + a_x)}{(b_x c_x \cdot a_x)} + \frac{(c_y b_y + a_y)}{(c_y b_y \cdot a_y)}\right) + B \cdot \epsilon varepsilon \cdot left(\frac{(b_y c_y + a_y)}{(b_y c_y \cdot a_y)} + \frac{(c_x b_x + a_x)}{(c_x b_x \cdot a_x)}\right)</tex>
[[Файл:Tiny_angle.jpg]] Заметим, что все координаты (а, значит, и наши вычисления) производятся в вещественных числах, а это значит, что при вычислениях мы можем допустить ошибку. Распишем вещественное исчисление: <tex dpi = 140>\overbrace {V = (b c - a)\times(c b - a)}^{v} \approx \overbrace{(b_x c_x \ominus a_x)\otimes(c_y b_y \ominus a_y) \ominus (b_y c_y \ominus a_y)\otimes(c_x b_x \ominus a_x)}^{\tilde{v}} =</tex>
<tex dpi = 130>= \big((b_x c_x - a_x)(c_y b_y - a_y)(1 + \delta_1)(1 + \delta_2)(1 + \delta_3)\ -</tex>
<tex dpi = 130>-\ (b_y c_y - a_y)(c_x b_x - a_x)(1 + \delta_4)(1 + \delta_5)(1 + \delta_6)\big)(1 + \delta_7)= \tilde{V}</tex>
<tex dpi = 130>\mid\delta_i\mid \le \epsilonvarepsilon_m = 2^{-54}</tex>;
'''Замечание:''' расписанное неравенство смотрите в [[Файл:Tiny_angleПредставление_чисел_с_плавающей_точкой#.D0.A0.D0.B0.D1.81.D1.87.D0.B5.D1.jpg82|''другом конспекте'']]
=Bounding box=
Ещё следует обратить внимание на граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай надо рассмотреть рассматривается отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси X и Y пересекаются (часто эту проверку называют "''проверкой на bounding box"''). Но отметим, что чаще всего данный предикат используют для трех точек, где одна из них относится сразу к двум отрезкам.
[[Файл:Bounting_box().png]]
[[Файл:Bounting_box_.png]]