Просмотр исходного текста страницы Погрешность предиката левый поворот

{{в разработке}}
Пусть две точки <tex>a(a_x, a_y), b(b_x, b_y)</tex> заданы абсолютно точно, а точка <tex> c </tex> задана как точка внешнего касания двух окружностей <tex>(o_1(x_1, y_1), r_1)</tex> и <tex>(o_2(x_2, y_2), r_2).</tex>

<tex>\overrightarrow{o_1c} = \frac{r_1}{r_1 + r_2} \cdot \overrightarrow{o_1o_2}, \\
\overrightarrow{o_1o_2} = (x_2 - x_1, y_2 - y_1) \\
c_x = \frac{r_1}{r_1 + r_2} \cdot (x_2 - x_1) + x_1 = \frac{r_1}{r_1 + r_2} \cdot x_2 + \frac{r_2}{r_1 + r_2} \cdot x_1\\
c_y = \frac{r_1}{r_1 + r_2} \cdot (y_2 - y_1) + y_1 = \frac{r_1}{r_1 + r_2} \cdot y_2 + \frac{r_2}{r_1 + r_2} \cdot y_1</tex>

Обозначим 

<tex> v = (b - a) \times (c - a) = \\
= (b_x - a_x) (\frac{r_1}{r_1 + r_2} \cdot y_2 + \frac{r_2}{r_1 + r_2} \cdot y_1 - a_y) - \\
- (b_y - a_y) (\frac{r_1}{r_1 + r_2} \cdot x_2 + \frac{r_2}{r_1 + r_2} \cdot x_1 - a_x) = \\</tex>

<tex dpi = 140> = \frac{(b_x - a_x) (r_1 y_2 + r_2 y_1 - a_y (r_1 + r_2)) - (b_y - a_y) (r_1 x_2 + r_2 x_1 - a_x (r_1 + r_2))}{r_1 + r_2}</tex>. 

Так как <tex> r_1 + r_2 > 0, </tex> то мы можем оценивать знак выражения <tex>k = v \cdot (r_1 + r_2)</tex>

<tex>k = (b_x - a_x) (r_1 (y_2 - a_y) + r_2 (y_1 - a_y)) - (b_y - a_y) (r_1 (x_2 - a_x) + r_2 (x_1 - a_x)) = \\
= (b_x - a_x) r_1 (y_2 - a_y) + (b_x - a_x) r_2 (y_1 - a_y) - \\
- (b_y - a_y) r_1 (x_2 - a_x) - (b_y - a_y) r_2 (x_1 - a_x)</tex>

Теперь распишем это выражение в дабловой арифметике. 
Для сокращения обозначим произведение <tex>(1 + \delta_{p_1}) \cdot (1 + \delta_{p_2}) \cdot \ldots \cdot (1 + \delta_{p_n})</tex> за 
<tex>F(p_1, p_2, \ldots , p_n)</tex>

<tex>\tilde{k} = (b_x \ominus a_x) \otimes (r_1 \otimes (y_2 \ominus a_y) \oplus r_2 \otimes (y_1 \ominus a_y)) \ominus \\ 
         \ominus (b_y \ominus a_y) \otimes (r_1 \otimes (x_2 \ominus a_x) \oplus r_2 \otimes (x_1 \ominus a_x)) = \\
= [(b_x - a_x) (r_1 (y_2 - a_y)F(1, 2) + r_2 (y_1 - a_y)F(3, 4))F(5, 6, 7) - \\
- (b_y - a_y) (r_1 (x_2 - a_x)F(8, 9) + r_2 (x_1 - a_x)F(10, 11))F(12, 13, 14)]F(15) = \\
= (b_x - a_x) r_1 (y_2 - a_y)F(1, 2, 5, 6, 7, 15) + \\
+ (b_x - a_x) r_2 (y_1 - a_y)F(3, 4, 5, 6, 7, 15) - \\
- (b_y - a_y) r_1 (x_2 - a_x)F(8, 9, 12, 13, 14, 15) - \\
- (b_y - a_y) r_2 (x_1 - a_x)F(10, 11, 12, 13, 14, 15)
</tex>


<tex> |\delta_i| \leq \varepsilon_m </tex>

Заметим, что <tex> k\approx \tilde{k} </tex>

Теперь оценим абсолютную погрешность <tex> \epsilon = |k - \tilde{k}|. </tex> 

<tex> |k - \tilde{k}| = \\
=|r_1(b_x - a_x)(y_2 - a_y) + \\
+ r_2(b_x - a_x)(y_1 - a_y) - \\
- r_1(b_y - a_y)(x_2 - a_x) - \\
- r_2(b_y - a_y)(x_1 - a_x) - \\
- r_1(b_x - a_x)(y_2 - a_y) \cdot F(1, 2, 5, 6, 7, 15) - \\
- r_2(b_x - a_x)(y_1 - a_y) \cdot F(3, 4, 5, 6, 7, 15) + \\
+ r_1(b_y - a_y)(x_2 - a_x) \cdot F(8, 9, 12, 13, 14, 15) + \\
+ r_2(b_y - a_y)(x_1 - a_x) \cdot F(10, 11, 12, 13, 14, 15)| = \\
= |r_1(b_x - a_x)(y_2 - a_y) \cdot (F(1, 2, 5, 6, 7, 15) - 1) - \\
- r_2(b_x - a_x)(y_1 - a_y) \cdot (F(3, 4, 5, 6, 7, 15) - 1) + \\
+ r_1(b_y - a_y)(x_2 - a_x) \cdot (F(8, 9, 12, 13, 14, 15) - 1) + \\
+ r_2(b_y - a_y)(x_1 - a_x) \cdot (F(10, 11, 12, 13, 14, 15) - 1)| \leq \\
\leq |r_1(b_x - a_x)(y_2 - a_y)| \cdot |(F(1, 2, 5, 6, 7, 15) - 1)| + \\
+ |r_2(b_x - a_x)(y_1 - a_y)| \cdot |(F(3, 4, 5, 6, 7, 15) - 1)| + \\
+ |r_1(b_y - a_y)(x_2 - a_x)| \cdot |(F(8, 9, 12, 13, 14, 15) - 1)| + \\
+ |r_2(b_y - a_y)(x_1 - a_x)| \cdot |(F(10, 11, 12, 13, 14, 15) - 1)|</tex>

Теперь раскрываем скобки во всех <tex>F</tex>, сокращаем единицы. Пользуемся свойством, что <tex>|\sum{p_i}| \leq \sum{|p_i|}</tex>, 
потом вспоминаем, что <tex> |\delta_i| \leq \varepsilon_m </tex>.
Получаем следующее:

<tex> |k - \tilde{k}| \leq \\
\leq |r_1(b_x - a_x)(y_2 - a_y)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) + \\
+ |r_2(b_x - a_x)(y_1 - a_y)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) + \\
+ |r_1(b_y - a_y)(x_2 - a_x)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) + \\
+ |r_2(b_y - a_y)(x_1 - a_x)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) = \\
= (|r_1(b_x - a_x)(y_2 - a_y)| + |r_2(b_x - a_x)(y_1 - a_y)| + |r_1(b_y - a_y)(x_2 - a_x)| + \\
+ |r_2(b_y - a_y)(x_1 - a_x)|) \cdot
(6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6)</tex>

Пусть 

<tex> t = (|r_1(b_x - a_x)(y_2 - a_y)| + |r_2(b_x - a_x)(y_1 - a_y)| + |r_1(b_y - a_y)(x_2 - a_x)| + \\
+ |r_2(b_y - a_y)(x_1 - a_x)|).</tex> 

Получаем, что

<tex> \epsilon = |k - \tilde{k}| \leq t \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6). </tex>

Итого:

<tex> t \leq \tilde{t} \frac{1}{(1 - \varepsilon_m)^6} = \tilde{t} (1 + 6 \varepsilon_m + 21 \varepsilon_m^2 + 56 \varepsilon_m^3 + \ldots) </tex>

<tex> \epsilon = |k - \tilde{k}| \leq \tilde{\epsilon} \leq \tilde{t} (1 +  6 \varepsilon_m + 21 \varepsilon_m^2 + \ldots) (6 \varepsilon_m + 15 \varepsilon_m^2 + 20 \varepsilon_m^3 + \ldots) </tex>

[[Категория: Вычислительная геометрия]]