Выпуклая оболочка: алгоритм Эндрю, Грэхем и коллинеарные точки

Выпуклая оболочка простыми словами: векторное произведение и ориентация, алгоритм Эндрю (monotone chain) и Грэхема за O(n log n), коллинеарные точки и типичные ошибки. Код на Python.

12 мин чтенияалгоритмы · геометрия · python

Коротко

ПараметрЗначение
Задачанайти минимальный выпуклый многоугольник, содержащий все точки
Главный примитиввекторное произведение cross(o, a, b) — поворот налево, направо или прямо
Алгоритм Эндрю (monotone chain)O(n log n), сортировка по (x, y) + две цепочки на стеке
Алгоритм ГрэхемаO(n log n), сортировка по полярному углу + стек
Нижняя границаΩ(n log n) — быстрее сортировки в общем случае нельзя
Главный источник баговколлинеарные точки, дубликаты, все точки на одной прямой

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

Что такое выпуклая оболочка

Представьте, что точки — это гвозди, вбитые в доску. Натяните вокруг них резинку и отпустите. Резинка обхватит крайние гвозди и ляжет многоугольником — это и есть выпуклая оболочка.

  •           •              •-----------•
      •   •                  |   ·   ·    \
  •     •        •    →      •     ·        •
     •     •                  \  ·     ·   /
        •                       •---------•

Формально — это наименьшее выпуклое множество, содержащее все точки. На практике нам нужен список вершин этого многоугольника, обычно в порядке обхода против часовой стрелки.

Где это нужно:

  • площадь или периметр «забора» вокруг набора объектов;
  • диаметр множества точек — самая дальняя пара всегда лежит на оболочке;
  • проверка, пересекаются ли два облака точек;
  • предобработка для коллизий в играх и робототехнике.

На собеседованиях самая известная задача — Erect the Fence (LeetCode 587, Hard): дано множество деревьев, верните те, что лежат на заборе. Подвох в слове «на»: точки, лежащие на стороне забора, тоже нужно вернуть. Об этом подробно ниже.

Векторное произведение: весь фундамент

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

def cross(o, a, b): return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

Это z-компонента векторного произведения векторов OA⃗\vec{OA} и OB⃗\vec{OB}:

OA⃗×OB⃗=(ax−ox)(by−oy)−(ay−oy)(bx−ox)\vec{OA} \times \vec{OB} = (a_x - o_x)(b_y - o_y) - (a_y - o_y)(b_x - o_x)

Знак отвечает на вопрос «куда мы повернём, если пойдём из O в A, а потом в B»:

cross(o, a, b)Что значит
> 0поворот налево (против часовой) — B слева от луча OA
< 0поворот направо (по часовой)
== 0O, A, B лежат на одной прямой
print(cross((0, 0), (1, 0), (0, 1))) # 1 — налево print(cross((0, 0), (0, 1), (1, 0))) # -1 — направо print(cross((0, 0), (1, 1), (2, 2))) # 0 — на одной прямой

Бонус: модуль cross — удвоенная площадь треугольника OAB. Отсюда формула площади многоугольника (формула шнурования), к которой вернёмся в конце.

Почему не углы через atan2? Потому что cross работает в целых числах и даёт точный ответ. Углы — это числа с плавающей точкой, и три точки на одной прямой легко превращаются в «почти на одной прямой». На коллинеарных случаях это ломает всё.

Наивное решение за O(n³)

Ключевое наблюдение: отрезок AB — сторона оболочки, если все остальные точки лежат по одну сторону от прямой AB.

def naive_hull_edges(points): # предполагаем, что никакие три точки не лежат на одной прямой edges = [] for a in points: for b in points: if a != b and all(cross(a, b, c) >= 0 for c in points): edges.append((a, b)) # все точки слева от a→b return edges

Пар O(n2)O(n^2), на каждую проверка за O(n)O(n) — итого O(n3)O(n^3). Для n=104n = 10^4 это 101210^{12} операций, безнадёжно. Зато это хороший тест-оракул: на маленьких случайных наборах сверяйте с ним быстрый алгоритм.

Промежуточный вариант — заворачивание подарка (алгоритм Джарвиса): стартуем с самой левой точки и каждый раз ищем следующую вершину, относительно которой все точки лежат слева. Это O(nh)O(nh), где hh — число вершин оболочки. Хорошо, если hh маленькое, и плохо, если все точки на окружности: тогда h=nh = n и выходит O(n2)O(n^2).

Алгоритм Эндрю (monotone chain)

Идея: отсортируем точки по x (при равенстве — по y). Самая левая и самая правая точки точно лежат на оболочке. Они делят её на две цепочки:

  • нижнюю — идём слева направо по низу;
  • верхнюю — идём справа налево по верху.

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

def convex_hull(points): pts = sorted(set(points)) # сортировка по (x, y) и удаление дубликатов if len(pts) <= 2: return pts lower = [] for p in pts: while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) upper = [] for p in reversed(pts): while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) # последняя точка каждой цепочки — первая точка другой return lower[:-1] + upper[:-1]

Результат — вершины против часовой стрелки, начиная с самой левой нижней точки. Точки на сторонах (коллинеарные) не попадают в ответ — за это отвечает <= 0.

Это тот же приём, что и в монотонном стеке: поддерживаем инвариант на вершине стека и выталкиваем всё, что его нарушает.

Разбор на примере

Точки: (0,0), (2,0), (1,1), (2,2), (0,2), (1,0), (3,1).

y
2  •(0,2)     •(2,2)
1        •(1,1)     •(3,1)
0  •(0,0) •(1,0) •(2,0)
   0      1      2      3   x

После сортировки: (0,0) (0,2) (1,0) (1,1) (2,0) (2,2) (3,1).

Нижняя цепочка:

ТочкаЧто происходитСтек
(0,0)кладём(0,0)
(0,2)кладём(0,0) (0,2)
(1,0)cross((0,0),(0,2),(1,0)) = -2 — направо, выкидываем (0,2)(0,0) (1,0)
(1,1)налево, кладём(0,0) (1,0) (1,1)
(2,0)направо — выкидываем (1,1); потом cross = 0 — прямо, выкидываем (1,0)(0,0) (2,0)
(2,2)кладём(0,0) (2,0) (2,2)
(3,1)направо — выкидываем (2,2)(0,0) (2,0) (3,1)

Обратите внимание на шаг с (2,0): точка (1,0) лежит на нижней стороне между (0,0) и (2,0), и <= 0 её выкинул.

Верхняя цепочка (идём справа налево): (3,1) (2,2) (0,2) (0,0) — (2,0), (1,1) и (1,0) по дороге выталкиваются.

Склеиваем без повторов концов: (0,0) (2,0) (3,1) (2,2) (0,2). Пятиугольник против часовой стрелки.

Почему это корректно

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

Алгоритм Грэхема

Грэхем (1972) появился раньше Эндрю (1979), и именно его чаще показывают в учебниках. Идея та же — стек и проверка поворота, — но порядок обхода другой:

  1. Берём опорную точку p0 — самую нижнюю (при равенстве — самую левую). Она точно на оболочке.
  2. Сортируем остальные точки по полярному углу относительно p0.
  3. Обходим их по порядку и держим в стеке только левые повороты.

Сортировать по углу удобно тем же cross — без atan2:

from functools import cmp_to_key def graham(points): pts = list(set(points)) if len(pts) <= 2: return sorted(pts) p0 = min(pts, key=lambda p: (p[1], p[0])) others = [p for p in pts if p != p0] def dist2(p): return (p[0] - p0[0]) ** 2 + (p[1] - p0[1]) ** 2 def compare(a, b): c = cross(p0, a, b) if c != 0: return -1 if c > 0 else 1 # a раньше, если b левее луча p0→a return dist2(a) - dist2(b) # на одном луче — сначала ближняя others.sort(key=cmp_to_key(compare)) stack = [p0] for p in others: while len(stack) >= 2 and cross(stack[-2], stack[-1], p) <= 0: stack.pop() stack.append(p) return stack

Сравнение через cross корректно, потому что все точки лежат в верхней полуплоскости относительно p0 (она самая нижняя): углы от 0 до 180°, и «левее» однозначно значит «больше угол».

Эндрю или Грэхем

ЭндрюГрэхем
Сортировкапо (x, y), встроеннаяпо углу, свой компаратор
Опорная точкане нужнанужна
Коллинеарные точкименяем <= на < + один особый случайещё и разворот последнего луча
Длина кодакорочедлиннее
СложностьO(n log n)O(n log n)

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

Сложность

Время: O(nlog⁡n)O(n \log n). Сортировка — O(nlog⁡n)O(n \log n), проход стеком — O(n)O(n): каждая точка один раз входит в стек и не больше одного раза выходит. Подробнее о том, почему амортизированный while внутри for не даёт O(n2)O(n^2), — в статье про Big O.

Память: O(n)O(n) на отсортированный массив и стеки.

Быстрее нельзя. К построению оболочки сводится сортировка: возьмите числа x1,…,xnx_1, \dots, x_n, превратите их в точки (xi,xi2)(x_i, x_i^2) на параболе. Все они вершины оболочки, и обход оболочки выдаёт их в отсортированном порядке. Поэтому в модели сравнений нижняя граница Ω(nlog⁡n)\Omega(n \log n) — та же, что у сортировки.

Есть оговорка: если hh мало, бывают алгоритмы, чувствительные к размеру ответа. Джарвис — O(nh)O(nh), алгоритм Чана — O(nlog⁡h)O(n \log h). На собеседовании их обычно достаточно назвать.

Коллинеарные точки: где ломается почти все

Коллинеарные точки — это точки, лежащие на стороне оболочки, но не в её углах. Сначала решите, нужны ли они вам:

  • «вершины многоугольника» (площадь, диаметр, проверка точки внутри) — коллинеарные не нужны;
  • «все точки на границе» (Erect the Fence) — нужны.

Строгое и нестрогое сравнение

Вся разница в одном символе в условии выталкивания:

УсловиеЧто делаем при cross == 0Результат
cross(...) <= 0выкидываем среднюю точкутолько углы
cross(...) < 0оставляемуглы + точки на сторонах

Казалось бы, поменяли знак — и готово. Но нет.

Ловушка 1: все точки на одной прямой

Возьмём (0,0), (1,1), (2,2) и вариант с < 0. Ни одного поворота нет, поэтому нижняя цепочка — все три точки, верхняя — тоже все три, только в обратном порядке. Склеиваем:

# вариант с < 0 без защиты print(hull_bad([(0, 0), (1, 1), (2, 2)])) # [(0, 0), (1, 1), (2, 2), (1, 1)] — (1, 1) дважды

В LeetCode 587 это неверный ответ. Лечится удалением повторов с сохранением порядка:

def hull_with_collinear(points): pts = sorted(set(points)) if len(pts) <= 2: return pts lower = [] for p in pts: while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0: lower.pop() lower.append(p) upper = [] for p in reversed(pts): while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0: upper.pop() upper.append(p) hull = lower[:-1] + upper[:-1] # все точки на одной прямой: нижняя и верхняя цепочки совпали return list(dict.fromkeys(hull)) pts = [(0, 0), (2, 0), (1, 1), (2, 2), (0, 2), (1, 0), (3, 1)] print(hull_with_collinear(pts)) # [(0, 0), (1, 0), (2, 0), (3, 1), (2, 2), (0, 2)]

В обычном случае повторов в hull нет, и dict.fromkeys ничего не меняет. А в вырожденном — оставляет каждую точку прямой по одному разу.

Вариант с <= 0 от этой проблемы защищён: на прямой он оставляет только два крайних конца.

Ловушка 2: последний луч у Грэхема

У Грэхема с < 0 есть свой подвох. Точки на одном луче из p0 мы отсортировали от ближней к дальней. Для всех лучей это правильно, кроме последнего: по нему обход возвращается к p0, и идти надо от дальней точки к ближней.

(0,2) •------• (2,2)
      |      |
(0,1) •      |
      |      |
(0,0) •------• (2,0)

Порядок обхода: (0,0) → (2,0) → (2,2) → (0,1) → (0,2). Из (2,2) мы сначала прыгаем к (0,1), потом к (0,2) — это поворот направо, и (0,1) выкидывается, хотя лежит на границе. Решение — развернуть хвост отсортированного списка, где точки коллинеарны с последней:

# после others.sort(...), если нужны коллинеарные точки i = len(others) - 1 while i > 0 and cross(p0, others[i - 1], others[-1]) == 0: i -= 1 others[i:] = reversed(others[i:])

Если это забыть, тесты с точками только на нижней и правой сторонах пройдут, а на левой — упадут. Ещё одна причина выбирать Эндрю: у него этой проблемы нет.

Ловушка 3: дубликаты

Одинаковые точки дают cross == 0 с чем угодно. С <= 0 они выталкиваются сами, но не всегда: если все точки совпадают, цепочка не выродится до одной точки. С < 0 дубликаты остаются в ответе. Поэтому set(points) в начале — не украшение, а часть алгоритма.

Другие типичные ошибки

Числа с плавающей точкой. Точки (0.1, 0.3), (0.2, 0.6), (0.7, 2.1) лежат на прямой y=3xy = 3x, но:

print(cross((0.1, 0.3), (0.2, 0.6), (0.7, 2.1))) # 2.7755575615628914e-17

Не ноль. Если координаты дробные, сравнивайте с эпсилоном (cross > eps) или, если это возможно, переведите их в целые умножением.

Переполнение в Java/C++. В Python целые не переполняются. В Java и C++ при координатах до 10910^9 разности бывают до 2⋅1092 \cdot 10^9, а их произведение — до 4⋅10184 \cdot 10^{18}. В int это не влезает, нужен long / long long. Сама разность двух произведений доходит до 8⋅10188 \cdot 10^{18} — в long ещё помещается, но запас небольшой.

Забыли случай n <= 2. Одна-две точки — это и есть оболочка. Без проверки одна точка теряется: lower[:-1] + upper[:-1] для [(5, 5)] вернёт пустой список.

Склеили цепочки без [:-1]. Тогда самая левая и самая правая точки попадут в ответ дважды.

Перепутали знак. С >= 0 вместо <= 0 вы получите обход по часовой стрелке — или, если перепутать только в одной цепочке, вообще не многоугольник. Проверка простая: на квадрате (0,0) (1,0) (1,1) (0,1) с внутренней точкой (0.5, 0.5) должны остаться четыре угла.

Сортировка по углу через atan2. Работает, но на коллинеарных точках и при углах, близких к 180°, требует аккуратности. cross в компараторе — точнее и не медленнее.

Что делать с оболочкой дальше

Площадь — формула шнурования (Гаусса): сумма cross соседних вершин относительно начала координат.

def polygon_area(poly): s = 0 for i in range(len(poly)): x1, y1 = poly[i] x2, y2 = poly[(i + 1) % len(poly)] s += x1 * y2 - x2 * y1 return abs(s) / 2 print(polygon_area(convex_hull(pts))) # 5.0

Диаметр — самая дальняя пара точек. Она всегда среди вершин оболочки, и её находят вращающимися калиперами за O(h)O(h) — по сути, два указателя, бегущие по многоугольнику.

Точка внутри выпуклого многоугольника — бинарным поиском по углу из одной вершины за O(log⁡h)O(\log h).

Всем этим алгоритмам коллинеарные вершины только мешают, поэтому для них берите версию с <= 0.

На собеседовании

Геометрия встречается реже, чем графы или динамика, но если встречается, то почти всегда в виде оболочки или cross. Что обычно проверяют:

  1. Можете ли вы вывести cross и объяснить смысл знака. Это база, без неё дальше не идут.
  2. Знаете ли вы хоть один O(n log n) алгоритм — и почему проход стеком линейный.
  3. Вырожденные случаи: все точки на прямой, дубликаты, одна точка. Хороший кандидат сам их называет до того, как его спросят.
  4. Коллинеарные точки: нужны ли они в ответе. Уточните это у интервьюера в самом начале — в Erect the Fence от этого зависит вся корректность.

Хорошая последовательность ответа: «Отсортирую точки по x, построю нижнюю и верхнюю цепочки стеком, поворот проверяю векторным произведением в целых числах. Сложность — O(nlog⁡n)O(n \log n) из-за сортировки, проход линейный. Точки на сторонах нужны? Тогда сравниваю строго и убираю повторы для случая, когда все точки на одной прямой».

Задачи, на которых стоит потренироваться:

  • Erect the Fence (LeetCode 587) — выпуклая оболочка с точками на границе, ровно все ловушки из этой статьи;
  • Max Points on a Line (LeetCode 149) — коллинеарность без деления и float;
  • Valid Boomerang (LeetCode 1037) — разминка: три точки не на одной прямой — это cross != 0.

Перед сдачей прогоните своё решение на случайных маленьких наборах против наивного O(n3)O(n^3) — так ловятся почти все ошибки со знаками и вырожденными случаями.

Потренироваться в спокойной обстановке

Все задачи