Векторы и линейные преобразования

В компьютерной графике мы изображаем какие-то области плоскости/пространства — сущностей, которые присутствуют только у нас в голове (и, с некоторыми оговорками, — вокруг нас). Компьютер же умеет работать только с числами (да и тоже — с большим количеством оговорок).

Соответственно, первостепенная задача — определиться со способом моделирования плоскости/пространства при помощи чисел.

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

Системы координат

Если мы фиксируем невырожденный треугольник \(ABC\) (слово «невырожденный» означает, что вершины этого треугольника не лежат на одной прямой), то тогда для любой точки \(X\), зная расстояния \(XA\), \(XB\), \(XC\), можно однозначно восстановить её положение:

  • точка \(X\) лежит на окружности с центром в \(A\) и радиусом \(XA\)
  • эта же точка лежит на окружности с центром в \(B\) и радиусом \(XB\)
  • есть не более двух точек пересечения этих окружностей
  • эти точки (в том случае, когда их две) находятся на разном расстоянии от точки \(C\), поэтому ровно одна из них находится на расстоянии \(XC\)

Поэтому любую точку можно задать тремя числами — расстояниями до вершин треугольника. К сожалению, этот подход имеет много недостатков. В частности, такие:

  • не все тройки чисел соответствуют точкам
  • простейшие геометрические объекты (например, прямая и окружность) имеют очень сложные выражения в терминах таких троек чисел

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

А сейчас мы предложим другой подход, который обычно и используется. Проведём из точки \(X\) прямые, параллельные \(AC\) и \(AB\). Первая прямая где-то пересекает прямую \(AB\), вторая — \(AC\). Точки пересечения этих прямых с \(AB\) и \(AC\) назовём \(Y\) и \(Z\) соответственно.

Первой координатой точки \(X\) мы назовём отношение \(AY/AB\) если точка \(Y\) лежит по ту же сторону от \(A\), что и \(B\), и \(-AY/AB\) — в противном случае. Аналогично определим вторую координату точки \(X\) (взяв \(C\) вместо \(B\) и \(Z\) вместо \(Y\)).

Таким образом мы сопоставили каждой точке пару чисел. Более того, любая пара чисел оказалась сопоставлена какой-то одной точке. Самое главное, что теперь любая прямая может быть задана линейным неоднородным уравнением: а именно, прямая — это множество всевозможных точек с координатами \(x_1,x_2\), удовлетворяющими уравнению

\[ ax_1 + bx_2 + c = 0 \]

для какой-то тройки \(a, b, c\), в которой кто-то из \(a\) или \(b\) не ноль.

Более того, если выбрать треугольник \(ABC\) так, что \(\angle BAC = 90^\circ\), а \(AB=AC=1\), то появляются ещё две важные формулы:

  • расстояние между точками с координатами \((a_1, a_2)\) и \((b_1, b_2)\) равно \(\sqrt{(a_1-b_1)^2 + (a_2-b_2)^2}\)
  • окружность с центром в точке \((a_1, a_2)\) и радиусом \(R\) может быть задана уравнением \((x_1-a_1)^2 + (x_2-a_2)^2 = R^2\)

Векторы

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

И это что-то большее есть — векторы. Самая трудная часть векторов — их определение. Вообще говоря, в математике слово «вектор» употребляется в двух смыслах: «широком» и «узком».

В широком смысле вектор — тип объектов, для которых определены операции:

  • сложения двух векторов
  • растяжения вектора (в некоторое число раз)

Для этих операций требуется некоторый естественный набор свойств (например, растянуть сумму векторов всё равно что растянуть в такое же число раз каждый из векторов, а затем результаты сложить). В программировании такое называется «интерфейсом» или «абстрактным типом данных».

В узком же смысле вектор — это конкретная геометрическая реализация вышеописанного интерфейса. Причём, есть несколько широкораспространённых подходов. Каждый из них опишем на псевдопитоне.

Подход №1: направленный отрезок с нетрадиционным равенством

class Vector:
    # модель -- пара точек
    def __init__(self, A, B):
        self.src = A
        self.dst = B

    def __eq__(self, other):
        # пусть distance считает расстояние между точками:
        c1 = distance(self.src, self.dst) == distance(other.src, other.dst)

        # пусть same_side(A,B,C,D) определяет, лежат ли C и D по одну 
        # сторону от прямой AB на плоскости, если A!=B,
        # или точки A на прямой AC, если A=B
        c2 = same_side(self.src, other.src, self.dst, other.dst)

        return (c1 and c2)

    def __add__(self, other):
        A = self.src
        B = self.dst
        C = find_sum(B, other) # такая точка, что Vector(B, C) == other
        return Vector(A, C)

    def scale(self, k):
        A = self.src
        B = self.dst

        C = find_scaled(A, B, k) # такая точка, что AC = |k| AB, причём
                                 # B и C по одну или разные стороны от A
                                 # в зависимости от знака k
        return Vector(A, C)

Подход №2: множество направленных отрезков

class Vector:
    def __init__(self, A, B):
        self.names = { 
            (X, Y) 
            for X in plane 
            for Y in plane
            if distance(A, B) == distance(X, Y)
            if same_side(A, X, B, Y)
        }

    def __eq__(self, other):
        return self.names == other.names

    def __add__(self, other):
        for a, b in self.names:
            A, B = a, b
            break

        # пусть extract_wth_src(s, x) выдаёт элемент e множества s, 
        # которого e[0] == x
        _, C = extract_with_src(other.names, B)

        return Vector(A, C)

    def scale(self, k):
        for a, b in self.names:
            A, B = a, b
            break

        C = find_scaled(A, B, k) 
        return Vector(A, C)

Подход №3: пара чисел

Этот подход предполагает, что у каждой точки есть координаты .x и .y в некоторой заранее фиксированной системе координат.

class Vector:
    def __init__(self, A = None, B = None):
        if A == None: 
            self.x = 0
            self.y = 0
        else:
            self.x = B.x - A.x
            self.y = B.y - A.y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __add__(self, other):
        result = Vector()
        result.x = self.x + other.x
        result.y = self.y + other.y
        return result
    
    def scale(self, k):
        result = Vector()
        result.x = self.x * k
        result.y = self.y * k
        return result

Подход №4: «закреплённые» вектора

Этот подход предполагает, что есть заранее фиксированная точка P.

class Vector:
    def __init__(self, A, B):
        self.dst = find_end(P, A, B)
        # такая точка Q, что PQ = AB и выполнено same_side(P, A, Q, B)

    def __eq__(self, other):
        return self.dst == other.dst

    def __add__(self, other):
        Q = find_end(self.dst, P, other.dst)
        return Vector(P, Q)

    def scale(self, k):
        Q = find_scaled(P, self.dst, k) 
        return Vector(P, Q)

Так что же из этого лучше?

Первый подход неудачен как с точки зрения программирования (информация избыточна, реализации методов сложны), так и с точки зрения математики (в которой очень не приветствуются нетрадиционные способы определения равенства, так как равенство обычно является частью логики — того «железа», на котором математика работает).

Второй подход общепринят в математике, но с трудом применим в программировании из-за необходимости общения с бесконечными множествами.

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

Четвёртый подход можно встретить как в математике, так и в программировании, хотя он и не очень популярен (особенно в математике, где не очень любят «заранее фиксируем произвольную точку \(P\)»).

В любом из этих подходов направленный отрезок (пара точек) задаёт некоторый вектор, но сам не является вектором. Вектор, соответствующий направленному отрезку \((A,B)\) договоримся обозначать \(\overrightarrow{AB}\).

Небольшое лирическое отступление: разница между вторым и четвёртым подходами ровно та же, что и разница между «назовём рациональным числом максимальное по вложению множество пар целых чисех (второе из которых не равно нулю), в котором любые две пары \(a,b\) и \(x,y\) связаны соотношением \(ay=bx\)» и «назовём рациональным числом пару из целого и целого положительного числа, НОД которых равен 1».

Разложение по базису

Пусть вектора \(e_1, e_2\) соответствуют непараллельным направленным отрезкам. Тогда для любого вектора \(v\) существует единственная пара действительных чисел \(v_1, v_2\), для которой

\[ v = v_1 e_1 + v_2 e_2 \]

Такое представление вектора \(v\) называется разложением по базису \(e_1, e_2\), а сами числа \(v_1\) и \(v_2\) — координатами вектора \(v\) в базисе \(e_1, e_2\).

Не следует путать понятия координат точки и координат вектора. Кроме того, что точки и векторы — объекты разной природы, есть ещё следующие соображения:

  • координаты точки требуют наличия системы координат — невырожденного треугольника
  • координаты вектора требуют наличия базиса — пары непараллельных векторов

Причём если для любой системы координат \(ABC\) есть традиционный базис, ей соответствующий — вектора \(\overrightarrow{AB}\) и \(\overrightarrow{AC}\) — то ни для какого базиса нет какой-то определённой ассоциированной с ним системы координат.

Движения и некоторые другие преобразования

Напомним, что движением называется отображение плоскости в себя (т.е. функция, принимающая на вход точку плоскости и возвращающая точку плоскости), сохраняющее расстояния между парами точек.

Говоря псевдокодом, это такая функция f, что для любых точек A и B выполнено

distance(f(A), f(B)) == distance(A, B)

Зададимся вопросом о том, как можно задать движение \(f\) плоскости при помощи набора чисел.

Фиксируем некоторый треугольник \(ABC\) и обозначим \(e_1 = \overrightarrow{AB}\) и \(e_2 = \overrightarrow{AC}\).

Введём также обозначения \(X=f(A)\), \(Y=f(B)\), \(Z=f(C)\), \(f_1 = \overrightarrow{XY}\) и \(f_2 = \overrightarrow{XZ}\).

Рассмотрим точку \(P\) с координатами \(p_1, p_2\) в системе координат \(ABC\). Это можно записать в терминах векторов так:

\[ \overrightarrow{AP} = p_1 e_1 + p_2 e_2 \]

Поскольку движение \(f\) не меняет расстояния между точками, расстояния от \(f(P)\) до \(X, Y, Z\) равны соответственно расстояниям от \(P\) до \(A, B, C\). А ещё они же равны расстояниям до \(X, Y, Z\) от точки \(Q\), определённой равенством

\[ \overrightarrow{XQ} = p_1 f_1 + p_2 f_2 \]

Вспомнив о том, что тройка расстояний однозначно задаёт точку, получаем, что \(f(P) = Q\).

Заметив равенство \(\overrightarrow{AQ} = \overrightarrow{AX} + \overrightarrow{XQ}\), получаем, что для того, чтобы узнать координаты вектора \(\overrightarrow{AQ}\) в базисе \(e1, e2\) (они же — координаты точки \(Q\) в системе координат \(ABC\)), достаточно знать координаты векторов \(\overrightarrow{AX}\) и \(\overrightarrow{XQ}\) в этом же базисе.

Разложим \(f_1\), \(f_2\) и \(\overrightarrow{AX}\) по базису \(e1, e2\):

\[ \begin{aligned} f_1 & = f_{11} e_1 + f_{12} e_2 \\ f_2 & = f_{21} e_1 + f_{22} e_2 \\ \overrightarrow{AX} & = x_1 e_1 + x_2 e_2 \end{aligned} \]

Подставив эти разложения в выражение для \(\overrightarrow{AQ}\), получим

\[ \begin{aligned} \overrightarrow{AQ} & = (p_1 f_{11} + p_2 f_{21} + x_1)e_1 \\ & + (p_1 f_{12} + p_2 f_{22} + x_2)e_2 \end{aligned} \]

Набор чисел

\[ M = \begin{pmatrix} f_{11} & f_{21} & x_1 \\ f_{12} & f_{22} & x_2 \end{pmatrix} \]

называется матрицей преобразования \(f\). Такими матрицами при помощи вышеприведённой формулы можно задавать не только движения, но и другие преобразования (растяжения и скосы). Класс преобразований, задающихся формулой

\[ \begin{aligned} \overrightarrow{AQ} & = (p_1 f_{11} + p_2 f_{21} + x_1)e_1 \\ & + (p_1 f_{12} + p_2 f_{22} + x_2)e_2 \end{aligned} \]

называется линейными неоднородными преобразованиями.

Поэкспериментировать с ними можно в демонстрации.

Напоследок скажем, что, к сожалению, нет устоявшегося соглашения о том, как именно следует ставить эти 6 чисел в таблицу. Единственное более-менее общепринятое соглашение — о нумерации строк и столбцов таблицы:

\[ M = \begin{pmatrix} M_{11} & M_{12} & M_{13} \\ M_{21} & M_{22} & M_{23} \end{pmatrix} \]

То есть, в наших обозначениях \(M_{11} = f_{11}\), \(M_{12} = f_{21}\), \(M_{13} = x_{1}\), \(M_{21} = f_{12}\), \(M_{22} = f_{22}\), \(M_{23} = x_{2}\).

Приложение А (о понятии линейности)

Вообще говоря, в математике есть «широкое» понятие линейного преобразования. Так называется преобразование \(f\) векторных простанств, т.е. преобразующее вектор в вектор (возможно, другой природы), удовлетворяющее равенству

\[ f(\alpha u + \beta v) = \alpha f(u) + \beta f(v) \]

для любой пары чисел \(\alpha,\beta\) и пары векторов \(u\) и \(v\).

Нетрудно заметить, что преобразование, преобразующее вектор \(v = v_1 e_1 + v_2 e_2\) по формулам

\[ \begin{aligned} f(v) & = (v_1 f_{11} + v_2 f_{21})e_1 \\ & + (v_1 f_{12} + v_2 f_{22})e_2 \end{aligned} \]

является линейным.

Более того, любое линейное преобразование (векторов плоскости) можно задать такой формулой: поскольку для всех \(v_1\) и \(v_2\) выполнено

\[ f(v_1 e_1 + v_2 e_2) = v_1 f(e_1) + v_2 f(e_2) \]

то, зная \(f(e_1)\) и \f(e_2)\), мы знаем, во что преобразуется любой вектор. Соответственно, числа \(f_{ij}\) из вышеприведённой формулы для \(f(v)\) получаются путём разложения \(f(e_i)\) по базису:

\[ \begin{aligned} f(e_1) & = f_{11} e_1 + f_{12} e_2 \\ f(e_2) & = f_{21} e_1 + f_{22} e_2 \end{aligned} \]

Теперь, наконец, заметим что линейные преобразования векторов (ЛПВ) — это совсем не то же самое, что и рассмотренные нами выше линейные неоднородные преобразования плоскости (ЛНПП):

  • ЛПВ преобразуют вектора в вектора, ЛНПП — точки плоскости — в точки плоскости
  • даже если отоджествить точки плоскости с их радиус-векторами (относительно некоторого «начала»), ЛПВ не позволяют моделировать сдвиги

Приложение Б (о проективной геометрии)

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

  • увеличить размерность пространства на 1 (т.е. рассмотреть вместо плоскости трёхмерное пространство)
  • выбрать в нём плоскость \(\pi\) и точку \(P\), не лежащую в ней
  • на множестве всех векторов ввести операцию «проекции»:
    • если вектор \(v\) параллелен \(\pi\), то сопоставим ему вектор плоскости \(\pi\), соответствующий направленному отрезку, лежащему в \(pi\) и задающему \(v\) в пространстве
    • если же вектор \(v\) не параллелен \(\pi\), то сопоставим ему точку пересечения прямой, проведённой из \(P\) и параллельной \(v\), с плоскостью \(\pi\)
  • при этом обычно выбирают систему координат \(PABC\), в которой \(PA\), \(PB\) и \(PC\) равны по длине и перпендикулярны друг другу, причём \(C\) находится в плоскости \(\pi\)
  • при таком выборе проекция векторов, не параллельных \(\pi\) — просто отображение вида \((x,y,z)\mapsto (x/z, y/z, 1)\)

У этого подхода очень много привлекательных сторон:

  • теперь сдвиги — тоже линейные преобразования (трёхмерных) векторов
  • можно моделировать как точки, так и вектора плоскости тройками чисел без вероятности их перепутать: у векторов третья координата 0, у точек же она ненулевая
  • если для всех точек определить канонические координаты как те, у которых третья компонента равна 1, то получим удобные соотношения вида «разность точек является вектором» и «сумма точки и вектора является точкой»

Но есть и недостатки:

  • теперь у одной и той же точки есть бесконечно много троек чисел, ей соответствующих
  • три числа больше, чем два (и менее эффективно с вычислительной точки зрения)
  • нет единого соглашения о том, отличать ли точки с отрицательной третьей координатой от таковых с положительной:
    • математики предпочитают считать, что отличать не нужно (более того, они отождествляют даже параллельные \(\pi\) вектора, если эти вектора параллельны друг другу, а нулевой вектор вообще выкидывают)
    • программисты же чаще различают такие точки, чем нет (и по факту работают не с «проективной плоскостью» в общематематическом смысле, а просто — с парой или тройкой обычных плоскостей)

В заключение отметим, что та матрица \(3\times 3\), которая изображена на MDN в документации к методу setTransform

\[ \begin{pmatrix} f_{11} & f_{21} & x_1 \\ f_{12} & f_{22} & x_2 \\ 0 & 0 & 1 \end{pmatrix} \]

это — именно матрица линейного преобразования проективной геометрии. И применяется она к вектору \(p_1 e_1 + p_2 e_2 + 1 e_3\), который соответствует точке плоскости с координатами \((p_1, p_2)\).