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

Пусть $V={\begin{pmatrix}{\vec {v}}_{0},\cdots ,{\vec {v}}_{n-1}\end{pmatrix}}$ - непустое входное множество геометрических точек, и ${\vec {P}}$ - некоторая заданная точка, вокруг которой требуется построить сектор $\Omega =\left\langle {\vec {c}},\alpha \right\rangle$ сферы с единичным радиусом, где ${\vec {c}}$ - вектор, ассоциированный с направленным отрезком от ${\vec {P}}$ до центральной точки сектора на поверхности сферы, и $\alpha$ - ангулярный радиус сектора, как это реализуется классом encompassing_aperture_t. Проекции всех точек из $V$ на сферу должны принадлежать $\Omega$.

Пусть также все точки из $V$ лежат по одну сторону от $P$, т.е. $P$ не находится геометрически в облаке, образованном $V$. Если это не так, то множество $V$ должно быть разбито на подмножества точек, лежащих по одну сторону от $P$, а затем сектора, образованные применением описываемого алгоритма над $P$ и подмножествами, должны быть объединены с помощью функции unify.

Фактически, это означает, что все углы, образованные всеми возможными парами отрезков от $P$ до $\forall {\vec {v}}_{i}\in V$ должны быть меньше $\pi$. Это имеет место, когда $V$ образовано, например, вершинами одной отражающей поверхности ReflectingObject или контрольными точками одной плоскости вывода результатов PlainControlPointSet. См. также Source::OptimizeRadiationVectors.

Поиск центральной точки сферы и ангулярного радиуса при конструировании объекта encompassing_aperture_t на основе позиции точки ${\vec {P}}$, вокруг которой строится сфера, и двух точек, которые ограничивают площадь сектора. Вектора ${\vec {v}}_{1}$ и ${\vec {v}}_{2}$ на рисунке соответствуют векторам ${\vec {v'}}_{i}$ и ${\vec {v'}}_{j}$ в статье.

Если $\left|V\right|\equiv 1$, то $\Omega =\left\langle {\frac {{\vec {v}}_{0}-{\vec {P}}}{\left|{\vec {v}}_{0}-{\vec {P}}\right|}},0\right\rangle$. Далее по тексту $\left|V\right|\geq 2$.

Создадим множество $V'=\bigcup \limits _{i=0}^{n-1}\left({\vec {v}}_{i}-{\vec {P}}\right)$ и выберем пару ${\vec {v'}}_{i},{\vec {v'}}_{j}\in V'$ тех точек, отрезки из ${\vec {P}}$ до которых образуют между собой наибольший угол $2\alpha$.

Если угол равен нулю, то $\Omega =\left\langle {\frac {{\vec {v'}}_{i}}{\left|{\vec {v'}}_{i}\right|}},0\right\rangle$.

Поэтому далее по тексту рассматривается оставшийся случай, когда $\left|V\right|\geq 2$, $0<2\alpha <\pi$ и $0<\alpha <{\frac {\pi }{2}}$.

Тогда задача нахождения $\Omega$ будет сводиться к нахождению биссектрисы между ${\vec {v'}}_{i}$ и ${\vec {v'}}_{j}$, лежащий на ней вектор ${\vec {c}}$ единичной длины и угол $\alpha ={\frac {1}{2}}\arccos {\frac {{\vec {v'}}_{i}\cdot {\vec {v'}}_{j}}{\left|{\vec {v'}}_{i}\right|\cdot \left|{\vec {v'}}_{j}\right|}}$.

Для нахождения вектора ${\vec {c}}$ соединим прямой точки ${\vec {v'}}_{i}$ и ${\vec {v'}}_{j}$ и обозначим как $\tau {\vec {c}}$ вектор, с которым ассоциирован направленный отрезок, имеющий начало в точке ${\vec {P}}$, направленный вдоль биссектриссы между ${\vec {v'}}_{i}$ и ${\vec {v'}}_{j}$ до точки пересечения с прямой. Обозначим как ${\vec {v}}_{c}$ вектор, с которым ассоциирован направленный отрезок с началом в конце отрезка ${\vec {v'}}_{i}$ и концом в точке пересечения. То есть

${\vec {c}}={\vec {v}}_{i}+{\vec {v}}_{c}$.

Согласно теореме о биссектрисе эта точка делит отрезок между ${\vec {v'}}_{i}$ и ${\vec {v'}}_{j}$ в пропорции, равной отношению длин $\left|{\vec {v'}}_{i}\right|$ и $\left|{\vec {v'}}_{j}\right|$. Поэтому

${\vec {v}}_{c}=\left|{\vec {v}}_{c}\right|{\frac {{\vec {v'}}_{j}-{\vec {v'}}_{i}}{\left|{\vec {v'}}_{j}-{\vec {v'}}_{i}\right|}}$;

${\frac {\left|{\vec {v}}_{c}\right|}{\left|{\vec {v'}}_{j}-{\vec {v'}}_{i}\right|-\left|{\vec {v}}_{c}\right|}}={\frac {\left|{\vec {v}}_{i}\right|}{\left|{\vec {v}}_{j}\right|}}\Rightarrow {\vec {v}}_{c}={\frac {\left|{\vec {v}}_{i}\right|\cdot \left|{\vec {v}}_{j}-{\vec {v}}_{i}\right|}{\left|{\vec {v}}_{i}\right|+\left|{\vec {v}}_{j}\right|}}$.

Поэтому

$\tau {\vec {c}}={\frac {1}{\left|{\vec {v}}_{i}\right|\cdot \left|{\vec {v}}_{j}\right|}}\left(\left|{\vec {v}}_{j}\right|{\vec {v}}_{i}+\left|{\vec {v}}_{i}\right|{\vec {v}}_{j}\right)$.

Пусть $\tau '={\frac {\tau }{\left|{\vec {v}}_{i}\right|\cdot \left|{\vec {v}}_{j}\right|}}$ и

${\vec {c'}}={\begin{pmatrix}{\vec {v}}_{i}&{\vec {v}}_{j}\end{pmatrix}}{\begin{pmatrix}\left|{\vec {v}}_{j}\right|\\\left|{\vec {v}}_{i}\right|\end{pmatrix}}$.

Тогда ${\vec {c}}={\frac {\tau '{\vec {c'}}}{\tau '\left|{\vec {c'}}\right|}}={\frac {\vec {c'}}{\left|{\vec {c'}}\right|}}$ и $\alpha ={\frac {1}{2}}\arccos {\frac {{\vec {v'}}_{i}\cdot {\vec {v'}}_{j}}{\left|{\vec {v'}}_{i}\right|\cdot \left|{\vec {v'}}_{j}\right|}}$.