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


Конечная задача – найти положение точки на плоскости, используя координатную систему, определяемую этим прямоугольником.

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

Спасибо

Если я правильно понимаю - в реальном, неискажённом, пространстве.

Итеративно методом половинного деления - устроит? 

Это сообщение отредактировал(а) Akina - 13.5.2009, 17:50

Именно так.


Я тоже сначала так подумал. Типа старого анекдота "как поймать льва в пустыне" - забор при этом строить деля противоположные стороны пропорционально. Но потом думаю - что за радость процессор загружать - неужели нельзя напрямую решить? Вот и задал сюда вопрос.

10 итераций по каждой координате - точность в 0,1% тебя устроит? - вряд ли перегреет процессор.


Конечно, задача вполне решается аналитически. Прямые противолежащих сторон в искажении пересекаются - а на самом деле параллельны... следовательно любая прямая, проходящая через кажущуюся точку пересечения противолежащих сторон в реале параллельна им... точно так же точка пересечения диагоналей на проекции остаётся ею и в реале... можно погрузиться в дебри тригонометри, только имхо два десятка итераций на исключительно + - * / куда как менее вычислительно затратны, пусть и дают приближённый результат... а если много тебе ошибки один промилле, ну сделай по 20 итераций по каждой координате, тогда уж точно можно остановиться, потому как погрешность вычислений станет сравнима с точностью результата.

Умеешь ты уговаривать   Если не лень - напиши свою версию алгоритма, пожалуйста.

рис. 1 - исходное состояние. 
A, B, C, D - вершины прямоугольника
X - заданная точка
O1, O2 - кажущиеся точки пересечения сторон

Присоединённый файл ( Кол-во скачиваний: 31 )
 x1.gif 2,29 Kb

рис. 2 - первая итерация. 
Находим точку пересечения диагоналей прямоугольника.
Проводим прямые из кажущихся точек пересечения сторон, они делят (реальный) прямоугольник на 4 равных прямоугольника.
Определяем, в какой из частей находится искомая точка.
Пересчитываем координаты вершин.

В результате итерации координаты точки уже нужно искать в прямоугольнике A1 - B - C1 - D1, координаты новых вершин четырёхугольника cA1 = (cA + cB)/2 и аналогично для остальных трёх вершин.

И так далее - до достижения требуемой точности.

Присоединённый файл ( Кол-во скачиваний: 24 )
 x2.gif 2,74 Kb

Вот здесь чуть подробнее, если можно. Как определять?


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

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

Чем мой алгоритм хуже?

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


А вот с этим я могу сказать только сакраментальное "В поиск, тыщу раз обсуждалось".

Кстати, никто тебе не запрещает сначала делить пополам по одной координате до требуемой точности, потом по другой - просто в точности потеряешь... или по первой, потом по второй, потом снова по первой... ведь определение четвертинки есть не что иное как определение половинки, а потом определение половинки от половинки.

Это сообщение отредактировал(а) Akina - 14.5.2009, 10:23

Может, я чего-то не понимаю, уважаемые сэры. Растянуть четырехугольник в прямоугольник? Либо билинейное преобразование, либо проективное... Билинейное эквивалентно 2 афинным по 2 треугольникам и лучше себя ведет в некотором роде... Оба преобразования довольно просты. Там, конечно, не формула, а решение системы линейных уравнений, но тоже не бог весь что - всего 4...

Earnest, моя благодарность за подробности будет безгранична в пределах разумного.

Проективное преобразование:
       u = (A0 * x + A1 * y + A2) / (A6 * x + A7 * y + 1);
       v = (A3 * x + A4 * y + A5) / (A6 * x + A7 * y + 1);

Билинейное преобразование:
       u = A0 * x + A1 * y + A2 * x * y + A3;
       v = A4 * x + A5 * y + A6 * x * y + A7;

Подставляем координаты известных точек (4 угла) в обеих системах координат, получаем систему уравнений (их будет 8, я ошиблась, это в терминах точек 4, а скалярных - 8), решаем и находим коэффициенты. Для решения системы я использую метод Гаусса, для хорошо определенной системы вполне хватает, но дело хозяйское.

Earnest, прошу прощения за слабость моей математической базы, но хочется уточнить правильно ли я понимаю: 

A0 ... A7 это коэффициенты, определяющие зависимость между двумя системами координат.
x и y координаты точки в одной системе координат
u и v координаты той же точки во второй системе координат

С методом Гаусса я вроде знакомился когда-то-очень-давно.

Совершенно правильно.
У меня есть код на C++, вычисляющий эти коэффициенты по опорным точкам. Надо?

Спасибо. Даже и не знаю. Сильно сомневаюсь, что разберусь больше, чем в десятке-другом строчек С++ кода. Как-то не приходилось никогда работать с С++