Эффективное приближение вращения

Question

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

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

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

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

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

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

Как насчет этой схемы:

Поворот на угол 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. разбивает пространство поиска на два орфана (если пространство поиска от А до В, топервый orthant - A + (A + B) / 2, а второй orthant - B - (A + B) / 2)
2. проверьте левый orthant: поверните на A + (A + B) / 4.Сравните.
3. проверьте правильное положение: поверните на B - (A + B) / 4.Сравнить.
4. Отрегулировать пространство поиска либо влево, либо вправо в зависимости от того, имеет ли левое или правое значение более высокое значение соответствия.