воскресенье, 4 ноября 2012 г.

Проективное преобразование

И так, мы уже знаем что такое однородные координаты и проективное пространство \mathbb{P}^2 (или проективная плоскость). Есть еще одно очень важно понятие в проективной геометрии это проективное преобразование. Формальное определение выглядит так:

Проективным преобразованием - называется биективное отображение h:\mathbb{P}^2\rightarrow\mathbb{P}^2, такое что, для данных трех точек x, y и z лежащих на одной прямой, точки h(x), h(y) и h(z) так же будут лежать на одной прямой.
Иногда проективное преобразование называют гомографией. Для того что бы задать проективное преобразование между двумя проективными плоскостями используют так называемую матрицу гомографии H. Матрица гомографии H является не вырожденной матрицей размера 3х3. Тогда преобразование между двумя точками можно записать в следующем виде:
\begin{pmatrix}x'_{1} \\x'_{2} \\x'_{3}  \end{pmatrix}=\begin{pmatrix}h_{11} & h_{12} & h_{13}  \\h_{21} & h_{22} & h_{23}  \\h_{31} & h_{32} & h_{33}  \end{pmatrix}\begin{pmatrix}x_{1} \\x_{2} \\x_{3}  \end{pmatrix}
или в короче:
x'=Hx
Как же вычислить матрицу гомографии? Этот вопрос пока остается открытым. При программировании же матрицу гомографии получают по 8 точкам - 4 точки с одного изображения и 4 точки с другого изображения. В библиотеке компьютерного зрения OpenCV есть специальная функция для нахождения матрицы гомографии cvFindHomography. 

Прямая линия в однородных координатах и проективное пространство

Прямая линия на плоскости может быть задана уравнением:
Ax+By+C=0,
где А, В - произвольные числа, которые не могут равняется нулю одновременно. Вектор (А, В) - называется нормальным вектором прямой, который является перпендикулярным к прямой. При С=0 прямая проходит через начало координат.
Эта прямая может быть заданна вектором:
(A, B, C)
Соответствие между этим вектором и прямой определяется с точностью до k≠0. т.к. прямые Ax+By+C=0 и (kA)x+(kB)y+C=0 являются эквивалентными и векторы (A, B, C) и k(A, B, C) так же являются эквивалентными. Тогда мы можем говорить о некотором классе эквивалентности между вектором и прямой. Из этого класса исключается вектор (0, 0, 0) который не соответствует ни одной прямой.  
Для того что бы точка X=(x, y) принадлежала прямой l=(A, B, C) необходимо и достаточно что бы Ax+By+C=0. Это может быть записано в терминах скалярного произведения векторов, если X это точка в однородных координатах:
(x, y, 1)^T(A, B, C)=0
Это удобно вычислять при программировании используя матрицы. Т.е.:
x^Tl=0
Для того что бы узнать точку пересечения x для двух прямых l и l' необходимо найти векторное произведение этих двух прямых, результатом которого и будет искомая точка X:
x=l\times l'
А для того что бы построить прямую линию l проходящую через две точки x и x', необходимо вычислить векторное произведение:
l=x\times x'
Попробуем найти пересечение двух параллельных прямых l=(a, b,c) и l=(a, b,c'). Найдем их векторное произведение:

\left|\begin{matrix} i & j & k \\ a & b & c \\ a & b & c'\end{matrix} \right| =(c'-c)(ib-ja)\Rightarrow(b,-a,0)^T
Т.е. мы получили точку лежащую на бесконечности в направлении (b,-a), что соответствует действительности.
Вектор в однородных координатах (x_1, x_2, x_3), x_3\neq 0, соответствует точке из двухмерного пространства \mathbb{R}^2.  Если  \mathbb{R}^2 дополнить точками где последняя координата x_3=0, то мы получим так называемое проективное пространство \mathbb{P}^2. Точки где последняя координата x_3=0, называются идеальными точками или точками на бесконечности.

суббота, 6 октября 2012 г.

Однородные координаты

Что это такое?
Способ представления точки c координатами (x_1,...,x_n) в n-мерном пространстве в виде набора (wx_1,...,wx_n, w)\in\mathbb{R}^{n+1}, где хотя бы один элемент отличен от нуля.

Где используется?
В компьютерной графике для представления объектов в пространстве.

Почему бы не использовать обычные координаты?
В некоторых графических алгоритмах используется понятие бесконечно удаленной точки. Используя обычные координаты такую точку задать не возможно. Так же позволяют отличить точку от вектора.

Ну и как записать бесконечно удаленную точку в однородных координатах?
Выглядит это так: (x_1,...,x_n, 0) - данная запись так же означает что перед нами не точка, а вектор. А запись вида: (x_1,...,x_n, 1) говорит о том что перед нами точка, а не вектор. 

воскресенье, 26 августа 2012 г.

Инверсия односвязного списка

Очень долго тупил над этой задачей. На практике проще использовать чтение списка с конца. Так что задача имеет больше учебный характер. Немного погуглив нашел решение с помощью рекурсии.


Node * reverse(Node *head)
{
        if (head == 0) return 0;
        if (head->next == 0) return head;

        Node * tmp = reverse(head->next);

        head->next->next = head;
        head->next = 0;
        return tmp;
}

вторник, 5 июня 2012 г.

Инкапсулация

Инкапсулация в широком смысле упаковка данных вместе с функциями.

(с) Б. Эккель

воскресенье, 3 июня 2012 г.

Условная компиляция

Часто необходимо некоторым способом отладить программу. Конечно это надо делать с помощью отладчика типа gdb. Но иногда случается так, что отладчика нет под рукой и тогда на помощь может прийти условная компиляция с выводом отладочной информации. Но отсутствие отладчика не такая уж часто встречаемая проблема. Есть и другая задача, где применение условной компиляции неизбежно. Представьте себе, что ваша программа будет работать на нескольких платформах и в зависимости от платформы необходимо выполнять те или иные действия. Например подключать специфические для  данной ОС заголовочные файлы и соответственно вызывать разные функции. Здесь уж точно не обойтись без условной компиляции.
Для условной компиляции используются директивы препроцессора. Как известно директивы препроцессора начинаются с символа #. Например:

 #include <iostream>  //деректива препроцессора которая подключает заголовочный файл

Для условной компиляции используется директива

#ifdef NAME
...
#endif
или
#ifdef NAME
...
#elseif
...
#endif

которая проверяет, не было ли NAME определено ранее и в зависимости от результата выполняет то что заключено между ними. Пример использования условной компиляции для вывода отладочной информации:

#include <iostream>

int main()
{
        int var = 5;

        #ifdef DEBUG
                std::cout << "var: " << var << "\n";
        #endif
}

Для вывода отладочной информации необходимо определить имя DBUG в командной строке компилятора. Для компилятора GCC данная команда выполняется с помощью ключа -D name, где name - имя определяемой константы. Например:

g++ test.cpp -o test -D DEBUG

При отсутствии флага -D с именем константы отладочный код выводится на будет.
Для выполнения платформозависимого кода, существуют предопределенные константы. Синтаксис их использования такой же как и для пользовательских констант. Перечень доступных констант для компилятора GCC можно посмотреть тут.

суббота, 2 июня 2012 г.

Представление float в памяти

Размер float на моем компьютере равен 4 байтам или 32 битам:
cout << sizeof(float); // 4
Согласно стандарту IEEE 754 формат представления float в памяти компьютера следующий:

0
0
1
1
1
1
1
1
1
0
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
1
1 8 23
Это представление числа 1,2345.

Т.е. 1 бит отводится под знак, 8 бит отводится для представления целой части и оставшиеся 23 бита для представления дробной части. А само вычисление производится по формуле:

(-1)^{sing}(1+\displaystyle\sum_{i=1}^{23} b_{-i}2^{-i})2^{e-127}

Пример: Возьмем число изображенное выше 1,2345. Согласно формуле (-1)^0=1, т.е. наше число положительно. Далее вычисляем показатель степени. Для этого переведем двоичное значение 8ми битного поля целой части в десятичное представление:

01111111 =  1*2^0+1*2^1+1*2^2+1*2^3+1*2^4+1*2^5+1*2^6+0*2^7=
=1+2+4+8+16+32+64=127

Вычисляем по формуле:

2^(127-127)=2^0=1

Осталось вычислить дробную часть:

00111100000010000011001=1*2^(-3)+1*2^(-4)+1*2^(-5)+1*2^(-6)+1*2^(-13)+1*2^(-19)+1*2^(-20)+1*2^(-23)=0,125+0,0625+0,03125+0,01563+0,00012+0,0000019073+0,0000009537+0.000000119=(приблизительно)0,2345

Окончательно имеем 1+0,2345=1,2345.
Для того что бы увидеть битовое представление float на компьютере можно воспользоваться маленькой программкой:

#include <iostream>
using namespace std;

// Печать одной байта в битах
void printInBinary(const unsigned char val)
{
        for (int i = 7; i &gt;= 0; --i)
                if (val &amp; (1 &lt;&lt; i))
                        cout &lt;&lt; "1";
                else
                        cout &lt;&lt; "0";
}

int main()
{
        float f = 1.2345;
        unsigned char *ucp = 
              reinterpret_cast<unsigned char*="">(&amp;f);

        for (int i = sizeof(float) - 1; i &gt;= 0; --i)
                printInBinary(ucp[i]);
}

понедельник, 28 мая 2012 г.

Трансляторы

Традиционно трансляторы делятся: интерпретаторы и компиляторы.

Интерпретатор - транслирует исходный текст программы в операции (которые могут состоять из нескольких машинных команд) и немедленно выполняет эти операции.

Компилятор - транслирует исходный текст программы в машинные команды, которые записывает в файл.

По мотивам Эккеля

вторник, 22 мая 2012 г.

Механизмы ООП

На одном из собеседований при трудоустройстве на работу меня спросили определения механизмов ООП. Своими словами и на примерах я постарался объяснить, но формальных определений так и не смог дать.В качестве памятки составлю пост.


Объектно-ориентированное, или объектное, программирование (в дальнейшем ООП) — парадигма программирования, в которой основными концепциями являются понятия объектов и классов.[0]


Механизмы ООП:
  • Инкапсуляция — свойство языка программирования, позволяющее пользователю не задумываться о сложности реализации используемого программного компонента (то, что у него внутри), а взаимодействовать с ним посредством предоставляемого интерфейса (публичных членов — методов, данных etc.), а также объединить и защитить жизненно важные для компонента данные.[1]
  • Полиморфизм — возможность объектов с одинаковой спецификацией иметь различную реализацию. Полиморфизмом в программировании называется переопределение наследником функций-членов базового класса.[2]
  • Наследование — механизм позволяющий описать новый класс на основе уже существующего (родительского), при этом свойства и функциональность родительского класса заимствуются новым классом. В C++ при наследовании одного класса от другого наследуется реализация класса, плюс класс-наследник может добавлять свои поля и функции или переопределять функции базового класса.[3]
Википедия пишет про еще один механизм:
  • Абстракция — это придание объекту характеристик, которые четко определяют его концептуальные границы, отличая от всех других объектов. Основная идея состоит в том, чтобы отделить способ использования составных объектов данных от деталей их реализации в виде более простых объектов, подобно тому, как функциональная абстракция разделяет способ использования функции и деталей её реализации в терминах более примитивных функций, таким образом, данные обрабатываются функцией высокого уровня с помощью вызова функций низкого уровня.[4]

воскресенье, 20 мая 2012 г.

Процесс разработки ПО

Имеет 3 этапа:
  1. Анализ: определение границ решаемой проблемы;
  2. Проектирование: создание общей структуры системы;
  3. Реализация: написание и тестирование программы;
(с) Б. Страуструп