| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Система координат определяемая четырехугольником |
| Автор: _Y_ 13.5.2009, 17:13 |
Имеется четырехугольник с произвольными непрямыми углами. Координаты вершин известны. Нужена формула, позволяющая преобразовать систему координат так, чтобы в новой системе этот четырехугольник превратился в прямоугольник со сторонами параллельными осям. Конечная задача – найти положение точки на плоскости, используя координатную систему, определяемую этим прямоугольником. По моим соображениям, это стандартная задача исправления перспективы на фотографиях. Но попытки что-то нагуглить выдают кучу красивых фоток, софт для выполнения работы и ни одного связного математического описания. Спасибо |
| Автор: Akina 13.5.2009, 17:49 | ||||
Если я правильно понимаю - в реальном, неискажённом, пространстве.
Итеративно методом половинного деления - устроит? |
| Автор: _Y_ 13.5.2009, 22:39 | ||||||||
Именно так.
Я тоже сначала так подумал. Типа старого анекдота "как поймать льва в пустыне" - забор при этом строить деля противоположные стороны пропорционально. Но потом думаю - что за радость процессор загружать - неужели нельзя напрямую решить? Вот и задал сюда вопрос. |
| Автор: Akina 13.5.2009, 23:17 | ||||
10 итераций по каждой координате - точность в 0,1% тебя устроит? - вряд ли перегреет процессор.
Конечно, задача вполне решается аналитически. Прямые противолежащих сторон в искажении пересекаются - а на самом деле параллельны... следовательно любая прямая, проходящая через кажущуюся точку пересечения противолежащих сторон в реале параллельна им... точно так же точка пересечения диагоналей на проекции остаётся ею и в реале... можно погрузиться в дебри тригонометри, только имхо два десятка итераций на исключительно + - * / куда как менее вычислительно затратны, пусть и дают приближённый результат... а если много тебе ошибки один промилле, ну сделай по 20 итераций по каждой координате, тогда уж точно можно остановиться, потому как погрешность вычислений станет сравнима с точностью результата. |
| Автор: _Y_ 14.5.2009, 07:42 | ||
Умеешь ты уговаривать  Если не лень - напиши свою версию алгоритма, пожалуйста. |
| Автор: Akina 14.5.2009, 08:01 |
| рис. 1 - исходное состояние. A, B, C, D - вершины прямоугольника X - заданная точка O1, O2 - кажущиеся точки пересечения сторон |
| Автор: Akina 14.5.2009, 08:05 |
| рис. 2 - первая итерация. Находим точку пересечения диагоналей прямоугольника. Проводим прямые из кажущихся точек пересечения сторон, они делят (реальный) прямоугольник на 4 равных прямоугольника. Определяем, в какой из частей находится искомая точка. Пересчитываем координаты вершин. В результате итерации координаты точки уже нужно искать в прямоугольнике A1 - B - C1 - D1, координаты новых вершин четырёхугольника cA1 = (cA + cB)/2 и аналогично для остальных трёх вершин. И так далее - до достижения требуемой точности. |
| Автор: _Y_ 14.5.2009, 08:47 | ||
Вот здесь чуть подробнее, если можно. Как определять? Я, честно говоря, думал примитивнее. Сначала брать две противоположные стороны, делить их пополам, проводить прямую. Смотреть с какой стороны от прямой моя точка. Потом делить половинки пополам, потом четвертинки. На рисунке первый шаг - синяя прямая, второй зеленая, третий малиновая.  Остановиться когда точка отстоит от прямой не больше, чем на величину заданной ошибки. Потом проделать то же самое с другой парой сторон. Чем мой алгоритм хуже? |
| Автор: Akina 14.5.2009, 08:52 | ||||
Алгоритм ошибочен. Пополам на изображении - ни фига не пополам в реале (см. мой рис. 2). Именно для того, чтобы получить правильный пополам из реала, я ищу точку пересечения диагоналей.
А вот с этим я могу сказать только сакраментальное "В поиск, тыщу раз обсуждалось". Кстати, никто тебе не запрещает сначала делить пополам по одной координате до требуемой точности, потом по другой - просто в точности потеряешь... или по первой, потом по второй, потом снова по первой... ведь определение четвертинки есть не что иное как определение половинки, а потом определение половинки от половинки. |
| Автор: Earnest 16.5.2009, 22:03 |
| Может, я чего-то не понимаю, уважаемые сэры. Растянуть четырехугольник в прямоугольник? Либо билинейное преобразование, либо проективное... Билинейное эквивалентно 2 афинным по 2 треугольникам и лучше себя ведет в некотором роде... Оба преобразования довольно просты. Там, конечно, не формула, а решение системы линейных уравнений, но тоже не бог весь что - всего 4... |
| Автор: _Y_ 17.5.2009, 07:58 |
| Earnest, моя благодарность за подробности будет безгранична в пределах разумного. |
| Автор: Earnest 17.5.2009, 12:34 |
| Проективное преобразование: 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), решаем и находим коэффициенты. Для решения системы я использую метод Гаусса, для хорошо определенной системы вполне хватает, но дело хозяйское. |
| Автор: _Y_ 18.5.2009, 10:29 |
| Earnest, прошу прощения за слабость моей математической базы, но хочется уточнить правильно ли я понимаю: A0 ... A7 это коэффициенты, определяющие зависимость между двумя системами координат. x и y координаты точки в одной системе координат u и v координаты той же точки во второй системе координат С методом Гаусса я вроде знакомился когда-то-очень-давно. |
| Автор: Earnest 18.5.2009, 10:43 |
| Совершенно правильно. У меня есть код на C++, вычисляющий эти коэффициенты по опорным точкам. Надо? |
| Автор: _Y_ 18.5.2009, 11:29 | ||
Спасибо. Даже и не знаю. Сильно сомневаюсь, что разберусь больше, чем в десятке-другом строчек С++ кода. Как-то не приходилось никогда работать с С++ |
| Автор: _Y_ 3.6.2009, 17:21 |
| Earnest, спасибо. Билинейное преобразованиое вроде работает. |
