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

[Prosolver]

Всем привет!
Из спортивного интереса решил написать алгоритм для прецизионного поворота растрового изображения на произвольный угол относительно произвольной точки поворота. Но боюсь, что изобретаю велосипед...

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

[_PROGRAMM_]

Добрый, на данный момент, вечер. Честно скажу, что даже не разбирал этот код. Смотрел только на название функции. Не помню даже, откуда взялся. Он поворачивает изображение, находящееся в TBitmap. Мои знания в этом направлении закончились

[Prosolver]

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

[evg_m]

Меня же интересует точный алгоритм,

Ваше определение точности алгоритма?

[Prosolver]

Под "точным" алгоритмом я понимаю такой алгоритм, который даёт результат с ошибкой на уровне точности используемых типов данных. Т.е. если я использую, например, тип данных extended, то ошибка должна лежать в 19 знаке после запятой.
В интересующей меня тут задаче, если мы используем 24 битный цвет, то extended даёт даже слишком большой запас точности. Поскольку мы всё-равно округляем каждый канал RGB до целого значения (максимум 255 - 3 знака) нам достаточно иметь только 4 точных знака после запятой, а это значит, что возможно получить абсолютно точное решение даже с типом данных double. Т.е. в данной задаче можно получить настолько точное решение, что точнее не бывает.

[shelest]

О матрицах преобразования что-нибудь слышали?

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

[Prosolver]

shelest, проблема не в том, чтобы повернуть точку на произвольный угол, а в том, что сетка исходного растрового изображения накладывается на сетку итогового изображения нетривиальным образом. При этом квадрату в итоговом изображении может соответствовать, например, восьмиугольник и 4 треугольника "отрезанных" от разных пикселей исходного изображения... Вот здесь есть примерная картинка.
Но за попытку помочь - спасибо.

[evg_m]

Вот здесь есть примерная картинка

А чем не устраивает код(алгоритм) по ссылке? сам код не смотрел.

[Pathoswithin]

Алгоритм? Могу попробовать описать своё видение.
Итак, все точки вращаются по окружности. Допустим х и у - координаты точки относительно центра вращения. Если это катеты прямоугольного треугольника то радиус вращения - гипотенуза. Значит радиус будет равен квадратному корню из суммы квадратов координат. При помощи тригонометрии не трудно посчитать угол наклона гипотенузы относительно координатной сетки, и изменив его посчитать новые координаты. Берём точку итогового изображения и расчитываем её точные координаты на исходном изображении. Мне кажется, в данном сучае точка всё-таки скорей круг чем квадрат и не имеет угла поворота. Возможно, четырёх точек для определения её цвета будет достаточно. При помощи точных координат можно определить наиблизкую точку, ближайшую по оси х, ближайшую по оси у ну и четвёртую, чтоб получился квадрат. Далее необходимо расчитать коэффициены "важности" каждой из четырёх точек. Для этого отбрасываем целые части координат итоговой точки и перемножаем дробные части соответствующим образом: х*у, х(1-у), у(1-х), (1-х)(1-у). Умножаем значения цвета каждой из четырёх точек на её коэффициент и складываем результаты - получаем значение цвета итоговой точки (проделать отдельно для red, green, blue).

[Prosolver]

Сообщение от evg_m

чем не устраивает код(алгоритм) по ссылке?

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

Чтобы не быть голословным приведу результат работы точного алгоритма и результат работы Photoshop. Я взял изображение в виде горизонтальной линии толщиной 1 пиксель и длиной 10 пикселей чёрного цвета на белом фоне и повернул его по часовой стрелке на 3 градуса. Сверху - результат работы точного алгоритма, снизу - результат работы Photoshop (изображение увеличено в 24 раза):

На мой взгляд, это очень большое искажение.

Сообщение от Pathoswithin

Могу попробовать описать своё видение.

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

Сообщение от Pathoswithin

Мне кажется, в данном сучае точка всё-таки скорей круг чем квадрат

Пиксель - это квадрат, потому что вся информация о цвете изображения хранится в памяти ЭВМ в виде прямоугольной таблицы без "зазоров". На печать, действительно, пиксели могут выводится аппроксимированные кружочками, но мне думается, что это только искажает изображение и для процессинга нужно использовать всё-таки "родную" квадратную модель пикселя.