Предикат определения положения точек относительно друг друга — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 2 участников)
Строка 21: Строка 21:
 
Предикат, определяющий взаимное расположение точек <tex>c_1</tex> и <tex>c_2</tex> по ординате, выглядит следующим образом:
 
Предикат, определяющий взаимное расположение точек <tex>c_1</tex> и <tex>c_2</tex> по ординате, выглядит следующим образом:
  
<tex>K = (r_2 \cdot \sin \alpha + y_2) - (r_4 \cdot \sin \beta + y_4) = (r_2 \cdot \frac{y_1 - y_2}{r_1 + r_2} + y_2) - (r_4 \cdot \frac{y_3 - y_4}{r_3 + r_4} + y_4)</tex>
+
<tex>K = (r_2 \sin \alpha + y_2) - (r_4 \sin \beta + y_4) = (r_2 \frac{y_1 - y_2}{r_1 + r_2} + y_2) - (r_4 \frac{y_3 - y_4}{r_3 + r_4} + y_4)</tex>
  
Т.к. <tex> r_1 + r_2 > 0, r_3 + r_4 > 0</tex>, то можно оценивать знак выражения <tex>T = K \cdot (r_1 + r_2) \cdot (r_3 + r_4)</tex>
+
Т.к. <tex> r_1 + r_2 > 0, r_3 + r_4 > 0</tex>, то можно оценивать знак выражения <tex>T = K (r_1 + r_2) (r_3 + r_4)</tex>
  
<tex>T = (r_2 \cdot (y_1 - y_2)+y_2 \cdot (r_1+r_2)) \cdot (r_3+r_4) - (r_4 \cdot (y_3-y_4)+y_4 \cdot (r_3+r_4)) \cdot (r_1+r_2) = \\
+
<tex>T = (r_2 (y_1 - y_2)+y_2 (r_1+r_2)) (r_3+r_4) - (r_4 (y_3-y_4)+y_4 (r_3+r_4)) (r_1+r_2) = \\
= (y_1 \cdot r_2 + y_2 \cdot r_1)(r_3+r_4) - (y_3 \cdot r_4 + y_4 \cdot r_3)(r_1+r_2)</tex>
+
= (y_1 r_2 + y_2 r_1)(r_3+r_4) - (y_3 r_4 + y_4 r_3)(r_1+r_2)</tex>
  
Рассмотрим это выражение в дабловой арифметике. Обозначим за <tex>F(p_1, p_2, \ldots , p_n) = (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) = (1 + \delta_{p_1}) (1 + \delta_{p_2}) \ldots (1 + \delta_{p_n})</tex>
  
 
<tex>\tilde{T} = (y_1 \otimes r_2 \oplus y_2 \otimes r_1)(r_3 \oplus r_4) \ominus (y_3 \otimes r_4 \oplus y_4 \otimes r_3)(r_1 \oplus r_2) =</tex>
 
<tex>\tilde{T} = (y_1 \otimes r_2 \oplus y_2 \otimes r_1)(r_3 \oplus r_4) \ominus (y_3 \otimes r_4 \oplus y_4 \otimes r_3)(r_1 \oplus r_2) =</tex>
  
<tex>= [(y_1 \cdot r_2 \cdot F(1,2) + y_2 \cdot r_1 \cdot F(3,4))(r_3+r_4) \cdot F(5,6,7) - \\
+
<tex>= [(y_1 r_2 F(1,2) + y_2 r_1 F(3,4))(r_3+r_4) F(5,6,7) - \\
- (y_3 \cdot r_4 \cdot F(8,9) + y_4 \cdot r_3 \cdot F(10,11))(r_1+r_2) \cdot F(12,13,14)] \cdot F(15) =</tex>
+
- (y_3 r_4 F(8,9) + y_4 r_3 F(10,11))(r_1+r_2) F(12,13,14)] F(15) =</tex>
  
<tex>= y_1 \cdot r_2 \cdot (r_3+r_4)F(1,2,5,6,7,15)+ \\
+
<tex>= y_1 r_2 (r_3+r_4)F(1,2,5,6,7,15)+ \\
+ y_2 \cdot r_1 \cdot (r_3+r_4)F(3,4,5,6,7,15)- \\
+
+ y_2 r_1 (r_3+r_4)F(3,4,5,6,7,15)- \\
- y_3 \cdot r_4 \cdot (r_1+r_2)F(8,9,12,13,14,15)-\\
+
- y_3 r_4 (r_1+r_2)F(8,9,12,13,14,15)-\\
- y_4 \cdot r_3 \cdot (r_1+r_2)F(10,11,12,13,14,15)
+
- y_4 r_3 (r_1+r_2)F(10,11,12,13,14,15)
 
</tex>
 
</tex>
 +
 +
<tex>|\tilde{T}-T| = \\
 +
= |y_1  r_2  (r_3+r_4)(F(1,2,5,6,7,15)-1) + \\
 +
+ y_2  r_1  (r_3+r_4)(F(3,4,5,6,7,15)-1) - \\
 +
- y_3  r_4  (r_1+r_2)(F(8,9,12,13,14,15)-1) -\\
 +
- y_4  r_3  (r_1+r_2)(F(10,11,12,13,14,15)-1)| \leq \\
 +
\leq |y_1  r_2  (r_3+r_4)| \cdot |(F(1,2,5,6,7,15)-1)| + \\
 +
+ |y_2  r_1  (r_3+r_4)| \cdot |(F(3,4,5,6,7,15)-1)| + \\
 +
+ |y_3  r_4  (r_1+r_2)| \cdot |(F(8,9,12,13,14,15)-1)| +\\
 +
+ |y_4  r_3  (r_1+r_2)| \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>|\tilde{T}-T| \leq \\
 +
\leq |y_1  r_2  (r_3+r_4)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) + \\
 +
+ |y_2  r_1  (r_3+r_4)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) + \\
 +
+ |y_3  r_4  (r_1+r_2)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) +\\
 +
+ |y_4  r_3  (r_1+r_2)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) = \\
 +
= (|y_1  r_2  (r_3+r_4)|+|y_2  r_1  (r_3+r_4)|+|y_3  r_4  (r_1+r_2)|+|y_4  r_3  (r_1+r_2)|) \cdot \\
 +
\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' = |y_1  r_2  (r_3+r_4)|+|y_2  r_1  (r_3+r_4)|+|y_3  r_4  (r_1+r_2)|+|y_4  r_3  (r_1+r_2)|</tex>
 +
 +
Тогда <tex>|\tilde{T}-T| \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>|\tilde{T} - T| \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>
  
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]

Текущая версия на 19:10, 4 сентября 2022

Эта статья находится в разработке!

Пусть даны две пары касающихся окружностей [math](o_1(x_1, y_1), r_1)[/math], [math](o_2(x_2, y_2), r_2)[/math], [math](o_3(x_3, y_3), r_3)[/math], [math](o_4(x_4, y_4), r_4)[/math]. Положим, что [math]y_1 \gt y_2[/math] и [math]y_3 \gt y_4[/math].

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

Пусть [math]c_1[/math] - точка внешнего касания окружностей [math](o_1(x_1, y_1), r_1)[/math] и [math](o_2(x_2, y_2), r_2)[/math].

Точка [math]c_2[/math] - точка внешнего касания окружностей [math](o_3(x_3, y_3), r_3)[/math] и [math](o_4(x_4, y_4), r_4)[/math].

Определим углы [math]\alpha, \beta[/math].

[math]\alpha[/math] - угол между отрезком, соединяющим центры окружностей [math](o_1(x_1, y_1), r_1)[/math] и [math](o_2(x_2, y_2), r_2)[/math], и осью [math]OX[/math].

[math]\beta[/math] - угол между отрезком, соединяющим центры окружностей [math](o_3(x_3, y_3), r_3)[/math] и [math](o_4(x_4, y_4), r_4)[/math], и осью [math]OX[/math].

[math]\sin \alpha = \frac{y_1 - y_2}{r_1 + r_2}[/math].

[math]\sin \beta = \frac{y_3 - y_4}{r_3 + r_4}[/math].

Предикат, определяющий взаимное расположение точек [math]c_1[/math] и [math]c_2[/math] по ординате, выглядит следующим образом:

[math]K = (r_2 \sin \alpha + y_2) - (r_4 \sin \beta + y_4) = (r_2 \frac{y_1 - y_2}{r_1 + r_2} + y_2) - (r_4 \frac{y_3 - y_4}{r_3 + r_4} + y_4)[/math]

Т.к. [math] r_1 + r_2 \gt 0, r_3 + r_4 \gt 0[/math], то можно оценивать знак выражения [math]T = K (r_1 + r_2) (r_3 + r_4)[/math]

[math]T = (r_2 (y_1 - y_2)+y_2 (r_1+r_2)) (r_3+r_4) - (r_4 (y_3-y_4)+y_4 (r_3+r_4)) (r_1+r_2) = \\ = (y_1 r_2 + y_2 r_1)(r_3+r_4) - (y_3 r_4 + y_4 r_3)(r_1+r_2)[/math]

Рассмотрим это выражение в дабловой арифметике. Обозначим за [math]F(p_1, p_2, \ldots , p_n) = (1 + \delta_{p_1}) (1 + \delta_{p_2}) \ldots (1 + \delta_{p_n})[/math]

[math]\tilde{T} = (y_1 \otimes r_2 \oplus y_2 \otimes r_1)(r_3 \oplus r_4) \ominus (y_3 \otimes r_4 \oplus y_4 \otimes r_3)(r_1 \oplus r_2) =[/math]

[math]= [(y_1 r_2 F(1,2) + y_2 r_1 F(3,4))(r_3+r_4) F(5,6,7) - \\ - (y_3 r_4 F(8,9) + y_4 r_3 F(10,11))(r_1+r_2) F(12,13,14)] F(15) =[/math]

[math]= y_1 r_2 (r_3+r_4)F(1,2,5,6,7,15)+ \\ + y_2 r_1 (r_3+r_4)F(3,4,5,6,7,15)- \\ - y_3 r_4 (r_1+r_2)F(8,9,12,13,14,15)-\\ - y_4 r_3 (r_1+r_2)F(10,11,12,13,14,15) [/math]

[math]|\tilde{T}-T| = \\ = |y_1 r_2 (r_3+r_4)(F(1,2,5,6,7,15)-1) + \\ + y_2 r_1 (r_3+r_4)(F(3,4,5,6,7,15)-1) - \\ - y_3 r_4 (r_1+r_2)(F(8,9,12,13,14,15)-1) -\\ - y_4 r_3 (r_1+r_2)(F(10,11,12,13,14,15)-1)| \leq \\ \leq |y_1 r_2 (r_3+r_4)| \cdot |(F(1,2,5,6,7,15)-1)| + \\ + |y_2 r_1 (r_3+r_4)| \cdot |(F(3,4,5,6,7,15)-1)| + \\ + |y_3 r_4 (r_1+r_2)| \cdot |(F(8,9,12,13,14,15)-1)| +\\ + |y_4 r_3 (r_1+r_2)| \cdot |(F(10,11,12,13,14,15)-1)| [/math]

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

[math]|\tilde{T}-T| \leq \\ \leq |y_1 r_2 (r_3+r_4)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) + \\ + |y_2 r_1 (r_3+r_4)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) + \\ + |y_3 r_4 (r_1+r_2)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) +\\ + |y_4 r_3 (r_1+r_2)| \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) = \\ = (|y_1 r_2 (r_3+r_4)|+|y_2 r_1 (r_3+r_4)|+|y_3 r_4 (r_1+r_2)|+|y_4 r_3 (r_1+r_2)|) \cdot \\ \cdot (6\varepsilon_m + 15\varepsilon_m^2 + 20\varepsilon_m^3 + 15\varepsilon_m^4 + 6\varepsilon_m^5 + \varepsilon_m^6) [/math]

Обозначим [math]T' = |y_1 r_2 (r_3+r_4)|+|y_2 r_1 (r_3+r_4)|+|y_3 r_4 (r_1+r_2)|+|y_4 r_3 (r_1+r_2)|[/math]

Тогда [math]|\tilde{T}-T| \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)[/math]

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

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