Ангеом и сфера: расположить точку на дуге.

[logunov]

Здравствуйте, уважаемые участники форума, благодарю за проявленное внимание к заголовку проблемы. Излагаю свою проблему, одновременно с рассуждениями.
Дано: система трёхмерных прямоугольник координат. Оси z и x расположены в горизонтальной плоскости, ось z направлена от нас, ось x - вправо. Ось y - вверх.
В системе координат располагается сфера радиуса R. Центр сферы совпадает с началом координат. Даны две произвольные точки сферы (но гарантируется, что они не диаметрально противоположные). У данных точек известны координаты в заданной системе координат.
Необходимо: на меньшей дуге, соединяющей две точки, упорядоченно расположить 10 (100, 1000... n) точек на равном расстоянии друг от друга (не в строгом смысле, а приблизительно) и получить координаты этих точек.
Зачем: по этим точкам будет двигаться объект, это нужно для плавного движения вдоль поверхности сферы из точки 1 в точку 2.

Мои измышления:
Пусть для определённости координаты первой точки $P_1 = \left\lbrace x_1, y_1, z_1 \right\rbrace$ и $P_2 = \left\lbrace x_2, y_2, z_2 \right\rbrace $.
Тогда, мы можем провести векторы $ \vec{p_1}& и & \vec{p_2} $ с началом в системе координат и концом в указанных точках.
Тогда, пусть угол между этими векторами равен $\varphi$, он же равен $ a/R $, где a - длина искомой дуги, а R - радиус сферы, данный из условия (источник знания - методичка, ссылку дам по требованию).
Тогда: $\cos{ \varphi } = \cos {\frac{a}{R}} = \frac{x_1 x_2 + y_1y_2 + z_1z_2}{R^2} & (я здесь сразу подставляю квадрат радиуса, потому что длины векторов равны радиусу, следовательно их произведение - квадрат радиуса), откуда:
& a = \arccos({ \frac{x_1x_2 + y_1y_2 + z_1z_2}{R^2}})R &
Поскольку дуга - это способ задать угол (? я так предполагаю, может быть у меня здесь ошибка), тогда разобьём дугу на нужное число кусочков. Будем двигаться от точки $P_1 = \left\lbrace x_1, y_1, z_1 \right\rbrace$ в направлении $P_2 = \left\lbrace x_2, y_2, z_2 \right\rbrace $, делая шаг по дуге, равный $ $\frac{ak}{n}$, где $k$ и $n$ целые числа, $k>2$ (чтобы не спутать индексы). Делаем это до тех пор, пока $k$ не будет равно $n$ (придём в $P_2$ в этот момент), тогда на первом шаге получаем пару точек:
$P_1 = \left\lbrace x_1, y_1, z_1 \right\rbrace$ и $G_k = \left\lbrace x_k, y_k, z_k \right\rbrace$, аналогично сделаем их векторами из начала координат: $vec{p_1} и \vec{g_k}$, тогда длина дуги, стягивающей их, равна: $\frac{ak}{n}$, тогда получим систему:

$$\left\{ \begin{array}{rcl} a =\arccos({ \frac{x_1x_2 + y_1y_2 + z_1z_2}{R^2}})R\\ \frac{ak}{n}= \arccos({\frac{x_1x_k + y_1y_k + z_1z_k}{R^2}})R\\ \end{array} \right.$$

Соответственно, потом катая точка соединятся с катой-плюс-один точкой, и так до конечной точки маршрута.
Моя проблема заключается в следующем: я получил два уравнения с тремя неизвестными $ x_k, y_k, z_k уже для первой же точки (n - число, сколько всего точек будет). Я не знаю, откуда мне получить дальнейшую информацию для решения полученной системы. Мне нужны именно координаты точек.
Возможно, существует какой-то более простой путь, но я его не знаю, если он есть, пожалуйста, скажите, где мне о нём прочитать? Я будущий первокурсник, мне ещё не читали дисциплин, но я с удовольствием изучу любой раздел, который поможет решить эту задачу, если мне его назовут. Буду премного благодарен, если мне подскажут не только раздел, но и закон, который стоит изучить.

Большое спасибо за внимание!

[Geen]

logunov в сообщении #1333754 писал(а):

тогда получим систему:

Нет - надо просто повернуть начальный вектор на угол $\varphi/n$ относительно векторного произведения начального и конечного векторов (повернуть в плоскости, в которой лежат заданные вектора).
Или, если хотите, третье уравнение должно выражать факт, что все три вектора лежат в одной плоскости.
Рассмотрите, для начала, случай когда заданные вектора лежат в плоскости XY.

[arseniiv]

logunov в сообщении #1333754 писал(а):

упорядоченно расположить 10 (100, 1000... n) точек на равном расстоянии друг от друга (не в строгом смысле, а приблизительно)

В каком смысле приблизительно? Допускается какая-то погрешность в расположении точек относительно точного? Тогда важно, какая. Вообще нетрудно найти и точное решение.

logunov в сообщении #1333754 писал(а):

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

Это очень радует. Тогда посоветовал бы сначала забыть про координаты — да, в них всё в конечном итоге и считается, но всё по порядку — и написать бескоординатные формулы.

Способ, который предпочёл бы я: согласитесь, удобно тыкать в разные точки дуги (а лучше целой окружности), имея её параметрическое уравнение. Наверно, вы видели его для плоскости и в координатах: $(x, y) = R(\cos t,\sin t)$, где $t$ — полярный угол интересующей точки окружности. Его можно записать бескоординатно: $\mathbf r = R(\mathbf i\cos t + \mathbf j\sin t)$, где $\mathbf i,\mathbf j$ — орты декартовой системы. Но, внимание, на самом деле нам важно только то, чтобы между $\mathbf i,\mathbf j$ был прямой угол и их длины были единичными — и, разумеется, чтобы они лежали в плоскости окружности — а с координатной системой им быть связанными не нужно. Параметр $t$ отсчитывает угол, начиная от направления $\mathbf i$ в сторону направления $\mathbf j$.

Сам способ, как можно догадаться, состоит в том, чтобы найти пару подходящих векторов по началу и концу дуги, радиус-векторы которых не обязательно ортогональны. Это делается, например, ортогонализацией Грама—Шмидта. И останется лишь разобраться в нужных значениях $t$. Косинусы и синусы можно не считать по много раз, используя формулы суммы углов, позволяющие находить косинус и синус для очередной точки по предыдущим.

Этого должно хватить, а если что-то не получится, спрашивайте.

Geen
С явными поворотами точно будет вычислительно не хуже?

-- Ср авг 22, 2018 02:18:01 --

В частности, векторное произведение — это небольшой чит (вращение бывает в любом евклидовом пространстве, а векторное произведение только в трёхмерном ориентированном). Плоскость вращения дана почти явно, и вроде не нужно было бы идти в обход.

[Geen]

arseniiv в сообщении #1333762 писал(а):

С явными поворотами точно будет вычислительно не хуже?

По сравнению с чем?

Вычислительно видится навскидку одна проблема - косинус малого угла будет строго равен 1, и матрица поворота в большой степени будет заметно неортогональной (та же проблема будет и с формулами суммы углов).
Но для визуализации, в пределах 1000 шагов, без выхода/продолжения за конечный вектор, как кажется, проблем быть не должно при любом способе...

-- 22.08.2018, 00:39 --

arseniiv в сообщении #1333762 писал(а):

Плоскость вращения дана почти явно, и вроде не нужно было бы идти в обход.

Кажется, мы говорим об одном и том же - надо вычислить матрицу поворота (а лучше за вычетом единичной).

[arseniiv]

Geen в сообщении #1333764 писал(а):

По сравнению с чем?

Послал ЛС. (Если вы о двумерной матрице поворота, то да, разницы нет, что-то я не подумал про двумерную.)

[wrest]

logunov
Я бы, вслед за Geen, посоветовал бы вам рассмотреть сначала плоский случай: дана окружность, две точки на ней и надо вычислить сколько-то лежащих между ними. Этот случай проще нарисовать и проще над ним подумать, а по сути ничего не меняется.

[logunov]

Большое спасибо всем за добрые советы, воспользовался каждым поочерёдно, в меру своих сил, и понял, что нужно немного "прокачаться" в математике. К сожалению, наименее понятны мне оказались сферические координаты и мысль о том, что они описывают те же самые точки пространства, что и трёхмерная декартова система координат никак не приживалась в моей голове.
Ушло несколько месяцев, чтобы наконец-то осознать, что в данном случае не уравнения задают пространство, а это лишь способ задать точку, в каком-то пространстве, и, когда мы изучаем пространства, то ищем способы задать в них точку. Наоборот, конечно, тоже возможно, как я выяснил несколько позднее, но это несколько выходило за рамки поставленной задачи, поэтому я отложил изучение обратного вопроса на неопределённый срок.

Прошу простить долгое вступление, я перейду к решению, которое дало мне искомый результат.

Как заметил господин Geen, одно из основных условий, которых не хватало в исходных вычислениях - принадлежность вектора плоскости, я построил плоскость, проходящую через два вектора, отсекающую окружность в нашей сфере.

Пусть вектор $\vec{a}$ задан координатами $(x_1, y_1, z_1)$, аналогично $\vec{b}$ задан координатами $(x_2,y_2,z_2)$, тогда можно построить плоскость через два вектора и точку, где точка - начало координат. Далее я рассматриваю верхнюю полусферу, т.е плоский угол до 180 градусов.
1) Очевидно, что данные векторы неколлинеарны, т.к проходят через одну точку - начало координат (я вот здесь хочу сделать оговорку, я не совсем уверен, можно ли говорить, что векторы "проходят через точку", ведь на самом деле, как я выяснил, векторы - это просто некий набор чисел, имеющих направление и связанных с пространством, исходный набор чисел не содержит в себе данные о "начале", а только лишь о том, куда указывает "конец" вектора, и какие его "проекции"(?) на базисные оси).
2) У меня есть три точки: две - концы векторы, указывающие на поверхность сферы, и одна - начало координат, тогда можно построить плоскость по трём точкам (я использовал именно этот вариант, а (1) написал, потому что у меня есть насчёт его правильности сомнения, в отличие от (2), но быть может он имеет место быть).

$$\begin{pmatrix} (x-x_0) (x_1-x_0) (x_2-x_1) \\ (y-y_0) (y_1-y_0) (y_2-y_1) \\ (z-z_0) (z_1 - z_0) (z_2 - z_1) \end{pmatrix}$$

Здесь я не нашёл обоснования этой формулы в строгом виде (поделитесь, пожалуйста, литературой, если это возможно), но для себя я доказал правомочность так:
Так как нам дана матрица, то каждый вектор-столбец этой матрицы описывает вектор в пространстве, тогда, пусть векторы: $MN, MK, KN$ соответственно равны: $(x - x_0, y-y_0, z-z_0), (x_1 - x_0, y_1 - y_0, z_1 - z_0), (x_2-x_1,y_2-y_1, z_2-z_1)$, тогда, составим из этих векторов матрицу, и, если её определитель равен нулю, то это означает, что размерность фигуры, образованной векторами, меньше размерности пространства, в нём построенном, в моём случае это будет параллелограмм. Здесь ещё необходимо, кажется, проверить, что ранг матрицы равен двум, потому что если ранг матрицы будет единица, то я получу линию, а если ноль, то точку(?), но, кажется, я должен быть уверен в этом, так как беру заведомо не совпадающие точки.

Конечное уравнение я получу в виде $Ax+By+Cz+D = 0$.

Немного помучившись с определителем общего вида я получил следующее:
$A = (-y_2 + y_0) \cdot (-z_0 + z_1) + (z_2 - z_0) \cdot (-y_0 + y_1)$
$B = (-z_2 + z_0) \cdot (x_1 - x_0) + (-z_0 + z_1) \cdot (-x_0 + x_2)$
$C = (y_2 - y_0)\cdot(x_1 - x_0) + (x_0 - x_2)\cdot(-y_0 + y_1)$
$D = -(-y_2 + y_0)\cdot(-z_0 + z_1)\cdotx_0 - (z_2 - z_0)\cdot x_0 \cdot (-y_0 + y_1) -y_0 \cdot (-z_2 + z_0) \cdot (x_1 - x_0) - y_0 \cdot (-z_0 + z_1) \cdot (-x_0 + x_2) -(y_2 - y_0) \cdot z_0 \cdot (x_1 - x_0) - z_0 \cdot (x_0 - x_2) \cdot (-y_0 + y_1)$

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

Пропущу дальнейшие идеи. В общем, здесь у меня было два пути: Исследовать два вектора в плоскости, а вернее, разделить угол между ними на нужное количество частей, и двигать исходный угол на необходимый градус с помощью матрицы поворота (спасибо, г-н Geen, но в первый раз, читая ваше сообщения, я даже не имел представления о том, что такое линейная алгебра, слово "матрица поворота" мне тогда мало что сказало (даже с г-ном гуглом), но позже, перечитав Ваше сообщения, я понял, что нужно искать), либо найти более производительный способ. Я его нашёл: кватернион-матричное преобразование.
Изучив это преобразование, я узнал, что можно вращать точку вокруг оси, это именно то, что мне нужно. Но какую ось вращения взять, чтобы ничего не сломать? Перпендикуляр к плоскости! (осенило меня спустя неделю)
Уравнение нормали к плоскости будет иметь вид $\vec{n} = (A,B,C) $ Я могу пренебречь требование прохождения через какую-то конкретную точку, потому что моя сферы лежит в начале координат своим центром, в противном случае необходимо было бы потребовать уравнение прямой, проходящей через точку-центр сферы.

Тогда, я могу задать кватернион поворота, как $ q = (w, \vec{t}) $, где $ w = \cos(\varphi), \vec{t} = \sin(\varphi) \cdot \vec{n}$, где $\varphi $ половина от нужного мне угла поворота.

Тогда, задав такой кватернион, я могу его преобразовать в матрицу поворота, в которой не будет проблемы шарнирного замка (gimble lock), по следующему правилу:

$$\begin{pmatrix} 1-2 \cdot (A'^2+B'^2)\qquad 2 \cdot (A' \cdot B' - C' \cdot w)\qquad 2 \cdot (A' \cdot C' + B' \cdot w) \\ 2 \cdot (A' \cdot B' - C' \cdot w)\qquad 1-2(A'^2+C'^2) \qquad 2 \cdot (B' \cdoC C' - A' \cod w) \\ 2 \cdot (A' \cdot C' - B' \cdot w) \qquad 2(B' \cdot C' + A' \cdot w) \qquad 1-2 \cdot (A'^2 - B'^2) \end{pmatrix}$$

Где $A', B', C' $ соответственно равны $A\sin(\varphi), B\sin(\varphi), C\sin(\varphi)$
Осталось самое главное, переход от точки к точки:
1) Беру начальную точку
2) Беру конечную точку
3) Нахожу угол между векторами в плоскости
4) Делю этот угол на нужное количество мне частей
5) Записываю координаты точки старта в виде вектор-столбца
6) Нахожу уравнение направляющего вектора (по совместительству прямой, перпендикулярной плоскости проходящей через точку 0)
7) Создаю кватернион q, в который подаю свой угол по правилу: $\varphi = \frac{\alpha \cdot k }{2 \cdot n},$ где $n$ - количество частей, на которые я поделил исходный угол, $k$ - текущая итерация цикла.
8) Умножаю вектор столбец на кватерионную матрицу поворота (вектор-столбец справа), получаю новый вектор-столбец, с координатами исходной точки. Увеличиваю $k$ на единицу. Записываю полученные координаты в массив.


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


Большое спасибо за мотивацию и помощь, ваши идею подтолкнули меня на мысль, в каком направлении стоит искать и размышлять, однако, я совершенно не понял ортогонализацию Грама-Шмидта, возможно, чуть позже смогу понять.
Честно говоря, я не очень глубоко понимаю, как работает кватернион, лишь представляю себе это как стереографическую проекцию четырёхмерной сферы в трёхмерное пространство, и, отсутствие шарнирного замка возникает из-за того, что для всякой точки проекции определена точка в проецируемого объекта, но не наоборот, поэтому мы можем однозначно задать любую точку без вырождений, но вот если бы мы вращали объект в четырёхмерном пространстве, то нам, вероятно, понадобился пятимерный объект для такого же трюка?

К сожалению, я не нашёл литературы, в которой излагались бы приёмы, использованные мной, возможно, у кого-то из вас будут рекомендации.


p.s Не смотря на то, что метод г-на Geen помог мне в идее практических рассуждений, на верную мысль о представлении пространства меня натолкнула подсказка г-на arseniiv, на которую я потратил ни многим, ни малым три недели. Именно благодаря ей я смог лучше подумать о пространстве.
Я правда благодарен обоим господам за оказанную помощь в размышлениях. Спасибо.

[logunov]

A,B,C - в переходе к матрице поворота умножены на $\sin\varphi $, не заметил эту опечатку, а кнопка редактирования уже исчезла.

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- поправьте то, что требуется.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Geen]

logunov в сообщении #1351283 писал(а):

не заметил эту опечатку

Кажется, у Вас там ещё опечатки... - по крайней мере, последняя матрица выглядит "несимметричной" относительно $A,\ B,\ C$

logunov в сообщении #1351275 писал(а):

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

В большинстве случаев в жизни Вам придётся делать проверки самому... В данном случае стоит проверять: 1) "обычные" случаи; 2) близкие точки; 3) почти диаметрально-противоположные; 4) число промежуточных точек более 100 миллионов; 5) намотать по сфере несколько кругов. И у Вас есть очень хороший "критерий" проверки: попадание последней вычисленной точки во вторую заданную.

[logunov]

Исправленная матрица, большое спасибо за указанную неточность.

$$\begin{pmatrix} 1-2(B'^2+C'^2) \qquad 2(A'\cdot B' - C'\cdot w) \qquad 2(A' \cdot C' - B' \cdot w)\\ 2(A' \cdot B' + C' \cdot w) \qquad 1-2(A'^2+C'^2) \qquad 2(B' \cdot C' - A' \cdot w) \\ 2(A' \cdot C' + B' \cdot w) \qquad 2(B' \cdot C' - A' \cdot w) \qquad 1-2(A'^2+B'^2) \end{pmatrix}$$

Я, кажется, проверил свои рассуждения и выглядит, что решение рабочее. Правда, я проверял машинно, уж слишком много вычислений для ручной проверки. Спасибо за наставление про проверку решений.