2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Ангеом и сфера: расположить точку на дуге.
Сообщение21.08.2018, 23:38 
Аватара пользователя


21/08/18
8
Здравствуйте, уважаемые участники форума, благодарю за проявленное внимание к заголовку проблемы. Излагаю свою проблему, одновременно с рассуждениями.
Дано: система трёхмерных прямоугольник координат. Оси 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 - число, сколько всего точек будет). Я не знаю, откуда мне получить дальнейшую информацию для решения полученной системы. Мне нужны именно координаты точек.
Возможно, существует какой-то более простой путь, но я его не знаю, если он есть, пожалуйста, скажите, где мне о нём прочитать? Я будущий первокурсник, мне ещё не читали дисциплин, но я с удовольствием изучу любой раздел, который поможет решить эту задачу, если мне его назовут. Буду премного благодарен, если мне подскажут не только раздел, но и закон, который стоит изучить.

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

 Профиль  
                  
 
 Re: Ангеом и сфера: расположить точку на дуге.
Сообщение22.08.2018, 00:01 
Заслуженный участник
Аватара пользователя


01/09/13
4656
logunov в сообщении #1333754 писал(а):
тогда получим систему:

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

 Профиль  
                  
 
 Re: Ангеом и сфера: расположить точку на дуге.
Сообщение22.08.2018, 00:15 
Заслуженный участник


27/04/09
28128
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 --

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

 Профиль  
                  
 
 Re: Ангеом и сфера: расположить точку на дуге.
Сообщение22.08.2018, 00:36 
Заслуженный участник
Аватара пользователя


01/09/13
4656
arseniiv в сообщении #1333762 писал(а):
С явными поворотами точно будет вычислительно не хуже?

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

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

-- 22.08.2018, 00:39 --

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

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

 Профиль  
                  
 
 Re: Ангеом и сфера: расположить точку на дуге.
Сообщение22.08.2018, 00:58 
Заслуженный участник


27/04/09
28128
Geen в сообщении #1333764 писал(а):
По сравнению с чем? :-)
Послал ЛС. (Если вы о двумерной матрице поворота, то да, разницы нет, что-то я не подумал про двумерную.)

 Профиль  
                  
 
 Re: Ангеом и сфера: расположить точку на дуге.
Сообщение22.08.2018, 07:45 


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

 Профиль  
                  
 
 Re: Ангеом и сфера: расположить точку на дуге.
Сообщение03.11.2018, 01:10 
Аватара пользователя


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

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

Как заметил господин 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, на которую я потратил ни многим, ни малым три недели. Именно благодаря ей я смог лучше подумать о пространстве.
Я правда благодарен обоим господам за оказанную помощь в размышлениях. Спасибо.

 Профиль  
                  
 
 Re: Ангеом и сфера: расположить точку на дуге.
Сообщение03.11.2018, 02:14 
Аватара пользователя


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

 Профиль  
                  
 
 Posted automatically
Сообщение03.11.2018, 02:31 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение03.11.2018, 02:51 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Ангеом и сфера: расположить точку на дуге.
Сообщение03.11.2018, 12:11 
Заслуженный участник
Аватара пользователя


01/09/13
4656
logunov в сообщении #1351283 писал(а):
не заметил эту опечатку

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

logunov в сообщении #1351275 писал(а):
Задача, как мне кажется, решена, но, к сожалению, решение проверить некому.

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

 Профиль  
                  
 
 Re: Ангеом и сфера: расположить точку на дуге.
Сообщение03.11.2018, 19:39 
Аватара пользователя


21/08/18
8
Исправленная матрица, большое спасибо за указанную неточность.
$$\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}$$

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group