Весьма нетривиальная оптимизация

[Dmitriy40]

Про варианты матриц преобразования вот тут есть готовый список. А тут много разных готовых матрицы для разных вариантов поворота. Поворот вокруг произвольной оси и точки делается как композиция смещений, поворотов (переводящих фигуру в начало координат и поворачивающих оси в нужном направлении), желаемого поворота, и обратных поворотов и смещений. Зеркальное отражение выполняется как масштабирование с коэффициентом $-1$. Получается цепочка умножений простых матриц, зависящая лишь от параметров движения и рассчитываемая лишь однажды, в итоге получается одна матрица преобразования координат, которая и используется для вычислений координат всех точек.
Можно разделить движение на поворот и смещение и считать их отдельно, но смысла в этом не вижу, вычисления не ускоряются.
Для получения обратного преобразования нужна именно обратная матрица, а не транспонированная.

[vpb]

(Оффтоп)

Не следует злоупотреблять цитатами и вставлять чужое сообщение целиком. Часто достаточно выделить пару строчек, чтоб стало понятно, о чем речь идет.

Вращения это и есть движения, сохраняющие ориентацию. Бывают переворачивающие ориентацию (отражения).

-- 10.12.2018, 21:28 --

Википедия --- источник крайне ненадежный. Если хочешь что-либо понять и правильно сделать, надо самому разобраться по учебнику, и возможно посоветоваться со знающими людьми. А иначе весьма вероятно впасть в заблуждение.

-- 10.12.2018, 21:38 --

Я думаю, стоит написать общую формулу для движения, в трехмерном евклидовом пространстве. Если что непонятно, спрашивайте.

Значит, фиксируем прямоугольную декартову систему координат. Каждую точку будем изображать столбцом ее координат $\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}$. Тогда общее движение задается формулой

$$\Phi x=Ax+b\,, $$

где $A$ --- ортогональная матрица, $b$ --- произвольный вектор. Движение является собственным, если $\det A=1$ ( $\det$ --- определитель). Обратное движение дается формулой (проверьте!) $\Phi^{-1}x=A^{-1}x-A^{-1}b$.

[_genius_]

Dmitriy40 в сообщении #1360322 писал(а):

Про варианты матриц преобразования вот тут есть готовый список. А тут много разных готовых матрицы для разных вариантов поворота. Поворот вокруг произвольной оси и точки делается как композиция смещений, поворотов (переводящих фигуру в начало координат и поворачивающих оси в нужном направлении), желаемого поворота, и обратных поворотов и смещений. Зеркальное отражение выполняется как масштабирование с коэффициентом $-1$. Получается цепочка умножений простых матриц, зависящая лишь от параметров движения и рассчитываемая лишь однажды, в итоге получается одна матрица преобразования координат, которая и используется для вычислений координат всех точек.
Можно разделить движение на поворот и смещение и считать их отдельно, но смысла в этом не вижу, вычисления не ускоряются.
Для получения обратного преобразования нужна именно обратная матрица, а не транспонированная.

Здесь есть одна проблема - я не знаю, насколько мне смещать, пока не поверну, попробую опять-таки показать на своем примитивном двумерном рисунке

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

[Dmitriy40]

_genius_ в сообщении #1360331 писал(а):

Здесь есть одна проблема - я не знаю, насколько мне смещать, пока не поверну,

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

[_genius_]

vpb в сообщении #1360325 писал(а):

Значит, фиксируем прямоугольную декартову систему координат. Каждую точку будем изображать столбцом ее координат $\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}$. Тогда общее движение задается формулой

$$\Phi x=Ax+b\,, $$

где $A$ --- ортогональная матрица, $b$ --- произвольный вектор. Движение является собственным, если $\det A=1$ ( $\det$ --- определитель). Обратное движение дается формулой (проверьте!) $\Phi^{-1}x=A^{-1}x-A^{-1}b$.

Я вам верю, но если хотите $\Phi^{-1}x'=A^{-1}(Ax+b)-A^{-1}b = x + A^{-1}b - A^{-1}b = x$.

В общем добавил это в код, к сожалению по-прежнему вылезаю за границы, пусть теперь и не так сильно, максимальная координата $z = 261.75$ смещенного первого тела при границе ящика вокруг оригинального второго тела $z = 229$. Возможно я все-таки где-то просчитался с границами ящиков, т.к. ошибки в расчетах я не нахожу.
Но возможно я просто не понимаю что творю. Вот пример для первых 5 точек с вращением на 30 градусов вокруг оси $x$:



Как я уже говорил выше, смещение второго тела происходит в крайний угол (т.е. минимальные $x=-73, y=-106, z=-35$ и ещё $+0.5$ чтобы с запасом) ящика вокруг первого.

[vpb]

_genius_ в сообщении #1360345 писал(а):

Я вам верю, но если хотите $\Phi^{-1}x'=A^{-1}(Ax+b)-A^{-1}b = x + A^{-1}b - A^{-1}b = x$

Да, это правильно. Почему у Вас не получаются правильные результаты, я сказать не могу. Понять что-то из результатов работы чужой программы --- это, как правило, дело вообще очень трудное. Придется Вам самому разбираться. Книжки читать, самому обдумывать, чтоб быть уверенным, что Вы кодируете именно то, что надо. Могу только дать такой совет: сначала разобраться со всей геометрией и программой в плоском, двумерном то есть, случае, а уже потом делать объемный.

-- 11.12.2018, 00:10 --

vpb в сообщении #1360348 писал(а):

Книжки читать, самому обдумывать, чтоб быть уверенным

понимаете, когда Вы убедитесь в том, что, например, формула $\Phi x=Ax+b$ правильна, не через то, что я Вам об этом сказал, и не через результат работы компьютера, а собственным пониманием, то у Вас на многое глаза откроются.

[_genius_]

Решил визуализировать (красная точка - начало координат, бирюзовый ящик вокруг первого тела, темно-синий ящик вокруг второго тела):
https://ibb.co/JtPpWS8
https://ibb.co/LC6fqPx
https://ibb.co/vHTgW1S
https://ibb.co/nbwCSJ8
https://ibb.co/VSYNqCv

И не пожалел. Интересно что ящики оказались визуально больше чем я ожидал. Но это не беда, лучше чуть больше, чем чуть меньше.
А вот что мне совсем не нравится это то что первое тело оказывается отнюдь не там где я рассчитывал его увидеть, вот ещё финальная стадия с другого ракурса: https://ibb.co/qn7t6yn
Относительное положение совсем другое, поэтому неудивительно что вылезает за границы ящика. Но вот почему так получвается я не понимаю.
Либо в коде есть какая-то совсем уж дурацкая ошибка, либо найти обратное преобразование в моем случае намного сложнее.

[Dmitriy40]

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

(Немного банальностей)

Для нахождения размеров ящиков Вы считаете $\sqrt{(\max\limits_{i,j}|x_i-x_j|)^2+(\max\limits_{i,j}|y_i-y_j|)^2+(\max\limits_{i,j}|z_i-z_j|)^2}$ (т.е. наибольшую диагональ параллельного координатным осям ограничивающего параллелепипеда), я бы предложил считать $\max\limits_{i,j}\sqrt{(x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2}$ (т.е. диаметр ограничивающей сферы), это почти всегда немного меньше и гарантированно не даст фигуре вылезти за ящик при любых поворотах. Заодно и центры фигур найдёте: в момент присвоения очередного максимума присвоить и координаты центра $(x_c,y_c,z_c)=(\frac{x_i+x_j}{2}, \frac{y_i+y_j}{2}, \frac{z_i+z_j}{2})$.

Правильность обратного преобразования $\Phi^{-1}$ проверить легко: проверьте что $|\Phi\cdot\Phi^{-1}-1|<10^{-12}$ (одновременно для всех трёх координат), т.е. переводит любую точку в себя же. Или посчитайте прямое и обратное преобразование для нескольких (или даже всех) точек фигуры и сравните с исходными координатами. Подозреваю возможная ошибка где-то в геометрии, обратное преобразование на самом деле вовсе не обратное. Чем матричное представление преобразования и удобно, есть формальные правила его нахождения, что прямого, что обратного по нему.

[vpb]

_genius_ в сообщении #1360433 писал(а):

либо найти обратное преобразование в моем случае намного сложнее

Ну как сложнее, не понимаю ? Вы же своими руками проверили формулу для обратного преобразования. Другое дело, что Вы где-то у себя запросто перепутали плюс с минусом, "посеяли" слагаемое и т.д. Или в коде ошиблись, что тоже возможно. Но такие вещи через монитор не видно. Тем более что у Вас в голове. Да и вообще в этом можете разобраться только Вы сами. По численным выдачам и картинкам тут ничего не увидишь, я считаю. Вы же, как я убедился, до определенной степени простую математику (а тут ничего сложнее аналитической геометрии не нужно) знаете, в том смысле, что понимаете, а не только на уровне заучивания формул. Ортогональную матрицу от неортогональной отличите, ну и всё такое прочее. В общем, сейчас Вам надо самому у себя ошибки искать, при необходимости математику "поднять". А я позволю себе, пока что (если не будет необходимости в обратном), Вас оставить. Разве что хочу рекомендовать сначала все-таки решить модельную задачу с двумерными фигурами простой формы.

[vpb]

Позволю себе поправить коллегу: правильнее писать

$$ |\sum_{k=1}^3 \Phi_{ik}(\Phi^{-1})_{kj}-\delta_{ij}|<10^{-12}, \quad \forall\ i,j=1,2,3 $$

[Dmitriy40]

(Оффтоп)

Да я вообще хотел записать $\Phi\Phi^{-1}\equiv 1$ (или $E$, типа единичная матрица), но вспомнил о проблемах точности плавающих типов, ну и сформулировал как получилось.

[_genius_]

Нашел опечатку - $b$ умножался на $A$ вместо $A^T$
https://i.ibb.co/pZsPfq0/Untitled.png
Однако за границы я все равно немного вылезаю $y = 223$ при допустимом максимуме в 216.
Выходит что нужна другая формула для ящиков, чтобы попадание в один гарантировало попадание в другой.
При этом размер лучше оставить достаточно большим, чтобы не возникло недопустимых поворотов.
Насчет сфер надо думать, т.к. придется работать в сферических координатах как минимум для первоначального сдвига в """угол""" сферы, а мне это не очень удобно.

[Dmitriy40]

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

[_genius_]

Dmitriy40 в сообщении #1360800 писал(а):

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

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

-- Ср дек 12, 2018 19:31:34 --

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

[_genius_]

В общем все отлично, ещё немного расширил сетку и с самого начала сдвигаю начало координат в центр второго тела чтобы минимизировать количество вылезаний за границу при оптимизации. С последней Powell из scipy справляется на удивление хорошо несмотря на то что измерений 6 и они как мне кажется не совсем ортогональны.
Единственная проблема это то что присутствует наложение. Пытаюсь играться с $h(d)$ чтобы добиться желаемого поведения, но пока не выходит. Так же пробую различные стартовые параметры. Сейчас например стартую в середине каждой из 6 граней параллелипипеда вокруг первого тела. Вот что вышло из $h(d) = \exp(-d) + \exp(0.01/d) - 1$
https://i.ibb.co/G5v7JRX/untitled.png
Как мне казалось это приведет к тому что при первом же контакте тела слипнутся и уже не расстанутся. На деле это не так. Возможно метод Пауэлла слишком быстро движется и проскакивает этот момент. Но альтернатив нет: квазиньютоновские методы с такой задачей в жизни не справятся.
Может быть стоит попробовать функцию с довольно высоким пиком в (к примеру) $d = 0.1$ и минус бесконечностью в нуле? Разумеется она так же должна стремиться к нулю при больших $d$. Правда тогда есть шанс что второе тело буквально уплывет внутрь первого и уже никогда оттуда не вылезет. В общем предложения принимаются.