Math
Вороний і Делоне
Комірки найближчого сусіда, що перебудовуються, поки тягнеш їхні точки; двоїста їм тріангуляція Делоне з порожніми колами; диски, що ростуть у комірки; і релаксація Ллойда, яка робить їх шестикутниками.
Що відбувається
Сорок точок на квадраті, і кожна точка квадрата належить найближчій із них: одне це правило малює межі. Кожна комірка пофарбована у відтінок своєї точки й обведена світлом; потягни точку — і всі комірки перебудуються в тому самому кадрі, бо комірка — не що інше, як квадрат, обрізаний серединними перпендикулярами між її точкою та всіма іншими. Двоїстість: дві комірки зі спільною межею дають ребро між їхніми точками, а де три комірки сходяться в кут, три точки утворюють трикутник — це тріангуляція Делоне, і при h точках на зовнішній оболонці в ній рівно 3N − 3 − h ребер і 2N − 2 − h трикутників (лічба Ейлера, перевіряється наживо). У кожного її трикутника описане коло порожнє: увімкни кола і переконайся, що жодна точка не потрапляє всередину жодного з них, а кожен кут комірки рівновіддалений від своїх трьох точок. Сцена росту ростить диск навколо кожної точки з рівною швидкістю: диски зустрічаються рівно на межах комірок, бо межа — там, де дві точки однаково близькі, і квадрат заповнюється на найдальшому куті комірки. Релаксація Ллойда зсуває кожну точку в центр мас її комірки, крок за кроком: енергія Σ∫|x − точка|² по комірках падає монотонно, площі вирівнюються і комірки стають шестикутними — 9 шестикутників перетворюються на 15 із 40 за тридцять кроків.
Рівняння модуля
Рівняння
комірка: V_i = {x : |x − s_i| ≤ |x − s_j| для всіх j} = квадрат, відрізаний півплощинами (s_j − s_i)·x ≤ (|s_j|² − |s_i|²)/2, по одній на кожен інший центр, у порядку індексів (Сазерленд–Ходжман); кожне ребро пам'ятає центр, який його відрізав
дуальна: ребро Делоне s_i s_j існує, коли V_i і V_j мають спільне ребро; трикутник s_i s_j s_k - коли три комірки сходяться у вершині - ця вершина є центром описаного кола, і жоден центр не лежить усередині описаного кола; береться з діаграми, обрізаної рамкою в 1000 разів ширшою, бо два центри опуклої оболонки можуть зустрітися лише поза квадратом (98 зі 105 ребер видно всередині нього)
Ейлер: h центрів на опуклій оболонці (монотонний ланцюг Ендрю): E = 3N − 3 − h, T = 2N − 2 − h; N = 40, зерно 5: h = 12, E = 105, T = 66; 219 вершин комірок, 5.475 на комірку; комірки замощують квадрат: Σ площ = 4
зростання: круг радіуса r навколо кожного вузла, обрізаний його коміркою (правильний 32-кутник); покрита частка 0.260 / 0.694 при r = 0.1 / 0.2; повне покриття при r = max по комірках найдальшого кута = 0.5126; круги зустрічаються на межах, бо межа є місцем, де два вузли однаково близькі
Ллойд: s_i ← centroid(V_i) = (1/6A) Σ (x_k + x_{k+1})(x_k y_{k+1} − x_{k+1} y_k), потім перебудова; енергія F = Σ_i ∫_{V_i} |x − s_i|² dx (віяло трикутників з s_i, ∫ = A(a² + b² + a·b)/6 на трикутник) монотонно спадає: 0.1355 → 0.0954 після одного кроку → 0.0681 після тридцяти; розкид площ 0.0596 → 0.0149; шестикутників 9 → 15 з 40
