Computational Geometry in C, Joseph O'Rourke
Ещё раз спасибо! Дочитал до главы про диаграммы Вороного и понял, что это именно то, что мне нужно на первом этапе решения поставленной себе задачи. Правда диаграмму надо строить на сфере... И уметь эффективно перестраивать её при смещении только одной точки.
-- 30.12.2017, 17:32 --хотя в статье в Википедии, если мне не изменяет память, затрагивается такой важный вопрос, как повышение точности расчёта в случае, когда точки близки друг другу или в каком-либо другом неприятном случае). Только что решил задачу нахождения точки, равноудалённой от заданных трёх (как оказалось таких точек даже две
К сожалению, не нашёл нужной формулы, поэтому пришлось
изобретать велосипед решать самому. Опишу, то что напридумывал, вдруг кого заинтересует/кто-то предложит более разумный вариант.
Расстояние на сфере между двумя точками можно рассчитать в лоб через длину ходы, соединяющей эти точки. Получится такая формула:
![$\[\alpha =2\arcsin\sqrt{\frac{1-\cos {{\theta }_{1}}\cos {{\theta }_{2}}-\sin {{\theta }_{1}}\sin {{\theta }_{2}}\cos \left( {{\varphi }_{1}}-{{\varphi }_{2}} \right)}{2}}\]$](https://dxdy-04.korotkov.co.uk/f/3/0/7/307dfcbe5d00b740783a8c5a40dcc9e682.png "$\[\alpha =2\arcsin\sqrt{\frac{1-\cos {{\theta }_{1}}\cos {{\theta }_{2}}-\sin {{\theta }_{1}}\sin {{\theta }_{2}}\cos \left( {{\varphi }_{1}}-{{\varphi }_{2}} \right)}{2}}\]$")
Если чуть-чуть повозиться с формулами половинного/двойного угла, то её можно привести к такому виду:
К сожалению, обе эти формулы очень плохо работают, когда точки близки друг к другу. В первом случае из единицы вычитается число, отличающееся от неё на величину, квадратичную по порядку малости. В результате безумные погрешности округления для ещё разумных исходных значений. Вторая формула ничем не лучше: вычисляется арккосинус величины, так же отличающейся от единицы на квадратичную по порядку малости. Поэтому необходимо избавиться от этой разности единицы и близкого к ней значения. Это можно сделать так:
![$\[1-\cos {{\theta }_{1}}\cos {{\theta }_{2}}-\sin {{\theta }_{1}}\sin {{\theta }_{2}}\cos \left( {{\varphi }_{1}}-{{\varphi }_{2}} \right)=2{{\sin }^{2}}\frac{{{\theta }_{1}}-{{\theta }_{2}}}{2}+2\sin {{\theta }_{1}}\sin {{\theta }_{2}}{{\sin }^{2}}\frac{{{\varphi }_{1}}-{{\varphi }_{2}}}{2}\]$](https://dxdy-04.korotkov.co.uk/f/b/2/e/b2e2237f50e05cf42e1cf2fe2140a76c82.png "$\[1-\cos {{\theta }_{1}}\cos {{\theta }_{2}}-\sin {{\theta }_{1}}\sin {{\theta }_{2}}\cos \left( {{\varphi }_{1}}-{{\varphi }_{2}} \right)=2{{\sin }^{2}}\frac{{{\theta }_{1}}-{{\theta }_{2}}}{2}+2\sin {{\theta }_{1}}\sin {{\theta }_{2}}{{\sin }^{2}}\frac{{{\varphi }_{1}}-{{\varphi }_{2}}}{2}\]$")
Что приводит к формуле:
![$\[\alpha =2\arcsin\sqrt{{{\sin }^{2}}\frac{{{\theta }_{1}}-{{\theta }_{2}}}{2}+\sin {{\theta }_{1}}\sin {{\theta }_{2}}{{\sin }^{2}}\frac{{{\varphi }_{1}}-{{\varphi }_{2}}}{2}}\]$](https://dxdy-02.korotkov.co.uk/f/5/8/a/58a3d112327744c458fb790f31d664b682.png "$\[\alpha =2\arcsin\sqrt{{{\sin }^{2}}\frac{{{\theta }_{1}}-{{\theta }_{2}}}{2}+\sin {{\theta }_{1}}\sin {{\theta }_{2}}{{\sin }^{2}}\frac{{{\varphi }_{1}}-{{\varphi }_{2}}}{2}}\]$")
Эта формула уже прекрасно работает для близких точек, однако, проблема переместилась на другой конец интервала: формула очень плохо работает, когда точки лежат почти диаметрально противоположно (арксинус числа близкого к единице). И тут мне стало понятно, что простого решения я найти не смогу. Но можно подойти к задаче более обще. Пусть
![$\[y^2={{\sin }^{2}}\frac{{{\theta }_{1}}-{{\theta }_{2}}}{2}+\sin {{\theta }_{1}}\sin {{\theta }_{2}}{{\sin }^{2}}\frac{{{\varphi }_{1}}-{{\varphi }_{2}}}{2}\]$](https://dxdy-03.korotkov.co.uk/f/2/a/2/2a278d68f32b9a7be613308f1fdded0982.png "$\[y^2={{\sin }^{2}}\frac{{{\theta }_{1}}-{{\theta }_{2}}}{2}+\sin {{\theta }_{1}}\sin {{\theta }_{2}}{{\sin }^{2}}\frac{{{\varphi }_{1}}-{{\varphi }_{2}}}{2}\]$")
Тогда мне надо разрешить уравнение
![$\[\cos x=1-2{{y}^{2}}\]$](https://dxdy-02.korotkov.co.uk/f/1/b/9/1b9a93022ee719b0a91e91af2ee5bcb282.png "$\[\cos x=1-2{{y}^{2}}\]$")
относительно икса как можно точнее. Для малых значений аргумента и результата лучше использовать такую формулу:
![$\[\sin x=2y\sqrt{1-{{y}^{2}}}\]$](https://dxdy-02.korotkov.co.uk/f/1/2/0/1208083de514c943c13b53948863d84482.png "$\[\sin x=2y\sqrt{1-{{y}^{2}}}\]$")
А для величин порядка единицы решать уравнение в лоб, вычисляя арккосинус. Однако, очень неудобно пользоваться одной формулой для одного интервала, а другой — для другого. Лучшее, что я смог придумать — это объединить их в одну, используя арктангенс двух аргументов:
![$\[x={{\arctg}_{2}}\left( 2y\sqrt{1-{{y}^{2}}},1-2{{y}^{2}} \right)\]$](https://dxdy-02.korotkov.co.uk/f/d/6/1/d613bbdf0ed97fd5faf7a108d992ca4f82.png "$\[x={{\arctg}_{2}}\left( 2y\sqrt{1-{{y}^{2}}},1-2{{y}^{2}} \right)\]$")
Получился тот ещё крокодил.
— это группа ортогональных преобразований 
некоторого 
-мерного векторного евклидова пространства 
(она включает ещё и отражения). Соответственно, сложение «векторов» тут не коммутирует и всё немного хуже. Хотя это самое вложение сферы в евклидово пространство очень удобно для вычислений — можно брать 
— все повороты), которое лишь единственное переведёт первую во вторую, или даже переведёт одну в другую, оставляя на месте геодезическую, проходящую между ними — ибо для диаметрально противоположных точек она тоже не единственна. Во-вторых, и с этого следовало бы начать, касательные векторы теперь отвязаны от преобразований пространства, и касательные пространства для разных точек сферы друг с другом не отождествишь, как для аффинной/евклидовой плоскости. Хотя есть весьма хорошее отображение из пар (точка, касательный вектор в ней) в 
).