Девлог #88 – Хвиля 67: Логістичне відображення, муарові візерунки, тріангуляція Делоне, автомобільні затори, quadtree та припливи

Нові симуляції

📉 Логістичне відображення — вікно у всесвітній хаос

Відображення та його біфуркації

Логістичне відображення — найпростіша одновимірна система, що демонструє повний шлях подвоєння періоду до хаосу:

x_{n+1} = r · x_n · (1 − x_n)      x ∈ [0, 1], r ∈ [0, 4]

Нерухома точка (орбіта періоду 1):     x* = 1 − 1/r     стабільна для r < 3
Біфуркація періоду 2 при r₁ ≈ 3.000
Біфуркація періоду 4 при r₂ ≈ 3.449
Біфуркація періоду 8 при r₃ ≈ 3.544
...
Точка накопичення (початок хаосу) при r∞ ≈ 3.56995

Щоб відрендерити діаграму біфуркації, симуляція ітерує відображення 300 разів (перехідний процес), а потім записує наступні 300 ітерацій для кожного значення r, малюючи вертикальну колонку точок атрактора. Горизонтальна вісь охоплює r від 2.5 до 4.0 з роздільною здатністю 1200 пікселів. Перетягування для масштабування перерендерює обрану ділянку в повній роздільній здатності, розкриваючи самоподібну структуру всередині кожного хаотичного вікна.

Стала Фейгенбаума

Мітчелл Фейгенбаум у 1975 році виявив, що відношення послідовних інтервалів біфуркації сходиться до універсальної сталої, незалежної від конкретного відображення:

Стала Фейгенбаума:
  δ = lim_{n→∞} (r_n − r_{n-1}) / (r_{n+1} − r_n) ≈ 4.66920160910299...

Збіжність:
  (r₁ − r₀) / (r₂ − r₁) = (3.449 − 3.000) / (3.544 − 3.449) = 0.449 / 0.095 ≈ 4.73
  (r₂ − r₁) / (r₃ − r₂) ≈ 4.66  (вже дуже близько до границі)

Та сама δ з'являється в квадратичному відображенні, синусоїдальному відображенні,
і будь-якому унімодальному відображенні з квадратичним максимумом — клас
універсальності хаотичних систем.

Симуляція позначає кожну точку біфуркації подвоєння періоду вертикальною пунктирною лінією й обчислює поточне відношення між послідовними інтервалами, показуючи збіжність до δ на невеликій панелі збоку.

Павутинчаста діаграма та показник Ляпунова

Павутинчаста діаграма (cobweb plot) — це геометричний інструмент для візуалізації динаміки орбіти на параболі y = rx(1−x). Починаючи з x₀, проведіть вертикальну лінію до параболи в точці (x₀, x₁), потім горизонтальну лінію до діагоналі y = x в точці (x₁, x₁), потім вертикальну до параболи в точці (x₁, x₂) і так далі. Стабільна нерухома точка утворює спіраль, що сходиться до перетину; орбіта періоду 2 утворює прямокутник; хаос утворює густу павутину.

Показник Ляпунова (оцінка скінченного часу за N ітерацій):
  λ = (1/N) · Σ_{n=0}^{N-1}  ln |df/dx у x_n|
    = (1/N) · Σ_{n=0}^{N-1}  ln |r(1 − 2x_n)|

  λ < 0 : стабільна періодична орбіта (сусідні траєкторії сходяться)
  λ = 0 : точка біфуркації або гранична стабільність
  λ > 0 : хаос (сусідні траєкторії розходяться експоненційно)

Графік показника Ляпунова малюється безпосередньо під діаграмою біфуркації, поділяючи ту саму вісь r. Хаотичні смуги (λ > 0, показані червоним) і періодичні вікна (λ < 0, показані синім) точно вирівнюються зі структурою біфуркації вище — найяскравіше велике вікно періоду 3 при r ≈ 3.83, передбачене теоремою Лі-Йорка «період 3 означає хаос».

🌐 Муаровий візерунок — інтерференція, дискретизація й наліз

Просторова частота і період муару

Лінійна ґратка з просторовою частотою f (ліній на піксель) може бути описана як періодична бінарна функція g(x) = round(sin(2πfx)). Коли дві ґратки з частотами f₁ та f₂ перемножуються (або еквівалентно, одну переглядають крізь іншу), добуток містить суму й різницю частот:

g₁(x) · g₂(x) = cos(2πf₁x) · cos(2πf₂x)
              = (1/2)[cos(2π(f₁+f₂)x) + cos(2π(f₁−f₂)x)]

Частота муару:    f_m = |f₁ − f₂|
Період муару:       d_m = 1 / f_m    (пікселів на смугу муару)

Приклад: f₁ = 0.10 ліній/px, f₂ = 0.09 ліній/px
  f_m = 0.01 ліній/px  →  d_m = 100 px (широка, помітна смуга муару)

Симуляція рендерить кожну ґратку на окремому позаекранному полотні й компонує їх, використовуючи globalCompositeOperation = 'multiply'. Живе відображення показує f₁, f₂, f_m і d_m, що оновлюються в реальному часі, коли ви перетягуєте повзунки частоти.

Повернуті ґратки

Коли дві ґратки з однаковою частотою f повернуті на кут θ одна відносно іншої, муаровий візерунок має період, що визначається обертанням:

Період муару для ґраток з однаковою частотою під кутом θ:
  d_m = d / (2 · sin(θ/2))

  При θ = 5°:  d_m = d / (2 · sin(2.5°)) ≈ 11.5 d   (широкі смуги)
  При θ = 30°: d_m = d / (2 · sin(15°))  ≈ 1.93 d   (вузькі смуги)
  При θ = 0°:  d_m → ∞  (паралельні ґратки: без муару, рівномірне поле)

Диск обертання дозволяє прогортати від 0° до 90°. При малих кутах смуги муару широкі й повільно осцилюють; при 45° ви отримуєте ромбоподібний ґратчастий візерунок; при 90° дві ґратки ортогональні й утворюють квадратну сітку. Мітка періоду муару постійно оновлюється.

Зв'язок з налізом Найквіста

Муар у цифрових зображеннях — це пряме виявлення налізу: коли сенсор зображення дискретизує тонкий візерунок зі швидкістю нижче межі Найквіста, високі просторові частоти «згортаються назад» до нижчих частот — з'являючись як грубіші візерунки, яких не було в оригінальній сцені. Демонстрація налізу в симуляції рендерить тонку синусоїдальну ціль на частоті f, потім передискретизує її зі швидкістю f_s:

Критерій Найквіста: f_s ≥ 2 · f   (без налізу)

Якщо f_s < 2f (недостатня дискретизація):
  Частота алісу = |f − round(f / f_s) · f_s|

Приклад: f = 0.45 циклів/px, f_s = 1 зразок/px
  Аліс = |0.45 − 0| = 0.45  (без алісу, ледь у межах Найквіста)

  f = 0.55 циклів/px, f_s = 1 зразок/px
  Аліс = |0.55 − 1| = 0.45  (аліс до 0.45 — те саме, що вище!)

Показ поруч демонструє оригінальний візерунок (тонка сітка), результат дискретизації (муар) і мітку частоти алісу. Це дає найінтуїтивніше пояснення того, чому камерам потрібні оптичні низькочастотні антиалісингові фільтри перед сенсорами.

△ Тріангуляція Делоне — оптимальні трикутники та дуал Вороного

Критерій Делоне

Тріангуляція набору точок є тріангуляцією Делоне тоді й лише тоді, коли для кожного трикутника описане коло (circumcircle) не містить жодної іншої точки з набору у своїй внутрішній частині. Цей критерій «порожнього описаного кола» еквівалентний максимізації мінімального кута серед усіх трикутників у тріангуляції — роблячи тріангуляції Делоне максимально «рівносторонніми» для даного набору точок.

Описане коло трикутника (A, B, C):
  Центр D можна знайти на перетині серединних перпендикулярів AB і BC.

  На практиці (стійке обчислення):
    ax, ay = A.x − C.x,  A.y − C.y
    bx, by = B.x − C.x,  B.y − C.y
    D_denom = 2 · (ax·by − ay·bx)
    D.x = (by·(ax²+ay²) − ay·(bx²+by²)) / D_denom + C.x
    D.y = (ax·(bx²+by²) − bx·(ax²+ay²)) / D_denom + C.y
    R   = distance(D, A)

Інспектор при наведенні малює описане коло трикутника під курсором, зафарбовуючи його червоним, якщо воно (помилково) містить іншу точку — корисний режим налагодження, що перевіряє коректність алгоритму в реальному часі.

Інкрементний алгоритм Bowyer-Watson

Симуляція використовує алгоритм Bowyer-Watson, який інкрементно вставляє точки по одній:

Ініціалізація з «супертрикутником», що містить усі точки.

Для кожної нової точки P:
  1. Знайти всі «погані» трикутники: трикутники, чиє описане коло містить P.
  2. Знайти граничний многокутник «поганих» трикутників:
       ребра, не спільні між двома поганими трикутниками.
  3. Видалити всі погані трикутники.
  4. Створити нові трикутники від P до кожного граничного ребра.
  5. Перевірити й виправити будь-які залишкові порушення описаного кола (перевороти ребер).

Після вставки всіх точок:
  Видалити всі трикутники, що мають спільну вершину з супертрикутником.

Складність: O(n log n) очікувана для рівномірно випадкових наборів точок;
             O(n²) у найгіршому випадку (вироджені конфігурації).

Кожен крок вставки анімований: погані трикутники спалахують червоним, порожнина многокутника малюється помаранчевим, потім нові трикутники віялом розходяться від вставленої точки. Покроковий режим дозволяє просуватися по одній точці, щоб простежити алгоритм.

Діаграма Вороного як дуал

Діаграма Вороного — геометричний дуал тріангуляції Делоне. Для кожного трикутника Делоне розмістіть вершину в його центрі описаного кола; з'єднайте центри описаних кіл сусідніх трикутників (що мають спільне ребро). Результат — діаграма Вороного: кожна клітина містить усі точки, ближчі до однієї вхідної точки, ніж до будь-якої іншої.

Дуальність:
  Ребро Делоне (A,B) ↔ ребро Вороного, що розділяє клітини A і B
  Вершина Делоне P   ↔ клітина Вороного точки P
  Трикутник Делоне   ↔ вершина Вороного (центр описаного кола)

Клітина Вороного точки P — це опуклий многокутник:
  { x : |x − P| ≤ |x − Q| для всіх інших вхідних точок Q }

Перемкніть кнопку «Показати Вороного», щоб накласти дуальний граф. Обидві структури малюються одночасно різними кольорами, роблячи стосунок дуальності візуально очевидним: кожне ребро Делоне перетинається перпендикулярно відповідним ребром Вороного.

🚗 Автомобільний затор — як фантомні затори виникають із правил

Модель Нагеля-Шреккенберга

Клітинний автомат Нагеля-Шреккенберга (NaSch) (1992) моделює трафік на односмуговій кільцевій дорозі, поділеній на L клітин. Кожна клітина або порожня, або зайнята одним автомобілем з цілочисельною швидкістю v ∈ {0, 1, 2, …, v_max}. Один часовий крок застосовує чотири правила одночасно до всіх автомобілів:

Нехай d = проміжок попереду (кількість порожніх клітин перед наступним автомобілем)
    v = поточна швидкість
    v_max = максимальна швидкість (за замовчуванням 5)
    p = ймовірність рандомізації (за замовчуванням 0.3)

Правило 1 — Прискорення:
    якщо v < v_max:  v ← v + 1

Правило 2 — Гальмування (уникнення зіткнення):
    якщо v ≥ d:  v ← d − 1

Правило 3 — Рандомізація (шум людської реакції):
    якщо v > 0 і random() < p:  v ← v − 1

Правило 4 — Рух:
    автомобіль просувається на v клітин вперед

Крок рандомізації є ключовим: без нього (p = 0) трафік вільно тече за будь-якої густини. При p > 0 випадкові події гальмування поширюються назад як хвилі «стоп-старт» — фантомний затор, який водії відчувають на автомагістралях без видимої причини.

Просторово-часова діаграма та фундаментальна діаграма

Просторово-часова діаграма показує позиції автомобілів (горизонтальна вісь = позиція на дорозі, вертикальна вісь = час, прокручується вниз). Кожен автомобіль — точка; затори з'являються як темні діагональні смуги, нахилені вліво — вказуючи, що затор рухається назад із приблизно постійною швидкістю. Швидкість затору в моделі NaSch зазвичай становить −1 клітину/крок (одна клітина назад за один часовий крок) незалежно від густини трафіку.

Змінні потоку трафіку:
  ρ = густина = N / L  (автомобілів на клітину, 0 ≤ ρ ≤ 1)
  q = потік    = ρ · ⟨v⟩  (автомобілів, що проходять точку за часовий крок)

Фундаментальна діаграма (q проти ρ) для NaSch з v_max = 5, p = 0.3:
  Гілка вільного потоку  (ρ < ρ_crit ≈ 0.06):  q ≈ ρ · v_max
  Перевантажена гілка  (ρ > ρ_crit):          q зменшується з ρ
  Максимальний потік при  ρ_crit ≈ 0.06,  q_max ≈ 0.32 автомобілів/крок/клітину

Жива фундаментальна діаграма малюється як точка розсіювання (поточна густина, поточний потік) на площині q-ρ, яка простежує характерну перевернуту V-подібну форму, коли густина змінюється повзунком. Гістерезис між гілками вільного потоку та перевантаженою, знайомий з емпіричних даних автомагістралей, якісно відтворюється моделлю.

Фазовий перехід і ефект «швидше — повільніше»

При критичній густині модель зазнає фазового переходу першого роду від вільного потоку до перевантаженого. Вище ρ_crit збільшення v_max може парадоксально зменшити пропускну здатність: вищі індивідуальні швидкості означають, що потрібні більші безпечні дистанції слідування, зменшуючи густину, що зменшує потік. Цей ефект «швидше — повільніше» також спостерігається в моделях пішохідних натовпів (Гельбінг) і пов'язаний із ширшою фізикою рушійних дисипативних систем поблизу переходів до затору.

🌲 Quadtree — просторове розбиття та широка фаза зіткнень

Структура quadtree та вставка

Quadtree рекурсивно поділяє 2D-регіон на чотири рівні квадранти. Кожен внутрішній вузол представляє прямокутник; кожен лист або містить одну точку, або порожній. Вставка нової точки P:

function insert(node, P):
    якщо node є листом і node порожній:
        зберегти P у node
        повернутися
    якщо node є листом і node містить точку Q:
        розбити node на 4 дочірні
        повторно вставити Q у відповідну дочірню
        вставити P у відповідну дочірню
        повернутися
    // node внутрішній:
    вставити P у дочірній квадрант, що містить P

Глибина для n рівномірно випадкових точок: O(log n) очікувана
Найгірший випадок: n колінеарних точок → O(n) глибина (вироджений випадок)

Візуалізація полотна малює кожну межу прямокутника в реальному часі. Коли точки додаються по одній, з'являються нові розбиття з короткою анімацією спалаху. Глибина дерева й кількість листків показуються на панелі статистики.

Запит діапазону з відсіканням гілок

Запит діапазону запитує: «які точки лежать усередині цього прямокутника R?» Наївний пошук перевіряє всі n точок за O(n). Quadtree відсікає гілки, чий обмежувальний прямокутник не перекривається з R:

function range_query(node, R):
    якщо node.bounds не перекривається з R:
        повернути []    // відсікти: пропустити все піддерево
    якщо node є листом:
        повернути [P для P у node, якщо P у R]
    повернути range_query(NW) + range_query(NE) +
           range_query(SW) + range_query(SE)

Складність: O(√n + k) для рівномірно випадкових точок,
            де k = кількість повернутих результатів.

Інтерактивний запит діапазону дозволяє намалювати прямокутник запиту клацанням і перетягуванням. Відсічені піддерева негайно затінюються сірим; активні піддерева світяться. Лічильник показує «відвідані вузли» проти «усього вузлів» для кількісної оцінки переваги відсікання.

Широка фаза виявлення зіткнень

Панель виявлення зіткнень симулює n рухомих кіл. Наївний підхід перевіряє всі n(n−1)/2 пар кожен кадр. Широка фаза quadtree перебудовує дерево кожен кадр (O(n log n)) і перевіряє лише кола в тій самій або сусідніх клітинах як кандидатів широкої фази:

Наївний:     O(n²) перевірок за кадр
Quadtree:  O(n log n) побудова + O(n·k) перевірок
           де k = середня кількість сусідів на клітину ≈ константа

Коефіцієнт прискорення при n = 500:
  Наївний: 124,750 перевірок пар за кадр
  Quadtree: ~2,500 кандидатів широкої фази (≈ 50× менше перевірок)

Живий лічильник показує обидва підрахунки поруч, оновлюючись кожен кадр. Коефіцієнт прискорення наноситься на графік проти n як вторинний графік, підтверджуючи асимптотичну розбіжність O(n²) проти O(n log n).

🌊 Припливи — градієнт гравітації

Приливна сила: градієнт гравітації

Приливні сили — це не сама гравітація, а різниця у гравітаційному прискоренні по всьому тілу скінченного розміру. Для системи Земля-Місяць приливне прискорення в точці, зміщеній на Δr від центру Землі в напрямку Місяця (відстань D), становить:

Гравітаційне прискорення від Місяця в центрі Землі:
  a₀ = G·M_Місяць / D²

У точці поверхні, зміщеній на Δr до Місяця:
  a = G·M_Місяць / (D − Δr)²
  ≈ G·M_Місяць / D² · (1 + 2Δr/D)   (розклад Тейлора, Δr ≪ D)

Приливне прискорення (диференціальне):
  Δa = a − a₀ = 2·G·M_Місяць·Δr / D³   ∝ 1/D³

Ця залежність 1/D³ означає, що приливні сили спадають швидше за гравітацію (1/D²),
тож приливний ефект Місяця на Землю перевищує ефект Сонця, попри більше
гравітаційне притягання Сонця:
  (Приливна сила)_Місяць / (Приливна сила)_Сонце ≈ 2.2

Відображення векторного поля малює стрілки приливного прискорення в точках сітки навколо поверхні Землі. Стрілки утворюють характерний «двочастковий» візерунок: розтягування назовні до й від Місяця, стискання всередину перпендикулярно до лінії Земля-Місяць. Це дає два приливних горби й пояснює приблизно двічі-денний цикл припливу.

Весняні та квадратурні припливи

Місяць і Сонце кожен виробляють власну приливну силу. Їхнє відносне вирівнювання визначає тип припливу:

Сизигія (вирівнювання Місяць-Земля-Сонце або Сонце-Земля-Місяць):
  Приливні сили складаються конструктивно → весняні припливи
  Відбувається в новий місяць (з'єднання) і повний місяць (протистояння)
  Амплітуда весняного припливу ≈ 1 + 0.46 = 1.46 × середня

Квадратура (Місяць 90° від Сонця, якщо дивитись із Землі):
  Приливні сили частково скасовуються → квадратурні припливи
  Відбувається в першій і останній чверті
  Амплітуда квадратурного припливу ≈ 1 − 0.46 = 0.54 × середня

  (де 0.46 — відношення приливних сил Сонця/Місяця з маси та відстані)

Диск фази Місяця проходить крізь 29,5-денний синодичний місяць. Коли він обертається, суперпозиція векторного поля оновлюється в реальному часі, а мареограф внизу записує отриманий приливний діапазон. Піки весняного припливу вирівнюються з позиціями нового й повного місяця; квадратурні мінімуми припадають на чверті.

Приливне захоплення

Місяць завжди повертає до Землі один і той самий бік — наслідок приливного захоплення. Гравітація Землі піднімає приливний горб у породі Місяця. На ранньому етапі історії Місяця, коли він обертався швидше, цей горб зміщувався попереду лінії Земля-Місяць через обертальну інерцію. Гравітаційний момент від Землі на цьому невирівняному горбі уповільнював обертання Місяця, доки його період обертання не зрівнявся з його орбітальним періодом. Симуляція показує анімацію цього процесу з позначеним кутом приливного горба й уповільнювальним моментом.

Часова шкала приливного захоплення:
  t_lock ∝ a⁶ · ω₀ · Q / (M_планета · R_супутник⁵)

  де a = велика піввісь орбіти, Q = приливний коефіцієнт якості,
        ω₀ = початкова швидкість обертання, R_супутник = радіус захопленого тіла

Місяць-Земля: t_lock ≈ кілька сотень мільйонів років (уже захоплений)
Земля-Сонце:  t_lock ≈ 50 мільярдів років (не захопиться протягом життя Сонця)

Що далі

Хвиля 68 продовжує імпульс ще шістьма симуляціями: гравітація N тіл Барнса-Хата O(n log n), ізоконтурування маршуючими квадратами з метакулями, блакитно-шумова вибірка дисків Пуассона Бріджсона, експеримент нерівності Белла CHSH, що досягає межі Цирельсона, атрактор подвійного завитка кола Чуа та модель соціальної сили пішохідного натовпу Гельбінга з формуванням смуг руху. Ця хвиля та її девлог уже опубліковані — дивіться Девлог #89.