Шаблон:Распространение радиоволн ВЧ/Реализация/encompassing aperture t::unify/Алгоритм

Пусть объединяются два сектора сферы, релизуемые классом классом encompassing_aperture_t - $\Omega _{1}=\left\langle {\vec {c}}_{1},\alpha _{1}\right\rangle$ и $\Omega _{2}=\left\langle {\vec {c}}_{2},\alpha _{2}\right\rangle$, где ${\vec {c}}_{i}$ - вектор направления на центральную точку $i$-го сектора (возвращаемый методом encompassing_aperture_t::central_point), а $\alpha _{i}\in \left[0;\pi \right]$ - соответствующий ангулярный радиус (возвращаемый методом encompassing_aperture_t::radius). Сектор, у которого ангулярный радиус равен $\pi$ охватывает сферу полностью независимо от вектора ${\vec {c}}_{i}$.

Сектор encompassing_aperture_t

В результате объединения создается новый сектор $\Omega _{12}=\left\langle {\vec {c}}_{12},\alpha _{12}\right\rangle =\Omega _{1}\cup \Omega _{2}$.

Вектора ${\vec {c}}_{i}$ могут быть либо нулевыми либо единичными. Сектор с нулевым вектором направления считается нейтральным по операции объединения, т.е. $\left\langle {\vec {0}},\alpha _{1}\right\rangle \cup \Omega =\Omega \cup \left\langle {\vec {0}},\alpha _{2}\right\rangle =\Omega$.

Далее рассматривается случай, в котором $\left|{\vec {c}}_{1}\right|=\left|{\vec {c}}_{2}\right|=1$.

Поскольку направленные отрезки ${\vec {c}}_{1}$ и ${\vec {c}}_{2}$ исходят из одной точки - центра сферы, оба отрезка принадлежат одной плоскости, причем эта плоскость является диаметральным сечением сферы. Поэтому задача поиска объединяющего сектора, то есть вектора ${\vec {c}}_{12}$ и ангулярного радиуса $\alpha _{12}$, становится двумерной.

Диаметральное сечение сферы, которому принадлежат вектора ${\vec {c}}_{1}$ и ${\vec {c}}_{2}$. Если ${\vec {c'}}_{1}\nparallel {\vec {c'}}_{2}$, то вектор ${\vec {c}}_{12}$, задающий направление на центральную точку объединяющего сектора, будет являться нормализованной суммой векторов ${\vec {c'}}_{1}$ и ${\vec {c'}}_{2}$, если $\alpha _{12}<{\frac {\pi }{2}}$ и противоположен этой сумме, если $\alpha _{12}>{\frac {\pi }{2}}$.

Пусть далее $\cos \gamma ={\frac {{\vec {c}}_{1}\cdot {\vec {c}}_{2}}{\left|{\vec {c}}_{1}\right|\cdot \left|{\vec {c}}_{2}\right|}}$, где $\gamma$ - угол между ${\vec {c}}_{1}$ и ${\vec {c}}_{2}$.

Два особых случая:

$\Omega _{1}\subseteq \Omega _{2}\Leftrightarrow \gamma +\alpha _{1}\leq \alpha _{2}$ и

$\Omega _{2}\subseteq \Omega _{1}\Leftrightarrow \gamma +\alpha _{2}\leq \alpha _{1}$.

Поэтому:

$\gamma +\alpha _{1}\leq \alpha _{2}\Rightarrow \Omega _{12}\equiv \Omega _{2}$, иначе

$\gamma +\alpha _{2}\leq \alpha _{1}\Rightarrow \Omega _{12}\equiv \Omega _{1}$.

Далее по тексту предполагается, что $\Omega _{1}\nsubseteq \Omega _{2}\land \Omega _{2}\nsubseteq \Omega _{1}$. Следовательно $\gamma \neq 0$.

Существует три случая.

Объединение секторов, у которых ${\vec {c}}_{1}\|{\vec {c}}_{2}$ (первый случай).

Рассмотрим первый случай, когда ${\vec {c}}_{1}\|{\vec {c}}_{2}$ (то есть $\cos \gamma \equiv -1$). Поскольку длины всех векторов равны единице, ${\vec {c}}_{2}=-{\vec {c}}_{1}$, а количество плоскостей, которым одновременно могут принадлежать ${\vec {c}}_{1}$ и ${\vec {c}}_{2}$ бесконечно, вследствие чего количество возможных секторов минимальной площади, объединяющих $\Omega _{1}$ и $\Omega _{2}$, также бесконечно и зависит от того на какой из плоскостей будут принадлежать выбранные ${\vec {c'}}_{1}$ и ${\vec {c'}}_{2}$; и этот выбор будет сводится к выбору диаметральной плоскости, проходящей через ${\vec {c}}_{1}$.

Этот выбор можно сделать, если задать произвольный вектор ${\vec {c}}_{n}$, перпендикулярный ${\vec {c}}_{1}$.

В описываемой реализации

${\vec {c}}_{n}=\left[{\begin{matrix}{\begin{pmatrix}1&0&0\end{pmatrix}}^{T}\Leftrightarrow {\vec {c}}_{1x}\equiv 0\\{\frac {{\begin{pmatrix}-{\frac {{\vec {c}}_{1y}}{{\vec {c}}_{1x}}}&1&0\end{pmatrix}}^{T}}{\left|{\begin{pmatrix}-{\frac {{\vec {c}}_{1y}}{{\vec {c}}_{1x}}}&1&0\end{pmatrix}}^{T}\right|}}\Leftrightarrow {\vec {c}}_{1x}\neq 0\end{matrix}}\right.$.

Тогда на плоскости, которой одновременно принадлежат ${\vec {c}}_{1}$, ${\vec {c'}}_{1}$ и ${\vec {c'}}_{2}$, будет однозначно определен вектор ${\vec {c'}}_{12}$, отстоящий на одинаковом угловом расстоянии от векторов ${\vec {c'}}_{1}$ и ${\vec {c'}}_{2}$ и, поэтому, параллельный вектору ${\vec {c}}_{12}$ центральной точки сектора-объединения.

Для нахождения вектора ${\vec {c'}}_{12}$ достаточно выразить его в базисе $\left\langle {\vec {c}}_{1},{\vec {c}}_{n}\right\rangle$ и осуществить переход к мировой системе координат входной модели. Как видно из рисунка, в указанном базисе вектор ${\vec {c'}}_{12}$ имеет координаты

${\begin{pmatrix}\left|{\vec {c}}_{1}\right|\cdot \cos \left({\frac {\pi }{2}}-\beta \right)\cos \left({\frac {\pi }{2}}-\left(\alpha _{1}+\beta \right)\right)\\\left|{\vec {c}}_{1}\right|\cdot \cos \left({\frac {\pi }{2}}-\beta \right)\sin \left({\frac {\pi }{2}}-\left(\alpha _{1}+\beta \right)\right)\end{pmatrix}}={\begin{pmatrix}\cos \left({\frac {\pi }{2}}-\beta \right)\cos \left({\frac {\pi }{2}}-\left(\alpha _{1}+\beta \right)\right)\\\cos \left({\frac {\pi }{2}}-\beta \right)\sin \left({\frac {\pi }{2}}-\left(\alpha _{1}+\beta \right)\right)\end{pmatrix}}$,

причем $\beta ={\frac {\pi -\left(\alpha _{1}+\alpha _{2}\right)}{2}}={\frac {\pi }{2}}-{\frac {\alpha _{1}+\alpha _{2}}{2}}$.

Тогда в мировых координатах

${\vec {c'}}_{12}={\begin{pmatrix}{\vec {c}}_{1}&{\vec {c}}_{n}\end{pmatrix}}{\begin{pmatrix}\cos \left({\frac {\pi }{2}}-{\frac {\alpha _{1}+\alpha _{2}}{2}}\right)\cos \left({\frac {\pi }{2}}+{\frac {\alpha _{1}-\alpha _{2}}{2}}\right)\\\cos \left({\frac {\pi }{2}}-{\frac {\alpha _{1}+\alpha _{2}}{2}}\right)\sin \left({\frac {\pi }{2}}+{\frac {\alpha _{1}-\alpha _{2}}{2}}\right)\end{pmatrix}}=\cos \left({\frac {\pi }{2}}-{\frac {\alpha _{1}+\alpha _{2}}{2}}\right){\begin{pmatrix}{\vec {c}}_{1}&{\vec {c}}_{n}\end{pmatrix}}{\begin{pmatrix}-\sin {\frac {\alpha _{1}-\alpha _{2}}{2}}\\\cos {\frac {\alpha _{1}-\alpha _{2}}{2}}\end{pmatrix}}$.

Пусть $\tau =-\cos \left({\frac {\pi }{2}}-{\frac {\alpha _{1}+\alpha _{2}}{2}}\right)$ и ${\vec {c''}}_{12}={\begin{pmatrix}{\vec {c}}_{1}&{\vec {c}}_{n}\end{pmatrix}}{\begin{pmatrix}\sin {\frac {\alpha _{1}-\alpha _{2}}{2}}\\\cos {\frac {\alpha _{1}-\alpha _{2}}{2}}\end{pmatrix}}$.

Тогда ${\vec {c'}}_{12}=-\tau {\vec {c''}}_{12}$.

Отсюда

${\vec {c}}_{12}=-{\frac {{\vec {c'}}_{12}}{\left|{\vec {c'}}_{12}\right|}}={\frac {\tau {\vec {c''}}_{12}}{\left|-\tau {\vec {c''}}_{12}\right|}}={\frac {{\vec {c''}}_{12}}{\left|{\vec {c''}}_{12}\right|}}$,

а ангулярный радиус будет равен

$\alpha _{12}=\pi -\beta ={\frac {\pi +\alpha _{1}+\alpha _{2}}{2}}$.

Во втором случае ${\vec {c}}_{1}\nparallel {\vec {c}}_{2}$, однако ${\vec {c'}}_{1}\|{\vec {c'}}_{2}$ (то есть $\alpha _{1}+\gamma +\alpha _{2}\equiv \pi$).

Лемма

$0\leq \alpha _{1},\alpha _{2}<{\frac {\pi }{2}}$.

Действительно, допустим $\alpha _{1}\geq {\frac {\pi }{2}}\Rightarrow \pi -\gamma -\alpha _{2}\geq {\frac {\pi }{2}}\Rightarrow {\frac {\pi }{2}}\geq \gamma +\alpha _{2}\Rightarrow \alpha _{1}\geq \gamma +\alpha _{2}\Rightarrow \Omega _{2}\subseteq \Omega _{1}$.

Противоречие ограничению, приведенному выше.

Аналогично доказывается ограничение $0\leq \alpha _{2}<{\frac {\pi }{2}}$.

Лемма $\alpha _{1}$ и $\alpha _{2}$ не могут быть одновременно равны нулю. Иначе имел бы место случай 1 выше.

Следствие

$0<\alpha _{1}+\alpha _{2}<\pi$.

Поскольку один из ангулярных радиусов обязательно ненулевой, примем ограничение $\alpha _{1}>0$ (тогда $\alpha _{2}\geq 0$).

Объединение секторов, у которых ${\vec {c'}}_{1}\|{\vec {c'}}_{2}$ (второй случай).

Решение задачи объединения сводится к поиску вектора ${\vec {c}}_{12}$, перпендикулярного ${\vec {c'}}_{1}$ (и ${\vec {c'}}_{2}$), лежащего в плоскости ${\vec {c}}_{1}$ и ${\vec {c}}_{2}$, имеющего острый угол одновременно с ${\vec {c}}_{1}$ и с ${\vec {c}}_{2}$ и нормализованного.

Поскольку вектора ${\vec {c}}_{1}$ и ${\vec {c}}_{2}$ линейно-независимы, их можно использовать в качестве базиса для поиска вектора, сонаправленного с ${\vec {c}}_{12}$, следующим образом.

Опустим перпендикуляр от конца одного из векторов, например ${\vec {c}}_{1}$, на вектор ${\vec {c}}_{12}$, перперндикулярный ${\vec {c'}}_{1}$ и образующий острый угол с ${\vec {c}}_{1}$. Обозначим вектор, связанный с направленным отрезком, который исходит от центра сферы к точке пересечения ${\vec {c}}_{12}$ и проведенного перпендикуляра, как ${\vec {c'}}_{12}$. Такой вектор очевидно будет сонаправлен с ${\vec {c}}_{12}$, а его длина будет равна

$\left|{\vec {c'}}_{12}\right|=\left|{\vec {c}}_{1}\right|\sin \alpha _{1}=\sin \alpha _{1}$;

${\vec {c}}_{12}=\tau {\vec {c'}}_{12}$.

Обозначим как ${\vec {c'}}_{12,\left\langle {\vec {c}}_{1},{\vec {c}}_{2}\right\rangle ,x}$ и ${\vec {c'}}_{12,\left\langle {\vec {c}}_{1},{\vec {c}}_{2}\right\rangle ,y}$ соответственно проекции вектора ${\vec {c'}}_{12}$ на ${\vec {c}}_{1}$ и ${\vec {c}}_{2}$ а равно координаты вектора ${\vec {c'}}_{12}$ в базисе $\left\langle {\vec {c}}_{1},{\vec {c}}_{2}\right\rangle$. Из теоремы синусов следует, что

${\frac {\sin \left(\alpha _{1}+\alpha _{2}\right)}{\left|{\vec {c'}}_{12}\right|}}={\frac {\sin \left(\alpha _{1}+\alpha _{2}\right)}{\sin \alpha _{1}}}={\frac {\sin \left({\frac {\pi }{2}}-\alpha _{2}\right)}{\left|{\vec {c'}}_{12,\left\langle {\vec {c}}_{1},{\vec {c}}_{2}\right\rangle ,x}\right|}}={\frac {\cos \alpha _{2}}{\left|{\vec {c'}}_{12,\left\langle {\vec {c}}_{1},{\vec {c}}_{2}\right\rangle ,x}\right|}}={\frac {\sin \left({\frac {\pi }{2}}-\alpha _{1}\right)}{\left|{\vec {c'}}_{12,\left\langle {\vec {c}}_{1},{\vec {c}}_{2}\right\rangle ,y}\right|}}={\frac {\cos \alpha _{1}}{\left|{\vec {c'}}_{12,\left\langle {\vec {c}}_{1},{\vec {c}}_{2}\right\rangle ,y}\right|}}$.

Тогда в базисе $\left\langle {\vec {c}}_{1},{\vec {c}}_{2}\right\rangle$ вектор ${\vec {c'}}_{12}$ будет равен:

${\vec {c'}}_{12}={\frac {\sin \alpha _{1}}{\sin \left(\alpha _{1}+\alpha _{2}\right)}}{\begin{pmatrix}{\vec {c}}_{1}&{\vec {c}}_{2}\end{pmatrix}}{\begin{pmatrix}\cos \alpha _{2}\\\cos \alpha _{1}\end{pmatrix}}$.

Пусть $\tau '={\frac {\sin \left(\alpha _{1}+\alpha _{2}\right)}{\sin \alpha _{1}}}$, и ${\vec {c''}}_{12}=\tau '{\vec {c'}}_{12}={\begin{pmatrix}{\vec {c}}_{1}&{\vec {c}}_{2}\end{pmatrix}}{\begin{pmatrix}\cos \alpha _{2}\\\cos \alpha _{1}\end{pmatrix}}$.

Таким образом, во втором случае ${\vec {c}}_{12}={\frac {\tau '{\vec {c''}}_{12}}{\left|\tau '{\vec {c''}}_{12}\right|}}={\frac {{\vec {c''}}_{12}}{\left|{\vec {c''}}_{12}\right|}}$, $\alpha _{12}={\frac {\pi }{2}}$.

В третьем случае предполагается, что ${\vec {c}}_{1}\nparallel {\vec {c}}_{2}$, и ${\vec {c'}}_{1}\nparallel {\vec {c'}}_{2}$.

Объединение секторов, у которых ${\vec {c}}_{1}\nparallel {\vec {c}}_{2}$, и ${\vec {c'}}_{1}\nparallel {\vec {c'}}_{2}$ (третий случай).

Пусть $\delta =\alpha _{1}+\gamma +\alpha _{2}$. Здесь $\delta >0$ и $\delta \neq \pi$, поскольку это - ситуации, описанные выше.

Тогда сектор $\Omega _{12}$ может быть задан парой ${\vec {c}}_{12}=\left(-1\right)^{s}\tau \left({\vec {c'}}_{1}+{\vec {c'}}_{2}\right)$ и $\alpha _{12}={\frac {\delta }{2}}$. $\tau$ - скаляр, нормализующий ${\vec {c}}_{12}$. Знак вектора-направления на центральную точку определяется тем, является ли угол $\delta$ выпуклым, т.е.

$s=\left[{\begin{matrix}0\Leftrightarrow \delta <\pi \\1\Leftrightarrow \delta >\pi \end{matrix}}\right.$.

Тогда для окончательного решения необходимо найти ${\vec {c'}}_{1}$ и ${\vec {c'}}_{2}$. Для этого выразим ${\vec {c'}}_{1}$ в базисе ${\vec {c}}_{1}$ и ${\vec {c'}}_{2}$ - в базисе ${\vec {c}}_{2}$.

Рассмотрим вектора ${\vec {c}}_{1}$ и ${\vec {c'}}_{1}$ и угол $\alpha _{1}$. Если $\alpha _{1}\equiv 0$, то ${\vec {c'}}_{1}={\vec {c}}_{1}$, поэтому в базисе $\left\langle {\vec {c}}_{1},{\vec {c}}_{2}\right\rangle$ он будет равен ${\begin{pmatrix}1&0&0\end{pmatrix}}^{T}$.

Далее рассмотрим случай, когда $\alpha _{1}\neq 0$. Направленные отрезки ${\vec {c}}_{1}$, ${\vec {c'}}_{1}$ и ${\vec {c}}_{2}$, с началом в точке пересечения ${\vec {c'}}_{1}$ и сферы до точки пересечения с ${\vec {c}}_{1}$, будут образовывать треугольник, стороны которого соотносятся друг с другом как

${\frac {\left|{\vec {c'}}_{1}\right|}{\sin \gamma }}={\frac {1}{\sin \gamma }}={\frac {{\vec {c'}}_{1x}}{\sin \left(\pi -\alpha _{1}-\gamma \right)}}={\frac {{\vec {c'}}_{1x}}{\sin \left(\alpha _{1}+\gamma \right)}}={\frac {{\vec {c'}}_{1y}}{\sin \alpha _{1}}}$.

Поэтому ${\vec {c'}}_{1}={\frac {1}{\sin \gamma }}{\begin{pmatrix}{\vec {c}}_{1}&{\vec {c}}_{2}\end{pmatrix}}{\begin{pmatrix}\sin \left(\alpha _{1}+\gamma \right)\\\sin \alpha _{1}\end{pmatrix}}$. Заметим, что поскольку $\gamma >0$ это равенство выполняется также и для случая $\alpha _{1}\equiv 0$.

Также отметим, что аналогичные рассуждения справедливы и для ${\vec {c'}}_{2}$.

Далее, пусть $\tau '={\frac {1}{\sin \gamma }}$, и

${\vec {c''}}_{1}={\begin{pmatrix}{\vec {c}}_{1}&{\vec {c}}_{2}\end{pmatrix}}{\begin{pmatrix}\sin \left(\alpha _{1}+\gamma \right)\\\sin \alpha _{1}\end{pmatrix}}$, и

${\vec {c''}}_{2}{\begin{pmatrix}{\vec {c}}_{1}&{\vec {c}}_{2}\end{pmatrix}}{\begin{pmatrix}\sin \alpha _{2}\\\sin \left(\alpha _{2}+\gamma \right)\end{pmatrix}}$.

Тогда ${\vec {c'}}_{1}=\tau '{\vec {c''}}_{1}$ и ${\vec {c'}}_{2}=\tau '{\vec {c''}}_{2}$, и

${\vec {c}}_{12}=\left(-1\right)^{s}{\frac {\tau '\left({\vec {c''}}_{1}+{\vec {c''}}_{2}\right)}{\left|\tau '\left({\vec {c''}}_{1}+{\vec {c''}}_{2}\right)\right|}}=\left(-1\right)^{s}{\frac {\left({\vec {c''}}_{1}+{\vec {c''}}_{2}\right)}{\left|\left({\vec {c''}}_{1}+{\vec {c''}}_{2}\right)\right|}}$, и

$\alpha _{12}={\frac {\delta }{2}}$.