Диаграмма Вороного: у каждого объекта своя область ближайших точек

Если ты знаешь, почему ячейки Вороного выпуклы, что такое вершина как центр пустой окружности, сколько вершин и рёбер у диаграммы и какие ячейки уходят в бесконечность, листай до «Теперь сам».

Как думаешь, какой формы зоны

Пять почтовых отделений в городе. Каждый житель ходит в ближайшее. Нарисуй мысленно зоны: кто куда ходит. Это круги вокруг отделений? Квадраты? Кляксы произвольной формы?

Ответь себе до чтения - и заодно подумай, сколько «углов» будет у этой карты, если отделений тысяча. Ответ: зоны - выпуклые многоугольники с прямыми границами, а углов - точек, где сходятся три зоны, - не больше 2n − 5, то есть меньше двух тысяч на тысячу отделений.

На что это похоже

Пожар в степи, загоревшийся одновременно в пяти местах. Огонь идёт во все стороны с одной скоростью, и там, где встречаются два фронта, трава уже выгорела - фронты гаснут. Линии встречи - границы зон: каждая выжженная полоса принадлежит тому очагу, от которого огонь дошёл быстрее. Точки, куда огонь пришёл одновременно от трёх очагов, - вершины диаграммы.

Механизм: полуплоскости, пустые окружности и счёт

Ячейка - пересечение полуплоскостей. Точка ближе к p, чем к q, ровно тогда, когда она по ту же сторону от серединного перпендикуляра отрезка pq, что и p. Это полуплоскость. Ячейка p - точки, ближайшие к p, то есть пересечение таких полуплоскостей по всем остальным центрам. Пересечение выпуклых множеств выпукло, и границы у полуплоскостей прямые - отсюда выпуклые многоугольники.

Рёбра и вершины. Ребро между ячейками p и q - точки, равноудалённые от p и q и не ближе ни к кому третьему. Вершина - точка, равноудалённая от трёх центров p, q, r: это центр окружности через них, и внутри этой окружности нет других центров - иначе тот центр был бы ближе. Обратно: окружность через три центра, внутри которой пусто, даёт вершину. Проверить пустоту - тот же определитель «точка внутри окружности», что понадобится в главе о триангуляции ДелонеРазбирается в разделе 23, глава «Триангуляция Делоне и её свойства»: Пустая окружность и переворот рёбер: как получить Делоне из любой триангуляции, - и считается он точно, в целых.

Бесконечные ячейки. Ячейка центра не ограничена ровно тогда, когда центр лежит на границе выпуклой оболочки - в вершине или на стороне: в сторону «наружу» от оболочки никто не может оказаться ближе него.

Почему диаграмма маленькая. Добавим одну вершину «на бесконечности», куда уходят все бесконечные рёбра, - получится плоский граф: V + 1 вершин, E рёбер, n граней-ячеек. Формула Эйлера: (V + 1) − E + n = 2. У каждой вершины не меньше трёх рёбер (у обычной в общем положении - ровно три, у бесконечной - h), каждое ребро - у двух вершин: 2E ≥ 3(V + 1). Из этих двух соотношений V ≤ 2n − 5 и E ≤ 3n − 6. А если h центров на оболочке, никакие три не лежат на одной прямой и никакие четыре - на одной окружности, вершин ровно 2n − 2 − h.

Правило

Ячейка Вороного - выпуклый многоугольник, пересечение полуплоскостей серединных перпендикуляров. Вершина - центр пустой окружности через три центра, ребро - точки, равноудалённые от двух центров при пустой окружности. Бесконечны ячейки центров на границе выпуклой оболочки. Размер линейный: вершин не больше 2n − 5, рёбер не больше 3n − 6.

Разбор: зоны пяти отделений

Нарисуем зоны прямо перебором: для каждой клетки сетки 40 × 16 найдём ближайшее отделение. Буква - отделение, @ - само отделение, точка - клетка, равноудалённая от двух.

otdeleniya = [[6, 3], [30, 4], [18, 9], [8, 13], [33, 14]]
bukvy = "ABCDE"
for y in range(15, -1, -1):
    stroka = ""
    for x in range(40):
        luchshee = -1
        d_min = 10 ** 9
        nichya = False
        for i in range(len(otdeleniya)):
            p = otdeleniya[i]
            d = (p[0] - x) ** 2 + (p[1] - y) ** 2
            if d < d_min:
                d_min = d
                luchshee = i
                nichya = False
            elif d == d_min:
                nichya = True
        if d_min == 0:
            stroka = stroka + "@"
        elif nichya:
            stroka = stroka + "."
        else:
            stroka = stroka + bukvy[luchshee].lower()
    print(stroka)

dddddddddddddddcccccccccceeeeeeeeeeeeeee
dddddddddddddddcccccccccceeeeeeee@eeeeee
dddddddd@dddddccccccccccc.eeeeeeeeeeeeee
ddddddddddddddcccccccccccceeeeeeeeeeeeee
ddddddddddddd.cccccccccccceeeeeeeeeeeeee
dddddddddddddcccccccccccccbbbeeeeeeeeeee
aa.ddddddddddccccc@cccccccbbbbbbeeeeeeee
aaaaaaa.ddddcccccccccccccbbbbbbbbbbeeeee
aaaaaaaaaaaacccccccccccccbbbbbbbbbbbbbbe
aaaaaaaaaaaa.cccccccccccbbbbbbbbbbbbbbbb
aaaaaaaaaaaaacccccccccccbbbbbbbbbbbbbbbb
aaaaaaaaaaaaa.cccccccccbbbbbbb@bbbbbbbbb
aaaaaa@aaaaaaacccccccccbbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaa.ccccccccbbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaacccccccbbbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaa.ccccccbbbbbbbbbbbbbbbbbb

Ячейка c зажата в середине, остальные упираются в края - их отделения на оболочке. Видно и то, что границы прямые, только нарисованные ступеньками сетки: например, граница a и c идёт ровной наклонной лесенкой. Точки - клетки ровно на границе.

Так на практике зоны часто и считают - перебором на растре. Это работает для картинки, но не для запросов: клеток миллионы, а отделений тысячи. Диаграмма хранит то же самое в O(n) рёбер, и ответ на запрос - это локализация точки в разбиении из прошлого урока, O(log n).

Разбор: вершины как пустые окружности

Двенадцать случайных центров. Перебираем все тройки и оставляем те, у которых описанная окружность пуста. Предикат v_kruge - определитель 3 × 3 в целых, его знак говорит, внутри ли четвёртая точка.

import random

def povorot(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def v_kruge(a, b, c, d):
    # больше нуля: d строго внутри окружности через a, b, c
    # (обход a, b, c против часовой); всё в целых - ответ точный
    m = []
    for p in [a, b, c]:
        dx = p[0] - d[0]
        dy = p[1] - d[1]
        m.append([dx, dy, dx * dx + dy * dy])
    return (m[0][0] * (m[1][1] * m[2][2] - m[1][2] * m[2][1])
            - m[0][1] * (m[1][0] * m[2][2] - m[1][2] * m[2][0])
            + m[0][2] * (m[1][0] * m[2][1] - m[1][1] * m[2][0]))

def obolochka(t):
    t = sorted(t)
    niz = []
    for p in t:
        while len(niz) >= 2 and povorot(niz[-2], niz[-1], p) <= 0:
            niz.pop()
        niz.append(p)
    verh = []
    for p in t[::-1]:
        while len(verh) >= 2 and povorot(verh[-2], verh[-1], p) <= 0:
            verh.pop()
        verh.append(p)
    return niz[:-1] + verh[:-1]

random.seed(3)
tochki = []
while len(tochki) < 12:
    p = [random.randint(0, 100), random.randint(0, 100)]
    if p not in tochki:
        tochki.append(p)
n = len(tochki)
vershiny = 0
primer = []
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            a, b, c = tochki[i], tochki[j], tochki[k]
            z = povorot(a, b, c)
            if z == 0:
                continue
            if z < 0:
                b, c = c, b
            pustaya = True
            for d in tochki:
                if d == a or d == b or d == c:
                    continue
                if v_kruge(a, b, c, d) > 0:
                    pustaya = False
            if pustaya:
                vershiny = vershiny + 1
                if len(primer) == 0:
                    primer = [a, b, c]
h = len(obolochka(tochki))
print(n, h, vershiny, 2 * n - 2 - h, 2 * n - 5)
print(primer)

12 5 17 17 19
[[30, 75], [77, 1], [69, 16]]

Двенадцать центров, пять на оболочке, 17 пустых окружностей - 17 вершин диаграммы. Формула 2n − 2 − h даёт ровно 24 − 2 − 5 = 17, верхняя граница 2n − 5 = 19. Вторая строка - первая найденная тройка: окружность через (30, 75), (77, 1), (69, 16) не содержит ни одного из двенадцати центров, и её центр - вершина диаграммы, где сходятся три ячейки.

Тройка - вершина, пока четыре центра не лежат на одной пустой окружности: тогда четыре тройки дали бы одну вершину, а счёт - четыре. Перебор троек стоит n⁴ - для двенадцати точек это мгновенно, для тысячи нет. Диаграмму строят за n · log n - алгоритмом Форчуна, которому посвящён следующий урок.

Что ломается без этого

Зоны по растру как ответ на запросы. Сетка грубая - соседние клетки границы путаются; сетка мелкая - миллиарды клеток. Диаграмма даёт точный ответ при линейной памяти.

Не та метрика. По улицам с прямоугольной сеткой ходят «по Манхэттену»: расстояние |dx| + |dy|. У такой диаграммы границы ломаные из отрезков под 45 и 90 градусов (а у центров на одной диагонали, как (0, 0) и (2, 2), ничья занимает целые углы плоскости), и евклидова диаграмма ей не замена.

Центры с разным весом. Если у отделений разная пропускная способность и зону хотят пропорциональной, обычная диаграмма не годится. Для этого есть взвешенные варианты, например диаграмма мощности, где вместо расстояния d² берут d² − w; её ячейки тоже выпуклые.

Зачем это в работе

Зоны обслуживания: доставка, скорая, базовые станции сотовой сети - в первом приближении это ячейки Вороного. Робот, которому надо держаться подальше от препятствий, едет по рёбрам диаграммы Вороного препятствий: ребро - это места, равноудалённые от двух ближайших препятствий, поэтому путь по рёбрам держит наибольший возможный зазор с обеих сторон. В биологии и материаловедении ячейки Вороного моделируют клетки ткани и зёрна металла. В играх диаграмму используют для генерации карт: страны, биомы, плиты. В Python - scipy.spatial.Voronoi через библиотеку Qhull.

Теперь сам

1. Центры (0, 0) и (4, 0). Как выглядит диаграмма Вороного?
2. Центры - вершины квадрата (0, 0), (4, 0), (4, 4), (0, 4). Сколько вершин у диаграммы и почему здесь не выполняется 2n − 2 − h?
3. У диаграммы 1000 центров, из них 30 на оболочке, четырёх на одной окружности нет. Сколько вершин и сколько бесконечных ячеек?