Инструменты сайта


§

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


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

В настоящем разделе мы проанализируем следствия для $ \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] , $$ то уравнения его эквидистант: \begin{align*} x&=\left(a\pm \frac{bh}{\sqrt{a^2 \sin^2 t+b^2 \cos^2 t}} \right)\cos \, t,\\ 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] . \end{align*} Знаки должны быть согласоваными.

П

Пример. Эквидистанты эллипса $ 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} \ .$$

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

Т

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

$$ 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 $.

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

Т

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

$$ 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 $ берутся из формулировки теоремы $ 6 $ с осуществлением подстановки $ 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 $, которое в этом случае называют геометрическим расстоянием.

Т

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

$$ 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 $, не обязательно представленной в каноническом виде:

Т

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

$$ 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)
Внимание: это — не касательная гиперплоскость!
algebra2/optimiz/distance/appolonij.txt · Последние изменения: 2020/07/14 17:01 — au