Шаблон:Распространение радиоволн ВЧ/Реализация/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}}$.