Геометрическое преобразование изображения

[Smogg]

Как из вот этого:



получить вот это:



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

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

[Abstraction]

См. "проективные преобразования".

[Smogg]

Ага, значит только через векторы. И использовать принцип подобия из программы 7-го класса не катит.

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

// Ну, в псевдокоде все очевидно)

UPD: Или же векторы тут не при чем, а через сопоставление координат трапеции координатам прямоугольника получаем [3x3] матрицу "подобия", применив которую к точке исходной фигуры получим точку результирующей?

[Abstraction]

В интернете нашлась вот такая статья. Вроде неплохо описано.

Я могу изложить альтернативный подход, "художественный": пусть прямоугольник ABCD переходит в A'B'C'D'. Возьмём точки пересечения A'B' с C'D' (P) и A'D' с B'C' (Q). Линия PQ - это "горизонт": любое семейство параллельных прямых прообраза сходится в некоторую точку на нём (либо параллельно ему). С помощью этого правила легко перевести в образ любую точку, лежащую на пересечении пары выстраиваемых прямых.

[Smogg]

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

В интернете нашлась вот такая статья. Вроде неплохо описано.

Я могу изложить альтернативный подход, "художественный": пусть прямоугольник ABCD переходит в A'B'C'D'. Возьмём точки пересечения A'B' с C'D' (P) и A'D' с B'C' (Q). Линия PQ - это "горизонт": любое семейство параллельных прямых прообраза сходится в некоторую точку на нём (либо параллельно ему). С помощью этого правила легко перевести в образ любую точку, лежащую на пересечении пары выстраиваемых прямых.

Да, тоже мелькала мысль о нахождении точки через пересечения прямых. Но испугался дзена с пересечением параллельных прямых где-то в бесконечности.
А с другой стороны... Если взять за опорные точки пучков два смежных угла, то центр картинки просчитывается наверняка, а вот с краем, принадлежащем опорным точкам, может получится может стать что-то не то. Хотя для моих целей вполне можно отбросить десяток крайних пикселей исходной картинки, она все равно на порядок больше, так даже реализма добавится.
...Хм, исходную картинку еще можно обрезать, но с результирующей останется тот же самый вопрос - пересечение практически параллельных прямых. Или расчет треугольника высотой в 1 пиксель и шириной в триста - ничего страшного? Да, скорее всего точности float'a на это хватит...

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

Исходя из всего этого, пойду медитировать матрицы по ссылке, как более общий и универсальный принцип преобразований.

Пасиб)

UPD: Да, но ведь можно использовать все четыре угла как опорные точки пучков линий. Тогда одна половина трапеции рассчитывается от одной пары углов, а вторая от второй. Таким образом решается вопрос с краевой неопределенностью и можно обойтись знаниями геометрии на уровне 7-го класса вместе с банальной пропорциональностью.
Вопрос решен.

[Abstraction]

можно обойтись знаниями геометрии на уровне 7-го класса вместе с банальной пропорциональностью.

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

[Smogg]

И правда...

Магия какая-то. Пропорции нету, а прямые остаются прямыми:

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

Ладно, пошел читать DirectX )