🌐 Диаграми на Вороной и Триангулация на Делоне

Диаграмите на Вороной (Voronoi Diagrams) и тяхната дуална структура – Триангулацията на Делоне (Delaunay Triangulation) – са едни от най-фундаменталните обекти в изчислителната геометрия.

1. Диаграма на Вороной

1.1. Дефиниция

Нека имаме множество от \(N\) точки \(P = \{p_1, p_2, \dots, p_n\}\) в равнината, наречени сайтове (sites). За всяка точка \(p_i\), клетката на Вороной \(V(p_i)\) се състои от всички точки в равнината, които са по-близо до \(p_i\), отколкото до която и да е друга точка от \(P\).

\(V(p_i) = \{ x \in \mathbb{R}^2 \mid \text{dist}(x, p_i) \le \text{dist}(x, p_j), \forall j \neq i \}\)

1.2. Свойства

Всяка клетка е изпъкнал многоъгълник (сечение на полуравнини).
Ръбовете на диаграмата са части от симетралите на отсечките, свързващи двойки точки.
Върховете на диаграмата са точки, които са равноотдалечени от поне 3 сайта (центрове на описани окръжности).
Ако всички точки са колинеарни, диаграмата се състои от успоредни прави.

1.3. Приложения

Най-близък съсед (Nearest Neighbor): За дадена точка \(q\), намирането на най-близкия сайт се свежда до намиране в коя клетка попада \(q\) (\(O(\log N)\) след \(O(N \log N)\) препроцесинг).
Най-голяма празна окръжност (Largest Empty Circle): Центърът на такава окръжност трябва да съвпада с връх на диаграмата на Вороной или да лежи на изпъкналата обвивка.

2. Триангулация на Делоне (Delaunay Triangulation)

Триангулацията на Делоне е дуалният граф на диаграмата на Вороной. Ако две клетки \(V(p_i)\) и \(V(p_j)\) имат общ ръб, то свързваме \(p_i\) и \(p_j\) с отсечка.

2.1. Свойства

Празни окръжности: Описаната окръжност около всеки триъгълник от триангулацията не съдържа други точки от множеството във вътрешността си.
Максимизиране на минималния ъгъл: От всички възможни триангулации на множеството точки, тази на Делоне максимизира най-малкия ъгъл в триъгълниците (избягва "тесни" триъгълници).
Външните ръбове образуват Изпъкналата обвивка (Convex Hull) на множеството.

3. Алгоритми за построяване

3.1. Алгоритъм на Форчън (Fortune's Algorithm) - \(O(N \log N)\)

Това е "Sweep Line" алгоритъм. * Използваме сканираща права (sweep line), която се движи отгоре надолу. * Поддържаме "Плажна линия" (Beach Line): Границата между обработената и необработената част на равнината. Тя се състои от дъги на параболи (тъй като геометричното място на точките, равноотдалечени от точка (сайт) и права (sweep line), е парабола). * Срещата на две дъги описва ръб от Вороной. * Сложността е оптимална, но имплементацията е изключително трудна и рядко се прави на състезания (освен ако нямате подготвен код в библиотека).

3.2. Инкрементален алгоритъм (Bowyer-Watson) - \(O(N^2)\) (лош случай)

За състезания с малко \(N\) (до \(\approx 1000-2000\)) или случайно разпределени точки, този метод е предпочитан. 1. Започваме с "супер-триъгълник", който съдържа всички точки. 2. Добавяме точките една по една. 3. За всяка нова точка \(P\): * Намираме всички съществуващи триъгълници, чиято описана окръжност съдържа \(P\). Тези триъгълници вече не са валидни (нарушават условието на Делоне). * Премахваме ги, което образува "звездовидна дупка". * Свързваме \(P\) с върховете на тази дупка, за да образуваме нови триъгълници.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

struct Point {
    double x, y;
};

struct Edge {
    int u, v; // индекси на точки
    bool bad;
};

struct Triangle {
    int a, b, c; // индекси на точки
    bool bad; // маркиран за премахване
};

// Проверка дали точка p е вътре в описаната окръжност на триъгълника
bool is_inside_circumcircle(Point p, Point a, Point b, Point c) {
    // Детерминанта или формула за разстояние
    double ax = a.x - p.x, ay = a.y - p.y;
    double bx = b.x - p.x, by = b.y - p.y;
    double cx = c.x - p.x, cy = c.y - p.y;

    // (a^2 + ay^2) * (bx*cy - by*cx) - ...
    // За простота: разстоянието от центъра. 
    // Тук показваме само идеята.
    return false; // Имплементирайте Geometry логика
}

// Примерна структура на алгоритъма
vector<Triangle> bowyer_watson(vector<Point>& points) {
    vector<Triangle> triangles;
    // 1. Добави супер-триъгълник (достатъчно голям)
    // ...

    for (int i = 0; i < points.size(); ++i) {
        vector<Triangle> badTriangles;
        for (auto& t : triangles) {
            // Вземи координатите на върховете на t
            // Провери дали points[i] е в описаната окръжност
            // Ако да -> t.bad = true; badTriangles.push_back(t);
        }

        vector<Edge> polygon;
        for (auto& t : badTriangles) {
            // Добави ръбовете на t към polygon
            // Ако ръб се повтаря (споделен между два лоши триъгълника), той е вътрешен -> премахни го.
        }

        // Премахни лошите триъгълници от triangles
        // ...

        // Създай нови триъгълници от points[i] към всеки ръб в polygon
        for (auto& edge : polygon) {
            triangles.push_back({edge.u, edge.v, i, false});
        }
    }

    // Премахни триъгълниците, свързани със супер-триъгълника
    return triangles;
}

4. Задачи за упражнение

Codeforces 212E: Изисква геометрия, макар и не директно Вороной, концепциите помагат.
UVa 10002 - Center of Masses: Работа с полигони.
SPOJ CLOPPAIR: Най-близка двойка точки (Divide and Conquer е по-бърз, но Вороной също решава задачата).
IOI 2007 - Aliens: Може да изисква най-малка ограждаща окръжност.

Съвет: В състезания, ако задачата изисква Вороной, първо помислете дали не може да се реши с: * Най-близка двойка точки (Divide & Conquer). * Конвексна обвивка. * Половинни равнини (Half-plane intersection). Диаграмата на Вороной е "тежката артилерия".

5. Практически съвети за имплементация

5.1. Floating Point проблеми

При работа с геометрични алгоритми често се появяват проблеми с точността на дробните числа:

const double EPS = 1e-9;

bool doubleEquals(double a, double b) {
    return abs(a - b) < EPS;
}

5.2. Детерминанти и ориентация

За проверка дали три точки са в посока на часовниковата стрелка или обратно:

double cross(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

// Връща: > 0 (counter-clockwise), < 0 (clockwise), = 0 (collinear)

Това е полезно при построяване на Convex Hull, което е стъпка преди Delaunay.

6. Приложения на Delaunay триангулация

6.1. Mesh Generation (Генериране на мрежи)

В компютърната графика и симулациите (крайни елементи), Delaunay триангулацията се използва за генериране на качествени триъгълни мрежи.

6.2. Интерполация на терени

Ако имате множество точки с височини (например от GPS данни), можете да построите триангулация и да интерполирате височината в произволна точка.

6.3. Планиране на пътища (Path Planning)

В роботиката, Voronoi диаграмата помага за намиране на пътища, които са максимално далеч от препятствия.

7. Свързани структури

7.1. Изпъкнала обвивка (Convex Hull)

Външната граница на Delaunay триангулацията винаги е изпъкналата обвивка на точките. Ако ви трябва само тя, използвайте алгоритъм на Graham или Jarvis (по-прост за имплементация).

7.2. Най-близка двойка точки

Може да се реши с Divide and Conquer за \(O(N \log N)\), което е по-лесно от Voronoi. Но теоретично, Voronoi също решава този проблем.

7.3. Euclidean Minimum Spanning Tree

MST на точки в равнината, където ребрата са евклидовите разстояния. Може да се построи за \(O(N \log N)\), като първо се направи Delaunay триангулация (която съдържа всички ребра на MST).

8. Още примери и задачи

Задача: Nearest Airport

Имате \(N\) летища на картата. За дадена точка \((x, y)\), намерете най-близкото летище.

Решение: 1. Построете Voronoi диаграма. 2. За всяка точка, определете в коя клетка попада (Point Location problem - \(O(\log N)\) след препроцесинг).

Задача: Largest Empty Circle

Намерете най-голямата окръжност, която не съдържа нито една от дадените точки.

Решение: Центърът е или връх на Voronoi диаграмата, или лежи на изпъкналата обвивка.

🏁 Финални препоръки

Voronoi и Delaunay са теоретично красиви и мощни, но рядко се имплементират от нулата в състезания.
Ако задачата може да се реши с по-прости методи (sweep line, binary search, convex hull), предпочетете ги.
Ако решите да имплементирате Bowyer-Watson, тествайте добре с малки примери и ръбни случаи (колинеарни точки, cocircular точки).
За продукционен код или научни изследвания, използвайте библиотеки като CGAL (C++) или SciPy (Python).

Диаграмите на Voronoi са фундаментална структура с приложения в много области - от компютърна графика до биология и градско планиране!