Поиск ортогонального преобразования для системы МТ

[madschumacher]

Добрый день. Возможно, тему надо было бы разместить в математической части форума, но она достаточно простая и банальная, и наверное мне её проще сформулировать в физических терминах.

Есть система А из нескольких материальных точек (МТ), заданных своими векторами в Декартовых координатах $\mathbf{r}_i = (x_i, \ y_i, \ z_i)^\dagger$. И есть эквивалентная им с точностью до ортогонального преобразования система МТ Б, заданных радиус-векторами $\mathbf{r}_i' = (x_i', \ y_i', \ z_i')^\dagger$. Эквивалентность систем МТ известна из того, что $\forall \ i,j \ r_{ij} \approx r_{ij}'$, где $r_{ij}=|\mathbf{r}_i-\mathbf{r}_j|$ (то бишь расстояния между точками одинаковые).

Так вот задача: найти, является ли ортогональное преобразование $\mathbb{S}: \ \mathbb{S}\mathbf{r}_i = \mathbf{r}_i'$, связывающее А и Б собственным или несобственным.

Как я понимаю, самый адекватный способ решить эту задачу -- это найти (хотя бы приближенно) матрицу $\mathbb{S}$ и посмотреть на её определитель. Если он больше нуля, то собственное, а если меньше -- несобственное?

Приближение для $\mathbb{S}$ я пробовал искать из тупого метода наименьших квадратов: $\Phi = \sum_i \left( \mathbb{S}\mathbf{r}_i - \mathbf{r}_i' \right)^2 \rightarrow \min$. Саму матрицу при этом я представлял просто в виде симметричной матрицы (условия для ортогональности делают МНК нелинейным, возиться с этим было лень, тем более, что и не умею ): $\mathbb{S}=\begin{pmatrix} s_{xx} & s_{xy} & s_{xz} \\ s_{xy} & s_{yy} & s_{yz}\\ s_{xz} & s_{yz} & s_{zz} \end{pmatrix}$. Соответственно $\frac{\partial \Phi}{\partial s_{ab}}=0$ по всем $a, \ b = x, \ y, \ z$ дают систему из 6ти линейных уравнений на элементы вектора $\mathbf{s}=( s_{xx}, \ s_{xy}, \ s_{xz}, \ s_{yy}, \ s_{yz}, \ s_{zz} )^\dagger$:

$\begin{pmatrix} \sum_i x_i^2 & \sum_i x_i y_i & \sum_i x_i z_i & 0 & 0 & 0 \\ \sum_i x_i y_i & (\sum_i x_i^2 + \sum_i y_i^2) & \sum_i y_i z_i & \sum_i x_i y_i & \sum_i x_i z_i & 0 \\ \sum_i x_i z_i & \sum_i y_i z_i & (\sum_i x_i^2 + \sum_i z_i^2) & 0 & \sum_i x_i y_i & \sum_i x_i z_i \\ 0 & \sum_i x_i y_i & 0 & \sum_i y_i^2 & \sum_i y_i z_i & 0 \\ 0 & \sum_i x_i z_i & \sum_i x_i y_i & \sum_i x_i y_i &(\sum_i y_i^2 + \sum_i z_i^2) & \sum_i y_i z_i \\ 0 & 0 & \sum_i x_i z_i & 0 & \sum_i y_i z_i & \sum_i z_i^2 \end{pmatrix} \cdot \mathbf{s} = \begin{pmatrix} \sum_i x_i x_i' \\ \sum_i x_i y_i' + \sum_i y_i x_i' \\ \sum_i x_i z_i' + \sum_i z_i x_i' \\ \sum_i y_i y_i' \\ \sum_i y_i z_i' + \sum_i z_i y_i' \\ \sum_i z_i z_i' \end{pmatrix} $

Далее это все решается численно методом Гаусса с выбором ведущего элемента по столбцу и последующим обратным ходом. И для несобственного преобразования получаю определители около -0.2, а для собственного (мало того, например, для заведомо единичной матрицы) -- вырожденную матрицу!
Всё выводил руками, но проверял СЛУ 2 раза различными способами вывода (в лоб расписав $\Phi$ по всем компонентам и в матричной форме). Хотя может и не в ней изъян.

В общем, Люди Добрые, плиз помогите кто чем может....

[svv]

Следующий способ подойдёт, даже если имеется неоднородное слагаемое (сдвиг).
Найдите смешанное произведение $[\mathbf r_2-\mathbf r_1, \mathbf r_3-\mathbf r_1, \mathbf r_4-\mathbf r_1]$ для точек исходной системы.
Найдите смешанное произведение $[\mathbf r'_2-\mathbf r'_1, \mathbf r'_3-\mathbf r'_1, \mathbf r'_4-\mathbf r'_1]$ для соответствующих точек штрихованной системы.
Если знаки одинаковые, преобразование собственное.
Если знаки разные, преобразование несобственное.
Если нуль или очень малое число, выберите другие точки.

Короче говоря, сравните знаки соответствующих друг другу ориентированных объемов.

[madschumacher]

А смешанное произведение $[\mathbf{a}, \mathbf{b}, \mathbf{c}]$ -- это $\mathbf{a} \cdot [\mathbf{b} \times \mathbf{c}]$?

[svv]

Да. Равно определителю от компонент:
$\mathbf{a} \cdot [\mathbf{b} \times \mathbf{c}]=\begin{vmatrix}a_x&b_x&c_x\\a_y&b_y&c_y\\a_z&b_z&c_z\end{vmatrix}$
Геометрический смысл: ориентированный объём (со знаком, зависящим от того, правая или левая это тройка) параллелепипеда, построенного на этих трех векторах.

[madschumacher]

Спасибо большое.
Очень красивая и простая идея. Стыд мне и позор за то, что не додумался.
Еще раз спасибо

[svv]

Рад был помочь.
Если Вы совершенно уверены в том, что никаких сдвигов нет, и $\mathbf r'_i$ получаются из $\mathbf r_i$ умножением на матрицу, то можно обойтись тремя векторами: сравнить знак $[\mathbf r_1\mathbf r_2\mathbf r_3]$ и $[\mathbf r'_1\mathbf r'_2\mathbf r'_3]$. Вычитание радиус-вектора дополнительной точки нужно было для «нейтрализации» возможного сдвига.

[madschumacher]

Да, сдвиги изначально устраняются (работа идет в системе, где ЦМ -- это начало отсчета). Спасибо большое вновь. Буду пробовать реализовать)

[Munin]

В неприятном случае, если система точек имеет какую-то (отражательную, кажется) симметрию, задача не решается: существуют и собственное, и несобственное искомые ортогональные преобразования.

[madschumacher]

В смысле когда система точек плоская (или хуже линейная)?
В случае конкретной этой задачи подобные ситуации не важны. Сейчас реализовал алгоритм, который пробегает все 3ки точек, и если среди них не нашлось комбинации с ненулевым параллелепипедом, то он считает эти комбинации равными. На тестовой задаче вроде показывает приличные результаты.

Для задачи важно отсеять все пары, которые могут переводиться друг в друга собственным ортогональным преобразованием. Если есть еще и несобственное, то это не особо интересует шерифа.

[arseniiv]

madschumacher в сообщении #1127669 писал(а):

В смысле когда система точек плоская (или хуже линейная)?

Не обязательно плоская. Представьте вершины куба или октаэдра (и т. п.).

[madschumacher]

Ой, а можно тогда сказать, какие будут следствия для предложенного алгоритма расчета ориентированного объема параллелепипеда? А то я что-то не соображу, будет ли он лажать в этих случаях?

[arseniiv]

Может быть, это даже ерунда. Если понимать то, что вы написали, как сначала вышло, то, получается, вам известно, какая точка первого набора переходит в какую точку второго? Тогда никакой неоднозначности не будет в моих случаях, а вот в случае тройки точек, лежащих на плоскости симметрии, действительно может получиться нехорошо. Сия операция:

svv в сообщении #1127639 писал(а):

сравнить знак $[\mathbf r_1\mathbf r_2\mathbf r_3]$ и $[\mathbf r'_1\mathbf r'_2\mathbf r'_3]$

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

[madschumacher]

Нас особо не волнует существование эквивалентных по симметрии точек. Главное, чтобы не существовало одинакового одновременного поворота системы координат для всех точек с совмещением картинки.

[arseniiv]

(Несвоевременное продолжение.) Даже если найти такую тройку, которая переходит не в себя, она всё равно может получаться поворотом и потом отражением относительно плоскости, проходящей через новое положение этой тройки. А вот если взять четыре некомпланарные точки, должно сработать. Придётся вернуться к исходному алгоритму svv. А если некомпланарные точки не нашлись, то и разницы никакой не будет!

Некомпланарность проверяется как раз произведениями вида

svv в сообщении #1127630 писал(а):

$[\mathbf r_2-\mathbf r_1, \mathbf r_3-\mathbf r_1, \mathbf r_4-\mathbf r_1]$

(чем меньше объём, натянутый на эти три вектора, тем «компланарнее» четвёрка), так что алгоритм работает без изменений, и только если везде получаются нули или маленькие числа, можно перейти к упрощённому для тройки. Хотя стоило бы ещё проверить, не близки ли три точки к коллинеарности… (векторным произведением, от которого можно взять, например, модуль).

[madschumacher]

Наверное, если возвращаться к этому алгоритму, но в системе, где ЦМ -- начало отчета, то 4я точка не нужна, поскольку через ЦМ заведомо проходят все элементы симметрии и он в этом смысле лучше любой 4й точки.