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

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 9 промежуточных версий 2 участников)
Строка 1: Строка 1:
Заданы две окружности разного радиуса точками центров <tex>(x_0;y_0)</tex>, <tex>(x_1;y_1)</tex> и радиусами <tex>r_0</tex> и <tex>r_1</tex> соответственно.
+
[[Файл:circles.png‎|450px|thumb|Пересечение окружностей]]Заданы две окружности разного радиуса точками центров <tex>(x_0;y_0)</tex>, <tex>(x_1;y_1)</tex> и радиусами <tex>r_0</tex> и <tex>r_1</tex> соответственно.
 +
Будем вычислять координаты искомых точек пересечения окружностей в новой системе координат, связанной с векторами <tex>\bar{a}</tex> и <tex>\bar{b}</tex>, которые изображены на рисунке. Искать соответственно будем в виду <tex>\alpha\bar{a}+\beta\bar{b}</tex>.
 +
Для начала напишем, чему равен вектор <tex>\bar{a}=\begin{pmatrix}
 +
x_1-x_0\\
 +
y_1-y_0\\
 +
\end{pmatrix}</tex>, вектор <tex>\bar{b}</tex> перпендикулярен <tex>\bar{a}</tex>, следовательно равен <tex>\bar{b}=\begin{pmatrix}
 +
-y_1+y_0\\
 +
x_1-x_0\\
 +
\end{pmatrix}</tex>.
 +
Коэффициенты <tex>\alpha</tex> и <tex>\beta</tex> будем искать из системы уравнений <tex>\left\{\begin{array}{lrl}
 +
(\alpha\bar{a}+\beta\bar{b})^2=r_0^2\\
 +
(\alpha\bar{a}+\beta\bar{b}-\bar{a})^2=r_1^2\\
 +
\end{array}
 +
\right.</tex><br>
 +
<tex>\left\{\begin{array}{lrl}
 +
\alpha^2\bar{a}^2+\beta^2\bar{b}^2+2\alpha\beta\bar{a}\bar{b}=r_0^2\ \ \ (1)\\
 +
((\alpha-1)\bar{a}+\beta\bar{b})^2=r_1^2\\
 +
\end{array}
 +
\right.</tex><br>
 +
Заметим, что в уравнении <tex>(1)</tex> третье слагаемое в правой части равно <tex>0</tex>, т.к. векторы <tex>\bar{a}</tex> и <tex>\bar{b}</tex> перпендикулярны.<br>
 +
<tex>\left\{\begin{array}{lrl}
 +
\alpha^2\bar{a}^2+\beta^2\bar{b}^2=r_0^2\\
 +
(\alpha-1)^2\bar{a}^2+\beta^2\bar{b}^2=r_1^2\\
 +
\end{array}
 +
\right.</tex><br>
 +
<tex>\left\{\begin{array}{lrl}
 +
2\alpha-1=\frac{r_0^2-r_1^2}{\bar{a}^2}\\
 +
\beta^2\bar{b}^2=r_0^2-\alpha^2\bar{a}^2\\
 +
\end{array}
 +
\right.</tex><br>
 +
<tex>\left\{\begin{array}{lrl}
 +
\alpha=\frac{r_0^2-r_1^2+\bar{a}^2}{2\bar{a}^2}\\
 +
\beta^2\bar{b}^2=r_0^2-\alpha^2\bar{a}^2\\
 +
\end{array}
 +
\right.</tex><br>
 +
<tex>\left\{\begin{array}{lrl}
 +
\alpha=\frac{r_0^2-r_1^2+\bar{a}^2}{2\bar{a}^2}\\
 +
\beta^2=\frac{r_0^2-\frac{(r_0^2-r_1^2+\bar{a}^2)^2}{4\bar{a}^4}\bar{a}^2}{\bar{b}^2}\\
 +
\end{array}
 +
\right.</tex><br>
 +
<tex>\left\{\begin{array}{lrl}
 +
\alpha=\frac{r_0^2-r_1^2+\bar{a}^2}{2\bar{a}^2}\\
 +
\beta=\pm\frac{1}{|\bar{a}||\bar{b}|}\sqrt{-\frac{1}{2}(r_0^4+r_1^4+\bar{a}^4-2r_0^2r_1^2-2r_1^2\bar{a}^2)}\\
 +
\end{array}
 +
\right.</tex><br>
 +
Мы, например, будем рассматривать точку с положительным знаком <tex>\beta</tex>.
 +
Радиус-вектор такой точки будет равен <tex>\bar{s_1}=\bar{c_0}+\alpha\bar{a}+\beta\bar{b}</tex>. Его <tex>x</tex> координата равна <tex>{s_1}_x=x_0+\alpha\bar{a}_x+\beta\bar{b}_x</tex>. <tex>\bar{a}_x=x_1-x_0</tex>, <tex>\bar{b}_x=y_0-y_1</tex>.
 +
Допустим есть точка с <tex>x</tex> координатой равной <tex>x_c-r_c</tex> (точка вхождения некой окружности). Нам надо научиться сравнивать их для добавления в строку состояний.<br>
 +
<tex>{s_1}_x>x_c-r_c</tex><br>
 +
<tex>x_0+\alpha\bar{a}_x+\beta\bar{b}_x>x_c-r_c</tex><br>
 +
<tex>\alpha(x_1-x_0)+\beta(y_0-y_1)>x_c-r_c-x_0</tex><br>
 +
<tex>\frac{r_0^2-r_1^2+\bar{a}^2}{2\bar{a}^2}(x_1-x_0)+\frac{1}{|\bar{a}||\bar{b}|}\sqrt{-\frac{1}{2}(r_0^4+r_1^4+\bar{a}^4-2r_0^2r_1^2-2r_1^2\bar{a}^2)}(y_0-y_1)></tex><br>
 +
<tex>>x_c-r_c-x_0\ \ \ (*2\bar{a}^2|\bar{b}|)</tex><br>
 +
<tex>|\bar{b}|(r_0^2-r_1^2+\bar{a}^2)(x_1-x_0)+2|\bar{a}|\sqrt{-\frac{1}{2}(r_0^4+r_1^4+\bar{a}^4-2r_0^2r_1^2-2r_1^2\bar{a}^2)}(y_0-y_1)></tex><br>
 +
<tex>>2\bar{a}^2|\bar{b}|(x_c-r_c-x_0)</tex><br>
 +
<tex>2|\bar{a}|\sqrt{-\frac{1}{2}(r_0^4+r_1^4+\bar{a}^4-2r_0^2r_1^2-2r_1^2\bar{a}^2)}(y_0-y_1)></tex><br>
 +
<tex>>2\bar{a}^2|\bar{b}|(x_c-r_c-x_0)-|\bar{b}|(r_0^2-r_1^2+\bar{a}^2)(x_1-x_0)</tex><br>
 +
<tex>-2\bar{a}^2(r_0^4+r_1^4+\bar{a}^4-2r_0^2r_1^2-2r_1^2\bar{a}^2)(y_0-y_1)^2></tex><br>
 +
<tex>>(2\bar{a}^2|\bar{b}|(x_c-r_c-x_0)-|\bar{b}|(r_0^2-r_1^2+\bar{a}^2)(x_1-x_0))^2</tex><br>
 +
К сожалению, дальше упрощать ничего не получается :( Уже из этого выражения можно посчитать погрешность, так влоооом :(
 +
 
 +
[[Категория: Вычислительная геометрия]]

Текущая версия на 15:03, 16 июня 2012

Пересечение окружностей
Заданы две окружности разного радиуса точками центров [math](x_0;y_0)[/math], [math](x_1;y_1)[/math] и радиусами [math]r_0[/math] и [math]r_1[/math] соответственно.

Будем вычислять координаты искомых точек пересечения окружностей в новой системе координат, связанной с векторами [math]\bar{a}[/math] и [math]\bar{b}[/math], которые изображены на рисунке. Искать соответственно будем в виду [math]\alpha\bar{a}+\beta\bar{b}[/math]. Для начала напишем, чему равен вектор [math]\bar{a}=\begin{pmatrix} x_1-x_0\\ y_1-y_0\\ \end{pmatrix}[/math], вектор [math]\bar{b}[/math] перпендикулярен [math]\bar{a}[/math], следовательно равен [math]\bar{b}=\begin{pmatrix} -y_1+y_0\\ x_1-x_0\\ \end{pmatrix}[/math]. Коэффициенты [math]\alpha[/math] и [math]\beta[/math] будем искать из системы уравнений [math]\left\{\begin{array}{lrl} (\alpha\bar{a}+\beta\bar{b})^2=r_0^2\\ (\alpha\bar{a}+\beta\bar{b}-\bar{a})^2=r_1^2\\ \end{array} \right.[/math]
[math]\left\{\begin{array}{lrl} \alpha^2\bar{a}^2+\beta^2\bar{b}^2+2\alpha\beta\bar{a}\bar{b}=r_0^2\ \ \ (1)\\ ((\alpha-1)\bar{a}+\beta\bar{b})^2=r_1^2\\ \end{array} \right.[/math]
Заметим, что в уравнении [math](1)[/math] третье слагаемое в правой части равно [math]0[/math], т.к. векторы [math]\bar{a}[/math] и [math]\bar{b}[/math] перпендикулярны.
[math]\left\{\begin{array}{lrl} \alpha^2\bar{a}^2+\beta^2\bar{b}^2=r_0^2\\ (\alpha-1)^2\bar{a}^2+\beta^2\bar{b}^2=r_1^2\\ \end{array} \right.[/math]
[math]\left\{\begin{array}{lrl} 2\alpha-1=\frac{r_0^2-r_1^2}{\bar{a}^2}\\ \beta^2\bar{b}^2=r_0^2-\alpha^2\bar{a}^2\\ \end{array} \right.[/math]
[math]\left\{\begin{array}{lrl} \alpha=\frac{r_0^2-r_1^2+\bar{a}^2}{2\bar{a}^2}\\ \beta^2\bar{b}^2=r_0^2-\alpha^2\bar{a}^2\\ \end{array} \right.[/math]
[math]\left\{\begin{array}{lrl} \alpha=\frac{r_0^2-r_1^2+\bar{a}^2}{2\bar{a}^2}\\ \beta^2=\frac{r_0^2-\frac{(r_0^2-r_1^2+\bar{a}^2)^2}{4\bar{a}^4}\bar{a}^2}{\bar{b}^2}\\ \end{array} \right.[/math]
[math]\left\{\begin{array}{lrl} \alpha=\frac{r_0^2-r_1^2+\bar{a}^2}{2\bar{a}^2}\\ \beta=\pm\frac{1}{|\bar{a}||\bar{b}|}\sqrt{-\frac{1}{2}(r_0^4+r_1^4+\bar{a}^4-2r_0^2r_1^2-2r_1^2\bar{a}^2)}\\ \end{array} \right.[/math]
Мы, например, будем рассматривать точку с положительным знаком [math]\beta[/math]. Радиус-вектор такой точки будет равен [math]\bar{s_1}=\bar{c_0}+\alpha\bar{a}+\beta\bar{b}[/math]. Его [math]x[/math] координата равна [math]{s_1}_x=x_0+\alpha\bar{a}_x+\beta\bar{b}_x[/math]. [math]\bar{a}_x=x_1-x_0[/math], [math]\bar{b}_x=y_0-y_1[/math]. Допустим есть точка с [math]x[/math] координатой равной [math]x_c-r_c[/math] (точка вхождения некой окружности). Нам надо научиться сравнивать их для добавления в строку состояний.
[math]{s_1}_x\gt x_c-r_c[/math]
[math]x_0+\alpha\bar{a}_x+\beta\bar{b}_x\gt x_c-r_c[/math]
[math]\alpha(x_1-x_0)+\beta(y_0-y_1)\gt x_c-r_c-x_0[/math]
[math]\frac{r_0^2-r_1^2+\bar{a}^2}{2\bar{a}^2}(x_1-x_0)+\frac{1}{|\bar{a}||\bar{b}|}\sqrt{-\frac{1}{2}(r_0^4+r_1^4+\bar{a}^4-2r_0^2r_1^2-2r_1^2\bar{a}^2)}(y_0-y_1)\gt [/math]
[math]\gt x_c-r_c-x_0\ \ \ (*2\bar{a}^2|\bar{b}|)[/math]
[math]|\bar{b}|(r_0^2-r_1^2+\bar{a}^2)(x_1-x_0)+2|\bar{a}|\sqrt{-\frac{1}{2}(r_0^4+r_1^4+\bar{a}^4-2r_0^2r_1^2-2r_1^2\bar{a}^2)}(y_0-y_1)\gt [/math]
[math]\gt 2\bar{a}^2|\bar{b}|(x_c-r_c-x_0)[/math]
[math]2|\bar{a}|\sqrt{-\frac{1}{2}(r_0^4+r_1^4+\bar{a}^4-2r_0^2r_1^2-2r_1^2\bar{a}^2)}(y_0-y_1)\gt [/math]
[math]\gt 2\bar{a}^2|\bar{b}|(x_c-r_c-x_0)-|\bar{b}|(r_0^2-r_1^2+\bar{a}^2)(x_1-x_0)[/math]
[math]-2\bar{a}^2(r_0^4+r_1^4+\bar{a}^4-2r_0^2r_1^2-2r_1^2\bar{a}^2)(y_0-y_1)^2\gt [/math]
[math]\gt (2\bar{a}^2|\bar{b}|(x_c-r_c-x_0)-|\bar{b}|(r_0^2-r_1^2+\bar{a}^2)(x_1-x_0))^2[/math]
К сожалению, дальше упрощать ничего не получается :( Уже из этого выражения можно посчитать погрешность, так влоооом :(