Космология и квантовые флуктуации в браузере

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


    Результат

    Постановка задачи


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



    Конечный автомат


    Поведение подобных систем удобно описывать переходами между их состояниями, — т.е. конечным автоматом $\delta: S \rightarrow S$, где $\delta$ — функция перехода между состояниями, отображающая множество состояний в себя.


    В нашем случае диаграмма состояний выглядит так:





    При реализации функцию перехода удобно сделать событийно-зависимой. Это станет видно в дальнейшем. Точно так же удобно иметь возможность подписываться на изменение состояния автомата.


    type State = string | number;
    
    type Transition<States = State> = {
      to: States,
      where: (event: Event) => Array<boolean>,
    };
    
    type Scheme<States = State> = {
      [key: States]: Array<Transition<States>>
    };
    
    interface FSM<States = State> {
      constructor(state: States, scheme: Scheme<States>): void;
      // Returns true if the scheme had a transition, false otherwise
      get isActive(): boolean;
      // Dispatch event and try to do transition
      dispatch(event: Event): void;
      // subscribe on state change
      on(state: States, cb: (event: Event) => any): FSM<States>;
      // remove subscriber
      removeListener(state: States, cb: (event: Event) => any): void;
    };
    

    Отложим на время реализацию и займёмся геометрическими преобразованиями, лежащими в основании нашей задачи.


    Геометрии


    Если вопрос с перемещением холста настолько очевиден, что не будем на нем останавливаться, то растяжение стоит рассмотреть подробнее. Прежде всего, потребуем, чтобы растяжение оставляло неподвижным одну единственную точку — курсор мыши. Также должно выполняться условие обратимости, т.е. обратная последовательность пользовательских действий должна приводить холст в исходное положение. Какая геометрия для этого подходит? Мы будем рассматривать некоторую группу точечных преобразований плоскости в себя $\mathbb{R}^2\rightarrow\mathbb{R}^2$, которая в общем случае выражается введением новых переменных $x', y'$, заданных как функции старых:


    $x' = \varphi(x, y)\\y' = \psi(x, y)$


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


    Современное понимание геометрии отличается от понимания древних. Согласно Ф. Клейну, — геометрия изучает инварианты относительно некоторых групп преобразований. Так, в группе движений $D$ инвариантом является расстояние между двумя точками $d((x_{1},y_{1}),((x_{2},y_{2}))=\sqrt{(x_{1} - x_{2})^2+(y_{1} - y_{2})^2}$. В нее входят параллельные переносы $T_{(x,y)}$ на вектор $(x, y)$, вращения $R_{\phi}$ относительно начала координат на угол $\phi$ и отражения $M_{l}$ относительно некоторой прямой $l$. Такие движения называются элементарными. Композиция двух движений принадлежит нашей группе и иногда сводится к элементарным. Так, например, два последовательных зеркальных отражения относительно прямых $l$ и $n$ дадут поворот вокруг некоторого центра на некоторый угол (проверьте сами):

    $M_{l} \circ M_{n} = T_{(-a,-b)} \circ R_{\alpha} \circ T_{(a,b)}$


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


    Геометрия, которая нам подходит, основана на группе растяжений $P$, к которой, помимо вышеуказанных движений, добавляется гомотетия $S_{k}$ на коэффициент $k$.


    Ну и последнее. В группе обязательно должен присутствовать обратный элемент. А потому существует нейтральный $e$ (или единичный), который ничего не меняет. Например

    $S_{k} \circ S_{k}^{-1}=e$


    означает сначала растяжение в $k$ раз, а затем в $1/k$.

    Теперь мы можем описать растяжение, оставляющие неподвижным точку курсора мыши, на теоретико-групповом языке:


    $(x, y) \rightarrow (x,y)( T_{(-clientX, -clientY)} \circ S_{k} \circ T_{(clientX, clientY)})$


    Примечание 1

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


    $\forall(x,y) \in \mathbb{R}^2 \neq 0 \Rightarrow T_{(-x, -y)} \circ S_{k} \circ T_{(x, y)}) \neq S_{k} \circ T_{(-x, -y)} \circ T_{(x, y)})$



    Выразим движения $T_{(x,y)}$ и $S_{k}$ и их композицию как функции вектора в коде


    type Scalar = number;
    type Vec = [number, number];
    
    type Action<A = Vec | Scalar> = (z: Vec) => (v: A)  => Vec;
    
    // Translate
    const T: Action<Vec> = (z: Vec) => (d: Vec): Vec => [
      z[0] + d[0],
      z[1] + d[1]
    ];
    // Scale
    const S: Action<Scalar> = (z: Vec) => (k: Scalar): Vec => [
      z[0] * k,
      z[1] * k
    ];
    
    const compose = (z: Vec) => (...actions: Array<(z: Vec) => Vec>) =>
    	actions.reduce((z, g) => g(z), z);
    

    Боль 1

    Весьма странно, что в JavaScript отсутствует перегрузка операторов. Казалось бы, при таком повсеместном использовании векторной и растровой графики куда удобнее работать с векторами или комплексными числами в «классической» форме. Понятия действия сменили бы арифметические операции. Так, например, поворот вокруг некоторого вектора $a$ на угол $\phi$ выражался бы тривиальным способом:


    $T_{-a} \circ R_{\phi} \circ T_{a} \Leftrightarrow z \rightarrow (z-a) e^{i \phi}+a$


    К сожалению, JS не следует развитию замечательной пифагорейской идеи «Мир есть число» в отличии, хотя бы, от Python.



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


    Космология холста. Модулярная решётка


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


    Поскольку решётка периодическая, удобно взять на вооружение модулярную алгебру. Таким образом, будем действовать группой $P$ ещё и на тор $T^2=S^1\times S^1$. Поскольку экран монитора не непрерывная плоскость, а целочисленная решётка $\mathbb{Z}^2$ (пренебрежём сейчас тем, что она конечна), то действие группы $P$ надо рассматривать на целочисленном торе $\mathbb{Z}_{p}^2$, где $p$ — размер ребра квадрата $p \times p$:





    Таким образом, раз и навсегда фиксировав наш тор возле начала координат, будем производить все дальнейшие вычисления на нём. Затем размножим его, используя стандартные методы библиотеки canvas. Вот, как выглядит перемещение на один пиксель:





    Очевидно, что стандартная операция взятия модуля x % p нам не подходит, поскольку переводит отрицательные значения аргумента в отрицательные, а на целочисленном торе таковых нет. Напишем свою функцию $x \mod p$:



    const mod = (x, p) =>
          x >= 0 ? Math.round(x) % p : p + Math.round(x) % p;
    

    Теперь вернёмся к машине конечных состояний и


    определим её
    Класс FSM удобно наследовать от EventEmitter, который предоставит нам возможность подписки.
    class FSM<States> extends EventEmitter {
          static get TRANSITION() { return '__transition__'; }
          state: States;
          scheme: Scheme<States>;
          constructor(state: States, scheme: Scheme<States>) {
            super();
            this.state = state;
            this.scheme = scheme;
            this.on(FSM.TRANSITION, event => this.emit(this.state, event));
          }
          get isActive(): boolean {
            return typeof(this.scheme[this.state]) === 'object';
          }      
          dispatch(event: Event) {
            if (this.isActive) {
              const transition = this.scheme[this.state].find(({ where }) =>
                where(event).every(domen => domen)
              );
              if (transition) {
                this.state = transition.to;
                this.emit(FSM.TRANSITION, event);
              }
            }
          }
        }
    


    Далее, определим схему переходов, создадим холст и


    все проинициализируем.
    canvas = document.getElementById('canvas');
        ctx = canvas.getContext('2d');
    
        // Create a pattern, offscreen
        patternCanvas = document.createElement('canvas');
        patternContext = patternCanvas.getContext('2d');
        
        type States = 
          | 'idle'
          | 'pressed'
          | 'dragging'
          | 'zooming';
    
        const scheme: Scheme<States> = {
          'idle': [
            { to: 'pressed', where: event => [event.type === 'mousedown'] },
            { to: 'zooming', where: event => [event.type === 'wheel'] },
          ],
          'pressed': [
            { to: 'moving', where: event => [event.type === 'mousemove'] },
            { to: 'idle', where: event => [event.type === 'mouseup'] },
          ],
          'moving': [
            { to: 'moving', where: event => [event.type === 'mousemove'] },
            { to: 'idle', where: event => [event.type === 'mouseup'] },
          ],
          'zooming': [
            { to: 'zooming', where: event => [event.type === 'wheel'] },
            { to: 'pressed', where: event => [event.type === 'mousedown'] },
            { to: 'idle', where: event => [true] },
          ],
        };
    
        const fsm: FSM<States> = new FSM('idle', scheme);
        const dispatch = fsm.dispatch.bind(fsm);
    


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


          fsm.on('zooming', (event: WheelEvent) => {
            // next scale factor
            const nk = g >= 1
              ? round(k + Math.sign(event.wheelDeltaY) * h * g / 1e2, 1e2)
              : round(k + Math.sign(event.wheelDeltaY) * h * g / 1e2, 1e12);
            // gain
            g = 2 ** Math.trunc(Math.log2(nk));
            if (g < min || g > max) return;
    
            vec = compose(vec)(
              T([-event.clientX, -event.clientY]),
              S(nk / k),
              T([event.clientX, event.clientY])
            );
    
            size = base * nk;
            patternCanvas.width = Math.round(size / g);
            patternCanvas.height = Math.round(size / g);
    
            xyMod = [
              mod(vec[0], patternCanvas.width),
              mod(vec[1], patternCanvas.height)
            ];
    
            k = nk;
    
            main();
          });
    

    Во-первых, мы производим расширение не на коэффициент k, а на некоторое отношение nk / k. Это связано с тем, что m-шаг нашего отображения при фиксированной точке $(a,b)$ выражается как


    $x_{m} = (x_{m-1}-a)k_{m-1}^*+a \\ y_{m} = (y_{m-1}-b)k_{m-1}^*+b $


    или, относительно начальных значений $x_{1}, y_{1}$


    $x_{m}=(x_{1}-a)\prod_{i=1}^{m-1} k_{i}^* + a \\ y_{m}=(y_{1}-b)\prod_{i=1}^{m-1} k_{i}^* + b$


    Очевидно, что произведение $\prod_{i=1}^{m-1} k_{i}^*$ есть нелинейная функция от шага итерации и либо очень быстро сходится к нулю, либо убегает на бесконечность при небольших начальных отклонениях.


    Введём переменную g, которая есть мера удвоения нашего полотна. Очевидно, она принимает постоянное значение на некотором отрезке. Для достижения линейности $k_{i}^*$ воспользуемся однородной подстановкой


    $k_{i+1}^*=\frac{k_{i+1}}{k_{i}}, k_{1}=1$


    Тогда все члены в произведении, кроме первого и последнего, сократятся:


    $\prod_{i=1}^{m-1} k_{i}^*=\prod_{i=1}^{m-1} \frac{k_{i}}{k_{i-1}}=\frac{k_{2}}{1} \frac{k_{3}}{k_{2}}... \frac{k_{m-2}}{k_{m-3}} \frac{k_{m-1}}{k_{m-2}}=k_{m-1}$


    Далее, фазовый скачок g уменьшает скорость расширения таким образом, что вновь разворачивающаяся перед нами фрактальная структура всегда движется линейно. Таким образом, мы получаем аппроксимированную вариацию степенного закона Хаббла расширения Вселенной.


    Осталось разобраться с пределами точности нашей модели.


    Квантовые флуктуцации. Поле 2-адических чисел


    Осмысление процесса измерения привело к понятию действительного числа. Принцип неопределённости Гейзенберга указывает на его пределы. Современный компьютер работает не действительными числами, а с машинными словами, длина которых определяется разрядностью процессора. Машинные слова образуют поле 2-адических чисел $\mathbb{Q_{2}}$ и обозначаются как $\mathbb{F_{2}^{n}}$, где $n$ — длина слова. Процесс измерения в этом случае заменяется процессом вычисления и связан с неархимедовой метрикой:


    $\forall n \in \mathbb{Z}, z \in \mathbb{F_{2}^{n}}: n \cdot z < 2^n$


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


    if (g < min || g > max) return;

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


    Заключение


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


    Результат

    P.S.
    Было ясно, что исходный код получится маленьким, поэтому я вёл разработку в обыкновенном index.html. По ходу написании статьи, я добавил типизацию, которую тестировал в TypeScript playground.
    Поделиться публикацией

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 10

      0
      В FF масштабирование не работает, только перемещение.
      Картинка сменяется белым экраном.
      0
      Осмысление процесса измерения привело к понятию действительного числа. Принцип неопределённости Гейзенберга указывает на его пределы.
      Серьезно? Мы в симуляции?)
        +2

        Ну нет, здесь речь лишь об ограничениях познания

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

          Статья действительно интересная, спасибо, пишите еще!
            0
            Думаю, самим объектам. Взять хотя бы структур кристаллов.
          0
          «Материя есть объективная реальность, данная нам в ощущении.»
          Что вам говорят ваши ощущения, если постучаться о материю, например, стены?

          ЗЫ а так статья — полный восторг: гармонично смешать математику, кванты и программирование!
            0
            Что вам говорят ваши ощущения, если постучаться о материю, например, стены?
            Это не факт, можно сделать систему ВР в которой воспроизвести тот же эффект)
            Приведенное определение несколько устарело.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое