Выпуклая оболочка и заворачивание подарка

Если ты знаешь, что такое выпуклая оболочка, как работает заворачивание подарка, почему оно стоит n · h и что делать с точками на одной прямой, листай до «Теперь сам».

Как думаешь, сколько это стоит

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

Ответь себе до чтения: сколько поворотов придётся посчитать для двенадцати гвоздей, если на каждом шаге выбирать следующий гвоздь перебором всех? И что будет, если гвоздей сто и все они стоят на дуге - то есть резинка касается каждого? Ответ для двенадцати - 77 поворотов, для ста гвоздей на дуге - 9900, то есть рост квадратичный.

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

Заворачивание подарка. Ты прижимаешь край бумаги к коробке в одной точке и поворачиваешь лист вокруг неё, пока бумага не упрётся в следующий угол. Упёрлась - этот угол становится новой осью, и лист поворачивается дальше. Бумага никогда не уходит внутрь коробки: она касается только выступающих углов.

Ровно так работает алгоритм. Текущая вершина - ось. Из всех точек выбирается та, до которой «поворачивающийся лист» дойдёт первым, - то есть та, относительно которой все остальные точки лежат по одну сторону. На её место переносится ось, и так до возвращения к старту.

Механизм: выпуклость и одна сторона

Множество выпукло, если вместе с любыми двумя своими точками оно содержит весь отрезок между ними. Квадрат выпуклый, буква Г - нет: отрезок между концами её ножек проходит снаружи. Выпуклая оболочка - наименьшее выпуклое множество, содержащее все точки. Для конечного набора это выпуклый многоугольник с вершинами в некоторых точках набора (или отрезок, если все точки на одной прямой, и сама точка, если она одна).

Почему ребро оболочки определяется поворотом. Отрезок ab между двумя точками набора - ребро оболочки ровно тогда, когда все остальные точки лежат по одну сторону от прямой ab, а точки на самой прямой - между a и b (иначе ab - только кусок ребра, до более далёкой точки). Если с обеих сторон есть точки, через эту прямую оболочка «перешагивает», и ab - диагональ, а не край. Сторона - это знак поворота.

Заворачивание подарка. Старт - самая левая точка (при равенстве - самая нижняя): она точно вершина оболочки, левее её ничего нет. Дальше на каждом шаге:

кандидат = любая точка, кроме текущей
для каждой точки p:
    если p справа от луча (текущая → кандидат):
        кандидат = p          луч поворачивается по часовой
текущая = кандидат            все точки теперь слева от ребра
стоп, когда вернулись к старту

Луч поворачивается к каждой точке, лежащей правее, - значит, в конце правее не остаётся никого, и ребро «текущая → кандидат» оставляет все точки слева: это ребро оболочки, а обход идёт против часовой стрелки.

Точки на одной прямой. Если p лежит на луче (поворот равен нулю), берут более далёкую: тогда средние точки ребра не попадут в оболочку как лишние вершины, а вершины на продолжении ребра не потеряются.

Правило

Выпуклая оболочка - выпуклый многоугольник с вершинами в точках набора, содержащий все точки. Отрезок - её ребро, если все остальные точки лежат по одну сторону от него. Заворачивание подарка начинает с самой левой точки и на каждом шаге проходом по всем точкам выбирает следующую вершину так, чтобы никто не остался справа; при нулевом повороте берёт дальнюю. Время O(n · h).

Разбор: двенадцать гвоздей

schet = [0]

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

def dal(a, b):
    return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2

def dzharvis(tochki):
    start = min(tochki)
    obolochka = []
    tek = start
    while True:
        obolochka.append(tek)
        kand = tochki[0]
        if kand == tek:
            kand = tochki[1]
        for p in tochki:
            if p == tek:
                continue
            z = povorot(tek, kand, p)
            if z < 0 or (z == 0 and dal(tek, p) > dal(tek, kand)):
                kand = p
        tek = kand
        if tek == start:
            break
    return obolochka

gvozdi = [[2, 1], [6, 0], [9, 3], [4, 4], [7, 6], [1, 5],
          [3, 8], [5, 2], [8, 8], [0, 3], [6, 5], [4, 7]]
o = dzharvis(gvozdi)
print(o)
print(len(gvozdi), len(o), schet[0])

[[0, 3], [2, 1], [6, 0], [9, 3], [8, 8], [3, 8], [1, 5]]
12 7 77

min(tochki) сравнивает пары как Python сравнивает списки - сначала x, при равенстве y, - и даёт самую левую нижнюю точку (0, 3). Резинка касается семи гвоздей из двенадцати, обход против часовой стрелки: вниз-вправо к (2, 1) и (6, 0), вверх к (9, 3) и (8, 8), влево к (3, 8), вниз к (1, 5).

Поворотов 77: семь шагов по 11 точек. Это и есть n · h - на каждой из h вершин проход по всем остальным точкам. Сколько точек внутри, роли почти не играет: внутренние гвозди (4, 4), (5, 2), (6, 5), (7, 6), (4, 7) проверялись на каждом шаге, хотя ни разу не стали ответом.

Разбор: когда h велико

Цена n · h хороша, когда вершин мало, и плоха, когда их много. Сравним два набора одного размера: точки на параболе (x, x²) - все они вершины оболочки - и случайные точки в квадрате.

schet = [0]

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

def dal(a, b):
    return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2

def dzharvis(tochki):
    start = min(tochki)
    obolochka = []
    tek = start
    while True:
        obolochka.append(tek)
        kand = tochki[0]
        if kand == tek:
            kand = tochki[1]
        for p in tochki:
            if p == tek:
                continue
            z = povorot(tek, kand, p)
            if z < 0 or (z == 0 and dal(tek, p) > dal(tek, kand)):
                kand = p
        tek = kand
        if tek == start:
            break
    return obolochka

import random
random.seed(1)
for n in [20, 40, 80]:
    parabola = []
    for x in range(n):
        parabola.append([x, x * x])
    kvadrat = []
    for i in range(n):
        x = random.randint(0, 10000)
        kvadrat.append([x, random.randint(0, 10000)])
    schet[0] = 0
    h1 = len(dzharvis(parabola))
    s1 = schet[0]
    schet[0] = 0
    h2 = len(dzharvis(kvadrat))
    s2 = schet[0]
    print(n, h1, s1, h2, s2)

20 20 380 7 133
40 40 1560 9 351
80 80 6320 11 869

Столбцы: число точек, вершин и поворотов на параболе, вершин и поворотов в квадрате. На параболе все точки на оболочке, h = n, и повороты растут вчетверо при удвоении: 380, 1560, 6320 - квадрат. В квадрате вершин оболочки 7, 9, 11 - они растут медленно, в среднем как логарифм для случайных точек квадрата, - и повороты растут в два с половиной раза, а не вчетверо.

Вывод: у заворачивания подарка время зависит от ответа, а не только от входа. Такие алгоритмы называют чувствительными к выходу. Это не недостаток и не достоинство само по себе: на случайных точках в квадрате, где вершин мало, заворачивание не уступает алгоритму с сортировкой из следующего урока, на точках «по кругу» - заметно медленнее.

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

Нет правила для нуля. Если при нулевом повороте не выбирать дальнюю точку, на ребре с тремя точками подряд алгоритм возьмёт среднюю точку как лишнюю вершину или перепрыгнет дальнюю - смотря в каком порядке точки лежат в списке. Ответ начинает зависеть от порядка входа.

Повторяющиеся точки. Две одинаковые точки дают нулевой вектор, поворот относительно него всегда ноль, и выбор «следующей» становится случайным. Дубликаты убирают до начала: после sorted(tochki) одинаковые стоят рядом, и из каждой серии берут одну. А набор из одной точки - отдельный случай: программа выше берёт tochki[1] и на нём упадёт.

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

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

Игровой движок окружает сложную модель выпуклой оболочкой и сначала проверяет столкновения оболочек: для выпуклых тел это просто и быстро. Аналитик строит оболочку точек доставки, чтобы увидеть фактическую зону обслуживания, - ST_ConvexHull в PostGIS. Компьютерное зрение ищет «вмятины» контура руки - места, где контур отходит от своей оболочки, - так считают пальцы в OpenCV. Оболочка - первый шаг и в задаче о самой далёкой паре точек: обе точки обязательно её вершины.

Теперь сам

1. Точки (0, 0), (4, 0), (2, 1), (4, 4), (0, 4), (2, 2). Какие из них на оболочке? Сколько поворотов посчитает заворачивание?
2. Точки (0, 0), (2, 0), (4, 0), (2, 3). Попадёт ли (2, 0) в оболочку при правиле «на нуле брать дальнюю»?
3. Почему старт можно брать и в самой нижней точке, а не в самой левой?