Эффективная аппроксимация вращения

Question

Я пытаюсь написать алгоритм, который вращает один квадрат вокруг его центра в 2D до тех пор, пока он не совпадёт или не станет «достаточно близко» к повернутому квадрату, который начался в том же положении, имеет тот же размер и имеет такой же центр. Это довольно легко.

Однако углы квадрата должны совпадать, чтобы получить соответствие, верхний правый угол квадрата для поворота должен быть достаточно близко к тому, что первоначально было в верхнем правом углу повернутого квадрата.

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

Я уже писал методы, чтобы вращать квадраты, и проверить, насколько они близки друг к другу

Моя главная проблема заключается в том, как я должен изменить количество вращаться на каждой итерации на основе того, насколько близко я

Например Если текущее измерение ближе, чем предыдущее, уменьшите угол на половину и перейдите в том же направлении, иначе удвойте угол и поверните в противоположном направлении?

Однако я не думаю, что это довольно плохое решение с точки зрения эффективности.

Любые идеи были бы высоко оценены.

Answer 1

Как об этой схеме:

Поворота в 0, 90, 180, 270 угла (обратите внимание, что существует эффективный алгоритм для этих специальных поворотов, чем общее вращение); сравните каждый из них, чтобы найти квадрант, который вам нужно искать. Другими словами, попробуйте найти две оси с наивысшим соответствием.

Затем выполните двоичный поиск, например, когда вы определили, что ваш повернутый квадрат находится в квадранте 90-180, затем разделите область поиска на два октанта: 90-135 и 135-180. Поверните на 90 + 45/2 и 180-45/2 и сравните. Если вращение 90 + 45/2 имеет более высокое совпадающее значение, чем 180-45/2, продолжайте поиск в октане 90-135, в противном случае продолжайте поиск в октане 135-180. Промыть, прополоскать, повторить.

Каждый раз, когда в рекурсии, вы делаете это:

1. раздел пространство поиска на две ортантов (если пространство поиска от А до В, то первый ортант является A + (A + B)/2 и второй ортант является B - (A + B)/2)
2. проверить левый ортант: повернуть на A + (A + B)/4. Сравните.
3. проверьте правильность ортанта: поверните на B - (A + B)/4. Сравните.
4. Отрегулируйте пространство поиска либо левым ортантом, либо правым ортантом, исходя из того, имеет ли левое или правое значение более высокое значение соответствия.

Answer 2

Другая схема, о которой я могу думать, вместо того, чтобы пытаться поворачивать и искать, вы пытаетесь найти «углы» повернутого изображения.

Если ваше изображение не содержит прозрачных пленок, то есть четыре точки, расположенные по адресу sqrt(width^2+height^2) вдали от центра, цвет которых точно совпадает с углами невращающегося изображения. Это ограничит количество поворотов, которые вам нужно будет искать.

Answer 3

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