УказательРазделыОбозначенияАвторО проектеEnglish version


§

Вспомогательный раздел к разделу РАССТОЯНИЕ ОТ ТОЧКИ ДО КВАДРИКИ


Расстояние от точки до эллипса и эллипсоида

В настоящем разделе мы проанализируем следствия для \mathbb R^{3} общего результата, касающегося вычисления расстояния от точки до квадрики в {\mathbb R}^{n}. Основная задача: вычисление уравнения расстояний и детализация алгоритма нахождения координат точки ближайшей (а также самой дальней) на эллипсе или эллипсоиде к заданной точке.

§

Приведенные ниже результаты (если не указано особо) взяты из статей [1,2].

Расстояние от точки до эллипса на плоскости

Т

Теорема 1. Квадрат расстояния до эллипса

a_{11}x^2+2\,a_{12}xy+a_{22}y^2+2\, b_1 x + 2\, b_2 y -1 =0

от точки (x_{0},y_0) , не лежащей на эллипсе, равен минимальному положительному корню уравнения расстояний

{\mathcal F}(z)={\mathcal D}_{\mu}(\Phi(\mu,z))=0

при условии, что этот корень не является кратным. Здесь

\Phi(\mu,z)= \left| \begin{array}{ccc} a_{11}-\mu & a_{12} & b_1+\mu x_0 \\ a_{12} & a_{22}-\mu & b_{2}+\mu y_0 \\ b_1+\mu x_0 & b_2+\mu y_0 & -1 + \mu (z-x_0^2-y_0^2) \end{array} \right| \ ,

а {\mathcal D}_{} означает дискриминант полинома \Phi(\mu,z), рассматриваемого относительно переменной \mu_{}, в то время как остальные переменные считаются параметрами.

П

Пример. Найти расстояние от точки (2,1) до эллипса

-\frac{1}{2}x^2+\frac{1}{2}xy-\frac{3}{2}y^2+\frac{5}{2}x+4\,y-1=0 \ .

Решение. Имеем:

\Phi(\mu,z)=\left| \begin{array}{ccc} -1/2-\mu & 1/4 & 5/4+ 2\,\mu \\ 1/4 & -3/2-\mu & 2+\mu \\ 5/4+ 2\,\mu & 2+\mu & -1 + \mu (z-5) \end{array} \right|=
=z\mu^3+\left(2\,z+\frac{11}{2}\right)\mu^2+\left(\frac{11}{16}z+\frac{49}{4}\right)\mu+\frac{157}{32} \ .

Дискриминант полинома третьей степени можно вычислить по формуле

{\mathcal D}_{\mu}(A_0\mu^3+A_1\mu^2+A_2\mu+A_3)=
=A_1^2A_2^2-4\,A_1^3A_3-4\,A_0A_2^3+18\,A_0A_1A_2A_3-27\,A_0^2A_3^2 \ .

Вещественные корни полинома

{\mathcal F}(z)={\mathcal D}_{\mu}(\Phi(\mu,z))\equiv 2^{-10} \left(605\,z^4-27932\,z^3+306696\,z^2-1181744\,z+1304864 \right)

могут быть только положительными (см. Правило знаков Декарта ), можно установить (см. Система полиномов Штурма), что их четыре:

z_1 \approx 1.845415, \ z_2 \approx 5.717733\ , \ z_3 \approx 6.333919,\ z_4 \approx 32.271528 \ .

Следовательно, расстояние от заданной точки до эллипса равно \sqrt{z_1} \approx 1.358460.

Можно выписать и явное представление для уравнения расстояний как функции параметров задачи (коэффициентов уравнения эллипса и координат точки), но я укажу его только для случая когда уравнение эллипса приведено к каноническому виду. Приведенный ниже результат получен из теоремы 1 с помощью вспомогательной подстановки \mu \rightarrow 1/\mu и свойства 4 дискриминанта, указанного ЗДЕСЬ.

Т

Теорема 2. Квадрат расстояния до эллипса

\frac{x^2}{a^2}+\frac{y^2}{b^2}=1

от точки (x_{0},y_0) , не лежащей на эллипсе, равен минимальному положительному корню уравнения расстояний

{\mathcal F}(z)={\mathcal D}_{\mu}(\Phi(\mu,z))=0

при условии, что этот корень не является кратным. Здесь

\Phi(\mu,z)=\mu^3+A_1\mu^2+A_2\mu+A_3 =
=\mu^3-\left\{a^2+b^2-x_0^2-y_0^2+z \right\}\mu^2 + \left\{-a^2b^2\left(\frac{x_0^2}{a^2}+\frac{y_0^2}{b^2} -1 \right)+z(a^2+b^2) \right\}\mu - a^2b^2z \ ,

а {\mathcal D}_{} означает дискриминант полинома \Phi(\mu,z), рассматриваемого относительно переменной \mu_{}, в то время как остальные переменные считаются параметрами.

Вычисление дискриминанта полинома третьей степени производится по указанной выше формуле

{\mathcal D}_{\mu}(\mu^3+A_1\mu^2+A_2\mu+A_3)=
=A_1^2A_2^2-4\,A_1^3A_3-4\,A_2^3+18\,A_1A_2A_3-27\,A_3^2 \ ,

но вот дальнейшее разложение по степеням z_{} становится довольно громоздким. Полное разложение ЗДЕСЬ, а мы приведем только выражения для старшего коэффициента и свободного члена1):

\mathcal F(z)= (a^2-b^2)^2 z^4+\dots +
+ a^{4}b^{4}G^2(x_0,y_0) \left[(x_0^2+y_0^2-a^2-b^2)^2+4\,a^2b^2G(x_0,y_0)\right] \, ;

здесь G(x_0,y_0)= x_0^2/a^2+y_0^2/b^2-1.

§

Если в формулировках теорем поменять слова «минимальный положительный корень уравнения расстояний» на «максимальный положительный…», то получим решение задачи о нахождении расстояния от (x_{0},y_{0}) до самой дальней точки эллипса. В дальнейшем основные результаты будем формулировать исключительно в версии «минимальное расстояние», но примеры приводить в обоих вариантах.

При условии a\ne b (эллипс отличен от окружности), степень уравнения расстояний равна 4_{} и его (по крайней мере, в теории) можно решить в радикалах. Среди вещественных корней этого уравнения будут величины квадратов двух расстояний: от точки (x_{0},y_0) до ближайшей и до самой дальней точек эллипса.

Для нахождения координат указанных точек используем результат теоремы 2 из пункта РАССТОЯНИЕ ОТ ТОЧКИ ДО КВАДРИКИ. Если z_{}=z_{\ast} — корень уравнения расстояний, то полином \Phi(\mu,z_{\ast}) имеет кратный корень \mu=\mu_{\ast}. При выполнении условий теорем, кратность этого корня равна 2_{} и других кратных корней полином \Phi(\mu,z_{\ast}) не имеет. Величину \mu_{\ast}^{} можно выразить в виде рациональной функции от коэффициентов полинома, например, воспользовавшись результатом, приведенным ЗДЕСЬ:

\mu_{\ast}=\frac{9\,A_3-A_1A_2}{2(A_1^2-3\,A_2)} \ ;

здесь значения для A_1,A_2,A_3 берутся из формулировки теоремы 2 с осуществлением подстановки z_{}=z_{\ast}. Координаты точки эллипса, находящейся на расстоянии \sqrt{z_{\ast}} от точки (x_{0},y_0), определяются формулами

x_{\ast}=\frac{a^2x_0}{a^2-\mu_{\ast}},\quad y_{\ast}=\frac{b^2y_0}{b^2-\mu_{\ast}} \ .
П

Пример. Найти расстояния от точки (3,4) до ближайшей и самой дальней точек эллипса x^{2}/4+y^{2}=1.

Решение. Для этого примера имеем:

A_1=-z+20,\ A_2=5\,z-69,\ A_3=-4\, z \ .

Вещественные корни полинома

{\mathcal F}(z)= 9\,z^4-870\,z^3+31261\,z^2-524740\,z+3218436

могут быть только положительными (см. Правило знаков Декарта ), можно установить (см. Система полиномов Штурма), что их в точности два:

z_1 \approx 13.356826, \ z_2 \approx 42.721212\ .

Следовательно, расстояние от заданной точки до эллипса равно \sqrt{z_1} \approx 3.654699, а расстояние от нее до самой дальней точки эллипса равно \sqrt{z_2} \approx 6.536146.

Вычислим теперь координаты ближайшей и самой дальней точек. Для каждого из найденных значений z_{j} вычисляем величину

\mu_{j}=\frac{9\,A_3-A_1A_2}{2(A_1^2-3\,A_2)}=\frac{5\,(z_j^2-41\,z_j+276)}{2\,(z_j^2-55\,z_j+607)} \ ;

получаем:

\mu_1 \approx -4.589712,\quad \mu_2 \approx 10.600200 \ .

Подставляем найденные значения в формулы для определения координат:

x_{j}=\frac{12}{4-\mu_{j}},\quad y_{j}=\frac{4}{1-\mu_{j}} \ .

Координаты ближайшей к (3,4) точки на эллипсе —

\approx ( 1.397020, 0.715600) ,

самой дальней —

\approx (-1.818127, -0.416658) \ .

Анализ вещественных корней уравнения расстояний

При решении примеров из предыдущего пункта мы столкнулись с двумя различными случаями, которые возможны при решении уравнения расстояний : количество вещественных корней полинома 4_{}-й степени равно либо 2_{}, либо 4_{} — за исключением практически невероятных случаев существования кратных корней. В настоящем пункте мы займемся поиском границы на плоскости (x_0,y_0) между двумя различными качественными ситуациями; величины полуосей a_{} и b_{} эллипса фиксируем.

Анализ количества вещественных корней полинома \mathcal F_{}(z) проводится анализом знака дискриминанта

\Psi(x_0,y_0)= \mathcal D_z ( \mathcal F(z)) \equiv
\equiv 256\,a^2b^2(a^2-b^2)^2x_0^2y_0^2\left[\left\{(a^2-b^2)^2-a^2x_0^2-b^2y_0^2\right\}^3-27\,(a^2-b^2)^2a^2b^2x_0^2y_0^2\right]^3 \ .

При фиксированных значениях a_{} и b_{} дискриминантная кривая \Psi(x_{0},y_0)= 0 задает на плоскости (x_{0},y_0) границы областей с различными количествами вещественных корней соответствующих уравнений расстояний. Выясним на примере геометрию этой кривой.

П

Пример. Построить кривую \Psi(x_0,y_0) = 0 для эллипса x^2/4+y^2=1.

Решение. На плоскости (x,y_{}) кривая \Psi(x_0,y_{0})= 0 распадается на три ветви: координатные оси и кривую, задаваемую неявно уравнением

(4\,x_0^2+y_0^2-9)^3 +972\,x_0^2y_0^2=0

— она изображена красным цветом на рисунке справа. Эта кривая — астроида; впервые она была исследована Аполлонием в III веке до н.э. Аполлоний пришел к ней, исходя из иных соображений: задачу ставил о количестве перпендикуляров, которые можно опустить из точки плоскости на коническое сечение. Решение задачи возможно разными способами (в частности, астроида может быть получена как эволюта эллипса); само уравнение астроиды тоже получается в разных видах:

(2\,x)^{2/3}+y^{2/3}=3^{2/3} \ ,

или

x=3/2 \cos^3(t),y=3\sin^3(t) \quad npu \quad t\in [0, 2\pi] \ .

Исторический очерк работ Аполлония можно найти в [3], два способа построения астроиды излагаются в [4], еще один — с точки зрения оптимизации — в [5].

Однако какими бы способами не решалась задача, ответ, разумеется, будет един: для точек (x_{0},y_0), расположенных внутри астроиды, уравнение расстояний {\mathcal F}(z)_{}=0 имеет четыре вещественных корня, для точек, расположенных вне ее — два.

Продолжим анализ приведенного только что примера, имея целью выяснить: почему существенно условие простоты минимального положительного корня {\mathcal F}(z)_{}, упомянутое в теоремах 1 и 2 предыдущего пункта?

П

Пример. Построить график изменения квадрата расстояния от точек оси абсцисс до эллипса из предыдущего примера и определить координаты соответствующих ближайших точек эллипса.

Решение. При y_{0}=0 полином {\mathcal F}(z)_{} раскладывается на линейные множители:

{\mathcal F}(z) \equiv (z-(x_0-2)^2)(z-(x_0+2)^2)(3\,z - (3-x_0^2))^2 \ .

Изобразим графики корней z_{1}=(x_0-2)^2 (зеленым цветом) и z_{2} = 1- x_0^2/3 (синим):

На всем протяжении своей неотрицательности x_0\in [ 0, \sqrt{3}] корень z_{2} будет минимальным из всех корней полинома {\mathcal F}(z). Тем не менее при x_{0} > 3/2 за квадрат расстояния отвечает корень z_{1} и график изменения квадрата расстояния оказывается склеенным из двух — с точкой склейки в (3/2, 1/4_{}).

Чтобы понять, почему это происходит, определим ближайшие точки эллипса к точке (x_{0},0). Очевидно, что при x_{0} = 0 их будет две — x=0_{}, y=\pm 1. При непрерывном возрастании x_{0} пара ближайших точек на эллипсе начинает двигаться в том же направлении до тех пор, пока… А, кстати, до каких пор? — Посмотрим:

x=4/3 x_0,\ y= \pm \sqrt{1-4/9x_0^2}

и y_{} будет вещественным числом только при x_{0}\le 3/2. Что происходит при дальнейшем увеличении x_{0}? — Ближайшей к (x_{0},0) точкой эллипса становится точка (2,0_{}) и остается ею навсегда.

Вывод. Может так случиться, что минимальный вещественный корень полинома {\mathcal F}(z)_{} окажется кратным и порожденным парой мнимых точек эллипса. Хотя эта ситуация и может считаться исключительной, но все же ее надо учитывать, и когда-нибудь я приведу здесь условие ее проверки. Пока замечу, что ее можно «отследить» проверкой более жесткого условия — чтобы полином {\mathcal F}(z)_{} вовсе не имел кратных корней, т.е. чтобы его дискриминант \mathcal D_{z} ({\mathcal F}(z)) был отличен от нуля.

Эквидистанта эллипса

Рассмотрим эллипс на плоскости, в каждой его точке A_{} проведем перпендикуляр и возьмем на этом перпендикуляре точки, находящиеся на некотором фиксированном расстоянии h_{} от точки A_{}. Полученные точки формируют две кривые, каждую из которых назовем эквидистантой эллипса

§

Общая теория эквидистант гладких плоских кривых ЗДЕСЬ.

Т

Теорема 3. Если эллипс задан параметрически уравнениями

x= a\,\cos t,\ y= b\,\sin t \ npu \ t \in [0, 2\, \pi] ,

то уравнения его эквидистант:

x=\left(a\pm \frac{bh}{\sqrt{a^2 \sin^2 t+b^2 \cos^2 t}} \right)\cos \, t,\quad y=\left(b\pm \frac{ah}{\sqrt{a^2 \sin^2 t+b^2 \cos^2 t}} \right)\sin \, t \quad npu \ t \in [0,2\pi] .

Знаки должны быть согласоваными.

П

Пример. Эквидистанты эллипса x^{2}/4+y^2=1, соответствующие значениям h_{}=1/2 и h_{}=3/4, изображены на рисунке. Видим, что при возрастании параметра h_{} от нуля, при некоторых его значениях происходит нарушение гладкости «внутренней» эквидистанты к эллипсу: на ней возникают «хвосты». Для каждой точки на хвосте существует точка эллипса, находящаяся на расстоянии, равном (определяющему эту эквидистанту значению параметра) h_{}; но при этом найдется и другая точка эллипса на расстоянии меньшем h_{}!

Представление эквидистант эллипса в алгебраической форме возможно с помощью теоремы 2.

Т

Теорема 4. Эквидистанты эллипса

\frac{x^2}{a^2}+\frac{y^2}{b^2}=1

задаются неявно уравнением \Psi_h(x,y)=0 при

\Psi_h(x,y)= {\mathcal D}_{\mu}\Bigg( \mu^3-\left\{a^2+b^2-x^2-y^2+h^2 \right\}\mu^2 + \left\{-a^2b^2\left(\frac{x^2}{a^2}+\frac{y^2}{b^2} -1 \right)+h^2(a^2+b^2) \right\}\mu - h^2a^2b^2 \Bigg) \ .

Здесь {\mathcal D}_{\mu} означает дискриминант полинома, рассматриваемого относительно переменной \mu_{}, в то время как остальные переменные считаются параметрами.

П

Пример. Найти представление эквидистант эллипса x^{2}/4+y^2=1 посредством алгебраического уравнения.

Решение. Имеем

\Psi_h(x,y)= {\mathcal D}_{\mu}(\mu^3-(5-x^2-y^2+h^2)\mu^2+(-x^2-4\,y^2+4+5\,h^2)\mu-4\,h^2)=
=9\,h^8-6(2\,x^2+7\,y^2+15)\,h^6+(-2\,x^4+73\,y^4+62\,x^2y^2-90\,x^2+270\,y^2+297)\,h^4+
+ (-56\,y^6-360\,y^2-62\,x^4-248\,y^4+4\,x^6+270\,x^2-90\,x^2y^4-30\,x^4y^2+140\,x^2y^2-360)\,h^2+
+4(x^4+2\,x^2y^2+y^4-6\,x^2+6\,y^2+9)(x^2/4+y^2-1)^2 \ .

Уравнение эквидистант \Psi_h(x,y) = 0. Можно ли утверждать, что неравенство \Psi_h(x,y)<0 задает h_{}-окрестность эллипса? — Ответ положителен при h\le 1/2, но отрицателен при h>1/2. На рисунке заштрихована область \Psi_{7/8}(x,y)<0. Видим, что \Psi_{7/8}(1,0)>0, в то время как расстояние от точки (1,0) до эллипса равно (см. решение примера ВЫШЕ) \sqrt{2/3} \approx 0.8164965 < 7/8 = 0.875.

§

Другие интересности про эквидистанты эллипса ЗДЕСЬ.

Расстояние от точки до эллипса в пространстве

!

В настоящем пункте — только расчет примера; объяснение алгоритма выложу очень не скоро…

П

Пример. Найти расстояние от начала координат до эллипса, получающегося пересечением

\frac{(x-2)^2}{4}+\frac{(y-2)^2}{9}+(z-2)^2=1 \quad u \quad z=2

Решение. Здесь

A=\left( \begin{array}{rrr} -9/160 & 0 & 0 \\ 0 & -1/40 & 0 \\ 0 & 0 & 1 \end{array} \right) \ , B=\left( \begin{array}{rrr} 0 \\ 0 \\ 0 \end{array} \right),\ C=\left( \begin{array}{rrr} 0 \\ 0 \\ 1 \end{array} \right),\ b=2
M=\left[ \begin{array}{cc} E & \mathbb O \\ \mathbb O & - z \end{array} \right]-\lambda \left[ \begin{array}{cc} A & B \\ B^{\top} & - 1 \end{array} \right] - \mu \left[ \begin{array}{cc} \mathbb O & C \\ C^{\top} & - 2b \end{array} \right]= \left[ \begin{array}{cccc} 1+9/160\lambda & 0 & 0 & -9/80\lambda \\ 0 & 1+1/40\lambda & 0 & -1/20\lambda \\ 0 & 0 & 1+9/40\lambda & -9/20\lambda-\mu \\ -9/80\lambda & -1/20\lambda & -9/20\lambda-\mu & -z+\lambda+4\mu \end{array} \right]
\det M =-z+\lambda+4\mu-\frac{49}{160}\lambda \, z+\frac{567}{6400}\lambda^2-\mu^2+\frac{13}{40}\lambda\mu-\frac{63}{3200}\lambda^2\,z-
-\frac{13}{160}\lambda\mu^2-\frac{81}{128000}\lambda^3+\frac{9}{1600}\lambda^2\mu-\frac{81}{256000}\lambda^3\,z-\frac{9}{6400}\lambda^2\mu^2-\frac{729}{10240000}\lambda^4

По отбрасывании постороннего множителя, уравнение расстояний

{\mathcal F}(z) =(5\,z-21)(5\,z^3-309\,z^2+5928\,z-41872)=0 \ .

Его вещественные корни:

z_1=\frac{21}5=4.2,
z_2=\frac{27}{5} \sqrt[3]{9}+\frac{9}{5} \sqrt[3]{3} + \frac{83}5 \approx 30.42850187

Корню z =z_1 соответствуют значения параметров: \lambda_1 = 40/9 , \mu_1= 2. Координаты точки на эллипсе, ближайшей к началу координат:

X_{\ast} = \left[ \frac{2}{5}, \frac{1}{5} , 2 \right]^{\top} \ .

Расстояние от точки до эллипсоида

Т

Теорема 1. Квадрат расстояния до эллипсоида

a_{11}x^2+a_{22}y^2+a_{33}z^2 +2\,a_{13}xz+2\,a_{12}xy+2\,a_{23}yz+2\, b_1 x + 2\, b_2 y +2\, b_3 z -1 =0

от точки (x_{0},y_0,z_0) , не лежащей на эллипсоиде, равен минимальному положительному корню уравнения расстояний

{\mathcal F}(u)={\mathcal D}_{\mu}(\Phi(\mu,u))=0

при условии, что этот корень не является кратным. Здесь

\Phi(\mu,u)= \left| \begin{array}{cccc} a_{11}-\mu & a_{12} & a_{13} & b_1+\mu x_0 \\ a_{12} & a_{22}-\mu & a_{23} & b_{2}+\mu y_0 \\ a_{13} & a_{23} & a_{33}-\mu & b_3+\mu z_0 \\ b_1+\mu x_0 & b_2+\mu y_0 & b_3+\mu z_0 & -1 + \mu (u-x_0^2-y_0^2-z_0^2) \end{array} \right| \ ,

а {\mathcal D}_{} означает дискриминант полинома \Phi(\mu,u), рассматриваемого относительно переменной \mu_{}, в то время как остальные переменные считаются параметрами.

П

Пример. Найти расстояние от точки (6,7,8) до эллипсоида

7\,x_1^2+6\,x_2^2+5\,x_3^2-4\,x_1x_2-4\,x_2x_3-3\,x_1-4\,x_2+5\,x_3-18=0\ .

Решение. Здесь

A = \left( {\begin{array}{rrr} \frac{7}{18} & -\frac{1}{9} & 0 \\ && \\ -\frac{1}{9} & \frac{1}{3} & -\frac{1}{9} \\ && \\ 0 & -\frac{1}{9} & \frac{5}{18} \end{array}} \right),\quad B = \left( \begin{array}{r} -\frac{1}{12} \\ \\ -\frac{1}{9} \\ \\ \frac{5}{36} \end{array} \right) ,

и

\Phi(\mu,u)= \left| \begin{array}{cccc} 7/18-\mu & -1/9 & 0 & -1/12+6\,\mu \\ -1/9 & 1/3-\mu & -1/9 & -1/9+7\,\mu \\ 0 & -1/9 & 5/18-\mu & 5/36+8\,\mu \\ -1/12+6\,\mu & -1/9+7\,\mu & 5/36+8\,\mu & -1 + \mu (u-149) \end{array} \right|=
=\mu^4u-(u-25)\mu^3-\left(-\frac{11}{36}\,u+\frac{12883}{648}\right)\mu^2-\left(\frac{1}{36}u-\frac{10949}{2916}\right)\mu+\frac{1621}{52488} \ .

Дискриминант полинома четвертой степени можно вычислить по формуле

{\mathcal D}_{\mu}(A_0\mu^4+A_1\mu^3+A_2\mu^2+A_3\mu+A_4)=4\,I_2^3-27\,I_3^2 \ .

Здесь

I_2=4\,A_0A_4-A_1A_3 +\frac{1}{3}A_2^2 \ ,
I_3=-A_0A_3^2-A_1^2A_4+\frac{8}{3}A_0A_2A_4+ \frac{1}{3}A_1A_2A_3-\frac{2}{27}A_2^3 \ .

В применении к нашему случаю получаем

{\mathcal F}(u) = {\mathcal D}_{\mu}(\Phi(\mu,u)) = 2^{-11}3^{-24} \Big( 38263752\,u^6+2599127028\,u^5-1635554407320\,u^4-
-208679286534113\,u^3+3201333858779186\,u^2+1534445084940739328\,u+70891021564332120000 \Big) \ .

Этот полином имеет ровно два вещественных корня:

u_1 \approx 91.969401, u_2 \approx 216.077674 \ .

Расстояние от заданной точки до эллипсоида равно \sqrt{u_1} \approx 9.590068, а расстояние до самой дальней точки эллипсоида равно \sqrt{u_2} \approx 14.699581.

Можно выписать и явное представление для уравнения расстояний как функции параметров задачи (коэффициентов уравнения эллипсоида и координат точки), но я укажу его только для случая когда уравнение эллипсоида приведено к каноническому виду. Приведенный ниже результат получен из теоремы ? с помощью вспомогательной подстановки \mu \rightarrow 1/\mu и свойства 4 дискриминанта, указанного ЗДЕСЬ.

Т

Теорема 2. Квадрат расстояния до эллипсоида

G(x,y,z)=\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1=0

от точки (x_{0},y_0,z_0) , не лежащей на эллипсоиде, равен минимальному положительному корню уравнения расстояний

{\mathcal F}(u)={\mathcal D}_{\mu}(\Phi(\mu,u))=0

при условии, что этот корень не является кратным. Здесь

\Phi(\mu,u)=\mu^4+A_1\mu^3+A_2\mu^2+A_3\mu +A_4

при

\begin{array}{lcl} A_1&=&x_0^2+y_0^2+z_0^2-u-a^2-b^2-c^2, \\ A_2&=& a^2b^2c^2\bigg\{\left( \displaystyle \frac{1}{b^2c^2}+\frac{1}{a^2c^2}+\frac{1}{a^2b^2}\right)u +\left( \displaystyle \frac{x_0^2}{a^4}+\frac{y_0^2}{b^4}+\frac{z_0^2}{c^4} \right) - \left(\displaystyle \frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2}\right)G(x_0,y_0,z_0) \bigg\} , \\ A_3&=&a^2b^2c^2\bigg\{G(x_0,y_0,z_0) -\left( \displaystyle \frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2}\right)u\bigg\} \\ A_4&=& a^2b^2c^2 u\ , \end{array}

а {\mathcal D}_{} означает дискриминант полинома \Phi(\mu,u), рассматриваемого относительно переменной \mu_{}, в то время как остальные переменные считаются параметрами.

Вычисление дискриминанта полинома четвертой степени производится по указанной выше формуле

{\mathcal D}_{\mu}(\mu^4+A_1\mu^3+A_2\mu^2+A_3\mu+A_4)=4\,I_2^3-27\,I_3^2 \ ;

здесь

I_2=4\,A_4-A_1A_3 +\frac{1}{3}A_2^2 \ ,
I_3=-A_3^2-A_1^2A_4+\frac{8}{3}A_2A_4+ \frac{1}{3}A_1A_2A_3-\frac{2}{27}A_2^3 \ .

Но вот дальнейшее разложение по степеням u_{} становится довольно громоздким, см. ЗДЕСЬ. Сейчас ограничусь только представлениями старшего коэффициента и свободного члена2):

\mathcal F(u)\equiv (a^2-b^2)^2(a^2-c^2)^2(b^2-c^2)^2 u^6+\dots+
+a^4b^4c^4G^2(x_0,y_0,z_0) \mathcal{D}_{\mu}(\mu^3+A_1\mu^2+A_2\mu+A_3) \, ,

здесь значения для A_1,A_2,A_3 берутся из формулировки теоремы 2 с осуществлением подстановки u=0.

При условии a\ne b \ne c \ne a (эллипсоид не является эллипсоидом вращения), степень уравнения расстояний равна 6_{} и его, как правило, нельзя решить в радикалах. Среди вещественных корней этого уравнения будут величины квадратов двух расстояний: от точки (x_{0},y_0,z_0) до ближайшей и до самой дальней точек эллипсоида.

Для нахождения координат указанных точек используем результат теоремы 2 из пункта РАССТОЯНИЕ ОТ ТОЧКИ ДО КВАДРИКИ. Если u_{}=u_{\ast} — корень уравнения расстояний, то полином \Phi(\mu,u_{\ast}) имеет кратный корень \mu=\mu_{\ast}. При выполнении условий теорем, кратность этого корня равна 2_{} и других кратных корней полином \Phi(\mu,u_{\ast}) не имеет. Величину \mu_{\ast}^{} можно выразить в виде рациональной функции от коэффициентов полинома, например, воспользовавшись результатом, приведенным ЗДЕСЬ:

\mu_{\ast}=\frac{2\,A_1I_2^2+(3\,A_1A_2-18\,A_3)I_3}{(24\,A_2-9\,A_1^2)I_3-8\,I_2^2}

здесь значения для A_1,A_2,A_3,A_4 берутся из формулировки теоремы ?? с осуществлением подстановки u=u_{\ast}.

Координаты точки эллипсоида, находящейся на расстоянии \sqrt{u_{\ast}} от точки (x_{0},y_0,z_0) вычисляются по формулам

x_{\ast}=\frac{a^2x_0}{a^2-\mu_{\ast}},\ y_{\ast}=\frac{b^2y_0}{b^2-\mu_{\ast}}, z_{\ast}=\frac{c^2z_0}{c^2-\mu_{\ast}} \ .
П

Пример. На эллипсоиде x^2/4+y^2/16+z^2/49=1 найти ближайшую и самую дальнюю точки к точке (6,-2,5).

Решение. Для этого примера имеем:

A_1=-u-4,\ A_2=69\,u-2008,\ A_3=-1044\,u+27472,\ A_4= 3136\,u\ .

Уравнение расстояний:

2^4(19847025\,u^6-8393808060\,u^5+1317736785456\,u^4 -103262746605120\,u^3+4327358033988864\,u^2-
-91883501048862720\,u+757148717189025792)=0

имеет (в точности) два положительных корня:

u_1 \approx 21.636337,\ u_2 \approx 186.729608 \ .

Следовательно, расстояние от заданной точки до эллипсоида равно \sqrt{u_1}\approx 4.651488, а расстояние от нее же до самой дальней точки эллипсоида равно \sqrt{u_2} \approx 13.664904. Соответствующие значения кратного корня полинома \Phi(\mu, u_j) вычисляются по приведенной выше формуле:

\mu_{j}= \frac{2(94581\,u_j^5-26525988\,u_j^4+2036643696\,u_j^3-41839985024\,u_j^2 -742245672192\,u_j +16044295020544)}{46683\,u_j^5-16504668\,u_j^4+1934686224\,u_j^3-101284594048\,u_j^2+2376476312064\, u_j-19462452484096}

т.е.

\mu_1 \approx -11.70096, \ \mu_2 \approx 84.64247 \ .

Координаты точки на эллипсоиде, ближайшей к (6,-2,5):

X_1 \approx (1.52857,-1.15519,4.03618),

а самой дальней от нее:

X_2 \approx (-0.29761,0.46618,-6.87382) \ .

§

В геодезии имеется понятие геодезической или эллипсоидальной высоты точки как расстояния от точки (космического) пространства до эллипсоида, представляющего собой приближение поверхности Земли. Подробнее ЗДЕСЬ.

Приближенные формулы для расстояния

Представленное в предыдущих пунктах решение задачи нахождения расстояния от точки до эллипса или эллипсоида является аналитическим и универсальным, т.е. дает полное решение задачи в виде зависимости расстояния от параметров кривой (поверхности) и координат точки. К сожалению, эта зависимость неявная: для того, чтобы получить расстояние требуется решить подходящее алгебраическое уравнение — уравнение расстояний. Можно ли найти приближение для корня этого уравнения в виде явной функции?

Поясним постановку задачи. В теореме 2 ПУНКТА уравнение расстояний для эллипса, заданного в каноническом виде G(x,y)=x^2/a^2+y^2/b^2-1=0, выписывается в форме

B_0z^4 + B_1z^3+B_2z^2+B_3z+B_4=0

при

B_0=(a^2-b^2)^2,\dots, B_4= a^{4}b^{4}G^2(x_0,y_0) \left[(x_0^2+y_0^2-a^2-b^2)^2+4\,a^2b^2G(x_0,y_0)\right]

и выражениях для B_1,B_2,B_3, приведенных ЗДЕСЬ. В предположении о близости точки (x_0,y_0) к рассматриваемому эллипсу, можно считать, что искомый корень z_{\ast} уравнения близок к 0_{} и поэтому может приближен корнем линеаризации этого уравнения:

B_3z+B_4=0 \quad \Rightarrow \quad z_{\ast} \approx -B_4/B_3 \, .

Предлагается вычислять приближение расстояния по формуле

d \approx \sqrt{-B_4/B_3} \, .

Исследуем применимость этой формулы на конкретном примере.

П

Пример. Расстояние от точки с координатами x_0=a+1/2, y_0=0 до эллипса x^2/a^2+y^2/25=1 равно 1/2 при любом a\ne 0. Вычислим приближения этого расстояния по предложенной формуле:

d\approx\frac{5}{4}\sqrt{-\frac{(8\,a+202)(4\,a+1)^2}{16\,a^4-792\,a^3-20999\,a^2-10400\,a-2550}} \ .

Имеем:

\begin{array}{c|c|c|c|c|c|c|c} a & 5 & 10 & 30 & 60 & 67 & 68 & 69 \\ \hline \sqrt{-B_4/B_3} \approx & 0.499 & 0.511 & 0.605 & 1.245 & 2.786 & 4.282 & n/a \end{array}

При a=69 подкоренное выражение отрицательно. Для этого случая формула начнет адекватно работать если взять точку ближе к эллипсу, например, для точки с координатами x_0=69.1, y_0=0 приближение расстояния \approx 0.105.

Нас будут интересовать альтернативы приведенной в примере формулы, представляющие приближения минимального корня уравнения расстояний в виде явных функций параметров задачи. Желательно, чтобы эти формулы были универсальными в смысле применимости к общему виду уравнения эллипса (эллипсоида), а не только к представлению этого уравнения в каноническом виде. И, разумеется, нас интересуют границы применимости этих формул, т.е. оценки для ошибок приближения.

Будем решать эту задачу в следующем виде: представим искомое расстояние в виде ряда по параметру, который заведомо будет малым в окрестности рассматриваемого эллипса (эллипсоида). Таким параметром можно взять величину G_0= G(x_0,y_0) (соответственно G_0=G(x_0,y_0,z_0)). Итак,

d^2=\ell_1 G_0+\ell_2 G_0^2+\dots

Величину G_0 или |G_0 | иногда называют алгебраическим расстоянием точки от эллипса (эллипсоида), в отличие от истинного расстояния d, которое в этом случае называют геометрическим расстоянием.

Т

Теорема. Для эллипсоида

G(x,y,z)=\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1 = 0

первые два приближения расстояния до него от точки (x_0,y_0,z_0) задаются формулами

d_{(1)}=\frac{1}{2} \frac{|G_0|}{\sqrt{S_{4,0}}},
d_{(2)}=d_{(1)}\sqrt{1+\frac{1}{2} \frac{S_{6,0}}{S_{4,0}^2}G_0}

при условии, что радиканд в последней формуле неотрицателен. Здесь

G_0=G(x_0,y_0,z_0),\ S_{4,0} = \frac{x_0^2}{a^4}+\frac{y_0^2}{b^4}+\frac{z_0^2}{c^4} ;\ S_{6,0}=\frac{x_0^2}{a^6}+\frac{y_0^2}{b^6}+\frac{z_0^2}{c^6} \, .

Обобщение этого результата на случай квадрики в \mathbb R^n, не обязательно представленной в каноническом виде:

Т

Теорема. Для квадрики

G(X)=X^{\top}AX+2\,B^{\top}X-1=0 \ , (A=A^{\top})

первое приближение расстояния до нее от точки X_0 \ne -A^{-1}B задается формулой

d_{(1)} = \frac{1}{2}\cdot \frac{|G(X_0)|}{\sqrt{(AX_0+B)^{\top}({\bf A}X_0+B)}} \, ,

а второе — формулой

d_{(2)} = d_{(1)} \sqrt{1+\frac{1}{2}\cdot \frac{({\bf A}X_0+B)^{\top}A(AX_0+B)}{[(AX_0+B)^{\top}(AX_0+B)]^2}G(X_0)} \, .

§

Геометрическая интерпретация приближения d_{(1)} следующая. Эта величина совпадает с расстоянием от точки X_0 до гиперплоскости, получаемой линеаризацией G(X) в этой точке3):

G(X_0)+ \operatorname{grad} \, (G)\bigg|_{X=X_0} (X-X_0) = 0 \ .

Здесь вектор-строка \operatorname{grad} \, (G)\bigg|_{X=X_0} является градиентом функции G(X), вычисленном в точке X_0. Формула была предложена в [6] в качестве приближения расстояния от точки X_0 до произвольного алгебраического многообразия G(X)=0 в \mathbb R^n.

П

Пример. Найти приближения расстояний от точки (6,7,8) до эллипсоида

7\,x_1^2+6\,x_2^2+5\,x_3^2-4\,x_1x_2-4\,x_2x_3-3\,x_1-4\,x_2+5\,x_3-18=0\ .

Решение. Величина расстояния вычислена посредством уравнения расстояний в ПУНКТЕ; B_5 и B_6 — коэффициенты этого уравнения при z^1 и z^0. Заодно и еще для нескольких точек просчитаем:

\begin{array}{c|c|c|c|c|c} X_0 & \sqrt{-B_6/B_5} & d_{(1)} & d_{(2)} & d \\ \hline (6,7,8) & n/a & 5.525 & 8.779 & 9.590 \\ \hline (-4,4,3) & 3.390 & 2.877 & 3.526 & 4.732 \\ \hline (-2,-2,4) & 3.187 & 2.409 & 2.907 & 3.647 \\ \hline (1,-2,1) & 1.050 & 0.941 & 1.093 & 1.213 \\ \hline (1,1,-1) & 0.656 & 0.861 & 0.420 & 0.664 \end{array}

Эксперименты показывают, что приближение d_{(2)} лучше работает для точек, лежащих снаружи эллипсоида, нежели внутри него (в приведенной выше таблице (1,1,-1) как раз лежит внутри). Интересно понаблюдать поведение кривых d_{(1)}(x_0,y_0)=d и d_{(2)}(x_0,y_0)=d в окрестности эллипса.

П

Пример. Эллипс x^2/18^2+y^2/5^2=1 (красный). Кривые d_{(1)}=1,2,3 представлены на рисунке:

Наихудшие (в смысле ошибки приближения) точки кривой d_{(1)}=3 обозначена желтым. Так, для той, что лежит снаружи эллипса величина расстояния \approx 4.717.

Для приближения d_{(2)}, точки ветвей кривых d_{(2)}=1,2,3, лежащих снаружи эллипса, представлены на рисунке:

Истинное расстояние от наихудших точек кривой d_{(2)}=3 (обозначены голубым) равны \approx 2.932 и \approx 3.549. Все ветви кривой d_{(2)}=1 изображены на нижнем рисунке. Внутри эллипса имеются две ветви этой кривой

Расположенная внутри эллипса ветвь кривой d_{(2)}=2 не содержит внутри начала координат:

Источники

[1]. Uteshev A.Yu., Yashina M.V. Metric Problems for Quadrics in Multidimensional Space. J.Symbolic Computation, 2015, Vol. 68, Part I, P. 287-315. Текст ЗДЕСЬ (pdf)

[2]. Uteshev A.Yu., Goncharova M.V. Point-to-ellipse and point-to-ellipsoid distance equation analysis. J.Comput. Applied Math., 2018, Vol. 328, P. 232-251. Текст ЗДЕСЬ (pdf)

[3]. Розенфельд Б.А. Аполлоний Пергский. Изд-во МЦНМО. М. 2004.

[4]. Брiо и Буке. Аналитическая геометрiя. М.-СПб. Изданie книгопродавца-типографа М.О.Вольфа. 1868

[5]. Галеев Э.М., Тихомиров В.М. Оптимизация: теория, примеры, задачи. М. Эдиториал УРСС. 2000

[6]. Sampson P.D. Fitting conic sections to very scattered data: an iterative refinement of the Bookstein algorithm. Comput. Gr. Image Process., 1982, Vol. 18, P.97-108

1) В приведенном ниже выражении произведено сокращение на множитель a^{-8} b^{-8}.
2) В приведенном ниже выражении произведено сокращение на множитель a^{-12} b^{-12} c^{-12}.
3) Внимание: это — не касательная гиперплоскость!

2018/12/04 13:44 редактировал au