Діаграми Вороного — замітальна пряма Фортуна, Делоне та GLSL-поля відстаней

1. Означення та властивості

Нехай P = {p₁, p₂, …, pₙ} — набір із n різних точок (опорних) у ℝ². Клітина Вороного опорної точки pᵢ — це:

Межі між сусідніми клітинами — це серединні перпендикуляри: кожне ребро діаграми є серединним перпендикуляром до відрізка між двома опорними точками. Три клітини сходяться у вершині Вороного, яка є центром описаного кола трикутника, утвореного цими трьома опорними точками.

Ключові структурні факти:

• Опуклість: як перетин півплощин, кожна клітина Вороного опукла.
• Порожнє описане коло: описане коло будь-якої вершини Вороного проходить рівно через три опорні точки й не містить жодної іншої опорної точки всередині.
• Двоїстий граф: двоїстою до діаграми Вороного є тріангуляція Делоне (з'єднати опорні точки, чиї клітини мають спільне ребро).
• Статистична регулярність: для рівномірного пуассонівського точкового процесу середня клітина має рівно 6 сторін (аргумент Ейлера + густина).

2. Наївний алгоритм O(n²) — растеризація

Найпряміший підхід: для кожного пікселя знайти найближчу опорну точку й зафарбувати піксель її кольором. Це пошук найближчого сусіда повним перебором по сітці зображення.

// Діаграма Вороного повним перебором — O(W·H·n), проста, але повільна для великих n
function voronoiBrute(seeds, width, height) {
  const out = new Uint8ClampedArray(width * height * 4);
  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      let minDist = Infinity, nearest = 0;
      for (let i = 0; i < seeds.length; i++) {
        const dx = x - seeds[i].x, dy = y - seeds[i].y;
        const d = dx*dx + dy*dy;  // пропускаємо sqrt — лише порівнюємо
        if (d < minDist) { minDist = d; nearest = i; }
      }
      const c = seeds[nearest].color;
      const idx = (y * width + x) * 4;
      out[idx] = c[0]; out[idx+1] = c[1]; out[idx+2] = c[2]; out[idx+3] = 255;
    }
  }
  return out;
}

Добре для малих n (≤ 100) або зображень низької роздільності. Для діаграм високої роздільності з тисячами опорних точок це неприйнятно повільно — відповідь дає алгоритм Фортуна.

3. Алгоритм замітальної прямої Фортуна — O(n log n)

Алгоритм Стівена Фортуна 1987 року обчислює точну діаграму Вороного за час O(n log n) і простір O(n), проводячи горизонтальну пряму вниз по площині. Він підтримує дві структури даних:

• Чергу подій (пріоритетну чергу, впорядковану за y): два типи подій — події точок (коли замітальна пряма досягає нової опорної точки) та події кіл (коли три параболічні дуги спричиняють утворення вершини Вороного).
• Берегову лінію (збалансоване бінарне дерево пошуку): послідовність параболічних дуг, що формують фронт обчислюваної діаграми. Кожна дуга — це геометричне місце точок, рівновіддалених від однієї опорної точки та замітальної прямої.

Коли спрацьовує подія точки (замітальна пряма досягає опорної точки pᵢ):

1. Знайти дугу безпосередньо над pᵢ на береговій лінії.
2. Розділити її та вставити нову параболічну дугу для pᵢ між двома половинами.
3. Записати два напівребра для нового ребра Вороного, що окреслюється.
4. Перевірити події кіл, що стосуються сусідів нової дуги.

Коли спрацьовує подія кола (три послідовні дуги сходяться в точку):

1. Видалити середню дугу з берегової лінії.
2. Записати вершину Вороного в центрі описаного кола трьох опорних точок.
3. З'єднати два напівребра від видаленої дуги в завершені ребра.
4. Повторно перевірити події кіл для нових сусідніх трійок дуг.

4. Тріангуляція Делоне — двоїстий граф

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

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

Інкрементне вставляння Боуєра-Ватсона

Легка для реалізації альтернатива алгоритму Фортуна для обчислення тріангуляцій Делоне:

// Інкрементна тріангуляція Делоне Боуєра-Ватсона
// (спрощено — без видалення межі («супертрикутника»))
function bowyer(points) {
  const triangles = [superTriangle(points)];  // спочатку один величезний трикутник

  for (const p of points) {
    // Знайти всі трикутники, описане коло яких містить p
    const bad = triangles.filter(t => inCircumcircle(t, p));

    // Знайти межу багатокутного отвору
    const boundary = uniqueEdges(bad);  // ребра, не спільні для двох поганих трикутників

    // Видалити погані трикутники
    for (const t of bad) triangles.splice(triangles.indexOf(t), 1);

    // Перетріангулювати отвір: з'єднати кожне ребро межі з p
    for (const [a, b] of boundary) {
      triangles.push({ a, b, c: p });
    }
  }
  return triangles.filter(t => !sharesSuperVertex(t));
}

// Перевірка порожнього описаного кола
function inCircumcircle({ a, b, c }, p) {
  const ax = a.x - p.x, ay = a.y - p.y;
  const bx = b.x - p.x, by = b.y - p.y;
  const cx = c.x - p.x, cy = c.y - p.y;
  return (
    ax*(by*(cx*cx+cy*cy) - cy*(bx*bx+by*by)) -
    ay*(bx*(cx*cx+cy*cy) - cx*(bx*bx+by*by)) +
    (ax*ax+ay*ay)*(bx*cy - by*cx)
  ) > 0;
}

Алгоритм Боуєра-Ватсона має складність O(n²) у найгіршому випадку (хоча O(n log n) на практиці з рандомізованим вставлянням). Щойно ви маєте тріангуляцію Делоне, діаграма Вороного є її геометричною двоїстою — з'єднайте центри описаних кіл сусідніх трикутників.

5. Релаксація Ллойда — центроїдна тесселяція Вороного

Центроїдна тесселяція Вороного (CVT) — це особлива діаграма Вороного, де кожна опорна точка збігається з центроїдом своєї власної клітини. Алгоритм Ллойда ітерує до CVT, чергуючи два кроки:

1. Обчислити діаграму Вороного поточних опорних точок.
2. Перемістити кожну опорну точку в центроїд (зважене середнє положень пікселів у тій клітині).

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

// Растрова релаксація Ллойда — одна ітерація
function lloydStep(seeds, width, height) {
  const sums = seeds.map(() => ({ sx: 0, sy: 0, count: 0 }));

  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      let best = 0, bestD = Infinity;
      for (let i = 0; i < seeds.length; i++) {
        const dx = x - seeds[i].x, dy = y - seeds[i].y;
        const d = dx*dx + dy*dy;
        if (d < bestD) { bestD = d; best = i; }
      }
      sums[best].sx += x;
      sums[best].sy += y;
      sums[best].count++;
    }
  }
  return seeds.map((s, i) => sums[i].count > 0
    ? { ...s, x: sums[i].sx / sums[i].count,
               y: sums[i].sy / sums[i].count }
    : s
  );
}

6. GLSL-діаграма Вороного на полі відстаней

Найефектніші візуалізації Вороного виконуються у фрагментних шейдерах, де кожен піксель паралельно на GPU обчислює найближчу опорну точку. Компактний варіант inigo quilez додатково обчислює відстань до другої найближчої точки, уможливлюючи плавні межі клітин і внутрішні візерунки.

// GLSL Вороной — передає опорні точки через текстуру або uniform-масив
// Тут: процедурні опорні точки, згенеровані з хешу сітки
// На основі техніки voronoise Іньїго Кілеса

vec2 hash22(vec2 p) {
  p = vec2(dot(p, vec2(127.1, 311.7)),
            dot(p, vec2(269.5, 183.3)));
  return -1.0 + 2.0 * fract(sin(p) * 43758.5453123);
}

// Повертає (minDist, secondMinDist, індекс клітини)
vec3 voronoi(vec2 uv, float scale) {
  vec2 p = uv * scale;
  vec2 gv = floor(p);
  float md = 8.0, md2 = 8.0;
  vec2 closest;

  for (int y = -2; y <= 2; y++) {
    for (int x = -2; x <= 2; x++) {
      vec2 cell = gv + vec2(x, y);
      // Зміщуємо опорну точку всередині клітини
      vec2 seed = cell + 0.5 + 0.5 * hash22(cell);
      float d = length(p - seed);
      if (d < md) { md2 = md; md = d; closest = seed; }
      else if (d < md2) { md2 = d; }
    }
  }
  return vec3(md, md2, md2 - md);
}

// Використання у фрагментному шейдері
void main() {
  vec2 uv = vUv;
  vec3 v = voronoi(uv, 8.0);

  float minD  = v.x;   // відстань до найближчої опорної точки
  float minD2 = v.y;   // відстань до другої найближчої
  float border = v.z;  // ≈ відстань до ребра (minD2 - minD)

  // Стиль: клітини з чіткими межами
  float edge = smoothstep(0.0, 0.04, border);
  vec3 col = mix(vec3(1.0), vec3(minD * 1.5), edge);
  gl_FragColor = vec4(col, 1.0);
}

Анімуючи зміщення опорних точок hash22 у часі (додайте зсув uTime до положення опорної точки), ви отримаєте плавно трансформівні рідкі клітини Вороного — популярний ефект у шейдерних демо та фонах інтерфейсів.

7. Застосування в науці, іграх і візуалізації

• Пошук найближчого сусіда: клітина Вороного для точки запиту q одразу визначає найближчу опорну точку без перебору всіх. У поєднанні з графом Делоне точні запити найближчого сусіда виконуються за O(log n).
• Процедурний рельєф і карти: Вороной + релаксація Ллойда поділяють площину на полігональні «плити» чи біоми. Призначте висоту/вологість кожній клітині для миттєвої правдоподібної географії (як у генераторі полігональних карт Аміта Пателя).
• Біологічні клітини: поперечні зрізи епітеліальної тканини, мильна піна та бджолині стільники наближено відповідають діаграмам Вороного з опорною точкою в ядрі клітини. Симуляція поділу клітин використовує CVT, щоб клітини лишалися рівномірного розміру.
• Стипплінг і нефотореалістичний рендеринг: зважена за густиною CVT створює точкові візерунки, що перцептивно відповідають вхідному зображенню — «стипплінг Вороного».
• Покриття та розміщення об'єктів: пошук n розташувань складів, що мінімізують середню відстань поїздки клієнта = центроїдна тесселяція Вороного.
• Скінченноелементні сітки: тріангуляція Делоне (двоїста до Вороного) — бажана стратегія генерування сіток, бо вона максимізує якість трикутників (без голчастих трикутників), покращуючи числову стабільність.
• Симуляція руйнування: клітини Вороного визначають уламки розколу в фізичних рушіях реального часу. Розмістіть опорні точки випадково всередині сітки, розріжте вздовж меж Вороного, а потім симулюйте уламки як тверді тіла за допомогою Cannon-es.

8. Розширення: 3D, зважені та степеневі діаграми

• 3D Вороной: природно розширюється на ℝ³ — кожна опорна точка отримує опуклу багатогранну клітину. Використовується в обчислювальній хімії (комірки Вігнера-Зейтца), матеріалознавстві (розділення зерен у полікристалах) та уточненні 3D-сіток.
• Степеневі діаграми (Лагерра-Вороного): кожна опорна точка pᵢ має вагу wᵢ (наприклад, радіус кола). Степенева відстань замінює евклідову:
  
  pow(x, pᵢ) = d(x, pᵢ)² − wᵢ²
  
  Клітини все ще опуклі, а двоїста — це регулярна тріангуляція. Критично для симуляції пакування сфер, динаміки піни та еліпсоїда Джона-Льовнера.
• Вороной на конусах на GPU: рендерте кожну опорну точку як конус (висота = відстань) прямо згори, проєктуючи вниз на буфер кадру. Видима поверхня конуса на кожному пікселі дає найближчу опорну точку — елегантний GPU-алгоритм O(n) для неперервнотонової діаграми Вороного з будь-якою метрикою, що змінюється з положенням.
• Геодезичний Вороной: замініть ℝ² поверхнею з трикутної сітки. Геодезична відстань (найкоротший шлях по поверхні) визначає належність до клітини. Використовується для текстурного атласингу, ремешингу поверхонь і прив'язки риґу персонажа.
• Анімований і змінний у часі: переміщуйте опорні точки в часі (наприклад, частинки SPH чи положення агентів). Перераховуйте Вороной щокадру — це дає відчуття володіння територією чи зон впливу у ШІ стратегічних ігор.