Как линейная алгебра помогла мне в разработке интерактивного редактора диаграмм / forpes.ru

Главная
Как линейная алгебра помогла мне в разработке интерактивного редактора диаграмм

Как линейная алгебра помогла мне в разработке интерактивного редактора диаграмм +3

28.12.2024 11:24

PatientZero 0 16 Источник

Ах, матрицы — одна из тех базовых концепций линейной алгебры, с которыми мы встречались в школе. Несмотря на их важность, мне за мою карьеру ни разу не доводилось с ними работать, и из-за этого я забыл, насколько они мощны и универсальны. Подходящий момент, чтобы вспомнить их, настал, когда я работал над моим интерактивным редактором диаграмм Schemio. В этой статье я расскажу, как использовал матрицы для решения сложных задач.

Начинаем с простого: первые дни Schemio

Когда я только начинал разрабатывать Schemio, всё было просто: пользователи могли создавать фигуры, передвигать их, менять размер и даже вращать. У каждой фигуры была простая область, задаваемая позицией (x, y), размером (ширина, высота) и углом поворота. Всё достаточно просто. Описывающая диаграмму структура данных выглядела примерно так:

const diagram = {
  name: "The title of a diagram",
  // все объекты диаграммы были представлены в виде обычного массива
  items: [{
    id: "2563",
    name: "Rect 1",
    shape: "rect",
    area: {
      // позиция в мировых координатах
      x: 0, y: 0,
      // ширина (w) и высота (h)
      w: 100, h: 40,
      // угол поворота в градусах
      r: 0
    }
  }, {
    id: "wer23",
    name: "Ellipse 1",
    shape: "ellipse",
    area: {
      // позиция в мировых координатах
      x: 100, y: 40,
      // ширина (w) и высота (h)
      w: 40, h: 40,
      // угол поворота в градусах
      r: 45
    }
  }]
};

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

Вот, как изначально выглядела структура элементов в коде:

const item = {
  id: "123",
  name: "Rect",
  shape: "rect",
  area: {
    x: 100, y: 400,
    w: 80, y: 40,
    r: 0,
  },
  childItems: [{
    id: "462",
    name: "Ellipse",
    shape: "ellipse",
    area: {
      x: 10, y: 0,
      w: 30, y: 10,
      r: 45,
    },
    childItems: [{
      // ещё один элемент, прикреплённый к эллипсу
    }]
  }]
};

Проблема иерархий

Представьте: в вашей диаграмме есть прямоугольник. Вы прикрепляете к нему ещё одну фигуру, и к ней ещё одну. Теперь повернём прямоугольник. Если вы выполняете рендеринг в SVG, то всё просто — достаточно вложить элементы SVG, и остальным займётся браузер. Но Schemio — это не только рендеринг. Пользователи могут прикреплять соединения, привязывать и отвязывать объекты друг от друга или выполнять настраиваемые взаимодействия. Для всего этого необходимо выполнять преобразования между локальными и мировыми координатами.

Каким же было моё первое решение? Наивным и неуклюжим. Я итеративно обходил родительскую цепь объектов, применяя преобразования с помощью простой формулы.

$\begin{align*} x_w &= x_p + x \cos \alpha - y \sin \alpha + x_l \cos \beta - y_l \sin \beta \\ y_w &= y_p + x \sin \alpha + y \cos \alpha + x_l \sin \beta + y_l \cos \beta \end{align*}$

Где — точка в мировых координатах; — перенос положения родительского объекта; (x, y) – перенос текущего объекта относительно его родителя; (x_l, y_l) – локальная точка на элементе относительно его левого верхнего края; $\alpha$ – угол родительского объекта в мировых координатах; $\beta$ – локальный угол текущего объекта относительно его родителя

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

На сцене появляются масштабирование и опорные точки

Масштабирование позволяет динамически менять размеры объектов, а опорные точки определяют центр вращения. Возможность изменения масштаба — огромный шаг вперёд для Schemio, позволяющий динамически загружать внешние диаграммы.

Демо загрузки одной динамической диаграммы в другую

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

const item = {
  id: "123",
  name: "Rect",
  shape: "rect",
  area: {
    x: 100, y: 400,
    w: 80, y: 40,
    r: 0,

    /*
      px и py обозначают опорную точку, относительную
      ширины и размера, поэтому при изменении пользователем размера фигуры
      положение опорной точки тоже меняется
    */
    px: 0.5, py: 0.5,
    
    /*
      sx и sy - это коэффициенты масштабирования по осям x и y
    */
    sx: 1, sy: 1
  },
  childItems: [{
     // ещё один элемент, прикреплённый к эллипсу
  }]
};

Но после добавления этих новых требований управление преобразованиями стало хаотичным. Тогда я понял: мне помогут матрицы!

В двухмерной (и трёхмерной) графике каждое преобразование — перенос, вращение, масштабирование — можно выразить при помощи матриц. Например, точка в пространстве — это матрица 3×1. Чтобы преобразовать её, мы умножаем её на матрицу преобразований 3×3. Давайте пройдёмся по основам.

Основы матричных преобразований

Начнём с единичной матрицы, обозначающей отсутствие преобразований:

$I = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

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

$A_T = \begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix}$

Вам нужен поворот? Используйте матрицу вращения:

$A_R = \begin{bmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix}$

А для изменения размера используйте матрицу масштабирования:

$A_S = \begin{bmatrix} s_x & 0 & 0 \\ 0 & s_y & 0 \\ 0 & 0 & 1 \end{bmatrix}$

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

Так как все матрицы преобразований имеют размер 3x3, 2D-точку нужно представить в виде матрицы 3x1. При умножении матрицы преобразований 3x3 на матрицу точки 3x1 мы получаем ещё одну матрицу 3x1 — это координаты преобразованной точки. По сути, именно так и работают все эти преобразования!

$P = \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$

Вот полная формула преобразования для объекта:

$P_W = A_P \cdot A_T \cdot A_{\Delta1} \cdot A_R \cdot A_S \cdot A_{\Delta2} \cdot P_L$

Где — точка в мировых координатах; — матрица преобразований родительского объекта; — матрица преобразований; $A_{\Delta1}$ — матрица преобразований для опорной точки, сдвигающейся на $x_\Delta$ и $y_\Delta$ ; — матрица вращения; — матрица масштабирования; $A_{\Delta2}$ — матрица переноса для опорной точки, сдвигающейся назад на $(-x_\Delta)$ и $(-y_\Delta)$ ; — точка в локальном положении относительно элемента.

Вы можете спросить: откуда берётся матрица преобразований родительского объекта? На самом деле, это просто произведение всех матриц. То есть если мы итеративно пройдём по цепочке элементов в иерархии, то можно превратить это в простую формулу, например, такую:

$A_i = A_{(i-1)} \cdot A_T \cdot A_{\Delta1} \cdot A_R \cdot A_S \cdot A_{\Delta2}$

В представленной выше формуле — это матрица преобразований текущего объекта, а $A_{(i-1)}$ — матрица преобразований его родителя.

Давайте развернём всем матрицы и запишем полную формулу преобразования локальной точки в мировую точку

$P_W = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & t_z \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & \Delta_z \\ 0 & 1 & \Delta_y \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} cos \theta & -sin\theta & 0\\ sin \theta & cos \theta & 0 \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} s_x & 0 & 0\\ 0 & s_y & 0 \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & -\Delta_z\\ 0 & 1 & -\Delta_y \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} x_L \\ y_L \\ 1 \end{bmatrix}$

Демонстрация поворота объекта относительно опорной точки

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

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

Showcase of scaling with the pivot point in the center — Масштабирование объекта с опорной точкой в центре

Мировые координаты и локальные координаты

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

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

$P_W = A_P \cdot A_T \cdot A_{\Delta1} \cdot A_R \cdot A_S \cdot A_{\Delta2} \cdot P_L$

В этой формуле нам известно уже всё, кроме локальной точки, поэтому можно упростить и сгруппировать матрицы так:

$A = A_P \cdot A_T \cdot A_{\Delta1} \cdot A_R \cdot A_S \cdot A_{\Delta2}$ $P_W = A \cdot P_L$

Здесь матрица A обозначает полное преобразование объекта, в том числе его собственные преобразования и преобразования родительских объектов. В линейной матрице мы не можем делить одну матрицу на другую, однако эту проблему можно обойти при помощи обращённой матрицы. Если мы найдём матрицу, обратную A, она будет обозначаться A⁻¹.

Я не буду вдаваться в подробности вычисления обращённой матрицы, потому что их можно найти в любом учебнике по линейной алгебре. Получив A⁻¹, мы можем умножить на неё слева обе части уравнения:

$A^{-1}\cdot P_W = A^{-1}\cdot A \cdot P_L$

У обратных матриц есть отличное свойство: умножив матрицу на обратную ей, мы получим единичную матрицу, что сильно всё упрощает. Это значит, что формула принимает такой вид:

$A^{-1}\cdot P_W = P_L$ $P_L = A^{-1}\cdot P_W$

Вот и всё! Это формула для преобразования мировых точек в локальные координаты. Матрицы делают такие преобразования гораздо более структурированными и удобными. Без них вывод формулы был бы излишне сложным и запутанным.

Прикрепление и открепление объектов: сложности иерархических преобразований

Одна из самых сложных проблем, с которыми я столкнулся при разработке иерархий элементов в Schemio было прикрепление и открепление объектов. Эти действия можно выполнить двумя способами:

Можно перетащить объект в сцене и бросить его на другой объект.

Или можно изменить иерархию в панели Item Selector.

На первый взгляд это выглядит довольно просто. Ведь, кажется, достаточно обновить иерархию объектов, и на этом всё? Не совсем. Главная трудность заключается в повторном вычислении новой позиции и вращения перетаскиваемого объекта. Почему? Потому что позиция каждого объекта определяется относительно его родителя. Если просто поменять иерархию без учёта разницы в позиции, то это будет выглядеть как-то так:

Обратите внимание, что объект Rounded Rect странно скачет вверх и вниз при перетаскивании на другой объект. Не очень-то красиво. Как же нам изменять его позицию и поворот, чтобы избежать этого?

Шаг 1: запоминаем позицию левого верхнего угла перетаскиваемого объекта

Первое, что нам нужно — это мировая позиция левого верхнего угла перетаскиваемого объекта до его перемещения. Давайте назовём её topLeftWorldPoint:

const topLeftWorldPoint = worldPointOnItem(0, 0, item);

На самом деле, функция worldPointOnItem реализована при помощи матричной формулы, выведенной нами выше.

Шаг 2: настраиваем поворот объекта

Далее нам нужно настроить поворот перетаскиваемого объекта при перемещении между родительскими объектами. Представьте, что мы переносим элемент от одного родителя на другой. Сначала мы вычисляем мировой угол поворота текущего родителя. Так как поворот объекта определяется относительно его родителя, мы преобразуем этот локальный поворот в глобальный при помощи функции worldAngleOfItem.

function worldAngleOfItem(item, transformMatrix) {
    // вычисляем мировую точку левого верхнего угла
    const p0 = worldPointOnItem(0, 0, item, transformMatrix);
    // вычисляем мировую точку правого верхнего угла
    const p1 = worldPointOnItem(item.area.w, 0, item, transformMatrix);
    // вычисляем угол между осью X
    // и мировым вектором верхнего края объекта
    return fullAngleForVector(p1.x - p0.x, p1.y - p0.y) * 180 / Math.PI;
}

function fullAngleForVector(x, y) {
    const dSquared = x * x + y * y;
    // проверка на безопасность, поскольку нам нужно нормализовать вектор
    // и разделить его компоненты x и y на его длину
    if (!tooSmall(dSquared)) {
        const d = Math.sqrt(dSquared);
        return fullAngleForNormalizedVector(x/d, y/d);
    }
    return 0;
}

function fullAngleForNormalizedVector(x, y) {
    if (y >= 0) {
        return Math.acos(x);
    } else {
        return -Math.acos(x);
    }
}

Принцип прост: находим вектор, описывающий локальную ось X элемента и преобразуем его в мировые координаты. Угол между этим вектором и мировой осью X даёт нам мировой угол поворота. Повторяем этот процесс для нового родителя и соответствующим образом меняем поворот перетаскиваемого объекта:

item.area.r += previousParentWorldAngle - newParentWorldAngle;

Шаг 3: сохраняем позицию объекта

Теперь нам нужно сделать так, чтобы после перемещения на нового родителя перетаскиваемый объект оставался в том же месте мира. Для этого я реализовал функцию findTranslationMatchingWorldPoint. Эта функция вычисляет необходимый перенос, чтобы указанная локальная точка соответствовала нужной мировой точке.

const newLocalPoint = myMath.findTranslationMatchingWorldPoint(
    Wx, Wy, // мировая точка x и y
    Lx, Ly, // локальная точка на объекте (x и y)
    item.area, // объект области объекта
    parentTransformMatrix // матрица преобразований его родителя
);

// Получив новую точку переноса,
// мы должны лишь обновить x и y области объекта.
// Благодаря этому при перетаскивании любого объекта на другой объект 
// и изменении его позиции в иерархии элементов
// iон будет оставаться в одной точке экрана
if (newLocalPoint) {
    item.area.x = newLocalPoint.x;
    item.area.y = newLocalPoint.y;
}

Как это работает?

Чтобы разобраться, вернёмся к формуле вычисления мировой точки из локальной:

$P_W = A_P \cdot A_T \cdot A_{\Delta1} \cdot A_R \cdot A_S \cdot A_{\Delta2} \cdot P_L$

Здесь:

P_W (мировая точка) и P_L (локальная точка) известны, потому что это аргументы функции.
Единственное неизвестное — это A_t, матрица переноса для объекта.

Объединим все известные матрицы в единую матрицу A:

$A = A_{\Delta1} \cdot A_R \cdot A_S \cdot A_{\Delta2} \cdot P_L$ $P_W = A_P \cdot A_T \cdot A$

Так как нам не нужно перемещать опорную точку и масштабировать объект, достаточно только новой A_t. Чтобы выделить её, снова воспользуемся трюком с обращением матрицы:

$A{_P}^{-1} \cdot P_W = A_T \cdot A$

Давайте переименуем матрицу, обратную матрице позиции родителя, чтобы всё стало понятнее:

$B \cdot P_W = A_T \cdot A$

Здесь есть сложность — мы не можем проделать тот же трюк с обращением для матрицы A, потому что это матрица 3x1, а обращать можно только квадратные матрицы. Давайте вместо этого развернём выражение:

$\begin{bmatrix} b_{11} & b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \\ b_{31} & b_{32} & b_{33} \end{bmatrix} \cdot \begin{bmatrix} x_w \\ y_w \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} a_{11} \\ a_{21} \\ a_{31} \end{bmatrix}$

После перемножения матриц в обеих частях мы получим следующее:

$\begin{bmatrix} b_{11}x_w + b_{12}y_w + b_{13} \\ b_{21}x_w + b_{22}y_w + b_{23} \\ b_{31}x_w + b_{32}y_w + b_{33} \end{bmatrix} = \begin{bmatrix} a_{11} + t_xa_{31} \\ a_{21} + t_ya_{31} \\ a_{31} \end{bmatrix}$

Далее мы можем сосредоточиться только на релевантном:

$\begin{aligned} b_{11}x_w + b_{12}y_w + b_{13} &= a_{11} + t_xa_{31} \\ b_{21}x_w + b_{22}y_w + b_{23} &= a_{21} + t_ya_{31} \end{aligned}$

И, наконец, мы приходим к нашей окончательной формуле:

$\begin{align*} t_x &= \frac{b_{11}x_w + b_{12}y_w + b_{13} - a_{11}}{a_{31}} \\ t_y &= \frac{b_{21}x_w + b_{22}y_w + b_{23} - a_{21}}{a_{31}} \end{align*}$

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

Это отличный пример того, как понимание и применение математических концепций, в частности, обращения матриц и преобразований, позволяют выполнять подобные сложные операции!

Подведём итог

Надеюсь, вам понравилась статья и вы получили представление о математических сложностях, с которыми я столкнулся при разработке Schemio. Если вам любопытен проект и вы хотите глубже понять, как он реализован, то можете изучить исходный код на GitHub: https://github.com/ishubin/schemio.

Хотите поработать в нём? Зайдите на https://schem.io и начните создавать собственные интерактивные диаграммы или прототипы приложений.

Как линейная алгебра помогла мне в разработке интерактивного редактора диаграмм +3

Начинаем с простого: первые дни Schemio

Проблема иерархий

На сцене появляются масштабирование и опорные точки

Основы матричных преобразований

Мировые координаты и локальные координаты

Прикрепление и открепление объектов: сложности иерархических преобразований

Шаг 1: запоминаем позицию левого верхнего угла перетаскиваемого объекта

Шаг 2: настраиваем поворот объекта

Шаг 3: сохраняем позицию объекта

Как это работает?

Подведём итог

Комментарии (0)