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
