Выпуклая оболочка: алгоритм Эндрю, Грэхем и коллинеарные точки
Выпуклая оболочка простыми словами: векторное произведение и ориентация, алгоритм Эндрю (monotone chain) и Грэхема за O(n log n), коллинеарные точки и типичные ошибки. Код на 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-компонента векторного произведения векторов и :
Знак отвечает на вопрос «куда мы повернём, если пойдём из O в A, а потом в B»:
cross(o, a, b) | Что значит |
|---|---|
> 0 | поворот налево (против часовой) — B слева от луча OA |
< 0 | поворот направо (по часовой) |
== 0 | O, 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
Пар , на каждую проверка за — итого . Для это операций, безнадёжно. Зато это хороший тест-оракул: на маленьких случайных наборах сверяйте с ним быстрый алгоритм.
Промежуточный вариант — заворачивание подарка (алгоритм Джарвиса): стартуем с самой левой точки и каждый раз ищем следующую вершину, относительно которой все точки лежат слева. Это , где — число вершин оболочки. Хорошо, если маленькое, и плохо, если все точки на окружности: тогда и выходит .
Алгоритм Эндрю (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), и именно его чаще показывают в учебниках. Идея та же — стек и проверка поворота, — но порядок обхода другой:
- Берём опорную точку
p0— самую нижнюю (при равенстве — самую левую). Она точно на оболочке. - Сортируем остальные точки по полярному углу относительно
p0. - Обходим их по порядку и держим в стеке только левые повороты.
Сортировать по углу удобно тем же 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) |
На собеседовании выбирайте Эндрю: меньше мест, где можно ошибиться. Грэхема стоит знать, чтобы узнать его в чужом коде и ответить на вопрос «а чем они отличаются».
Сложность
Время: . Сортировка — , проход стеком — : каждая точка один раз входит в стек и не больше одного раза выходит. Подробнее о том, почему амортизированный while внутри for не даёт , — в статье про Big O.
Память: на отсортированный массив и стеки.
Быстрее нельзя. К построению оболочки сводится сортировка: возьмите числа , превратите их в точки на параболе. Все они вершины оболочки, и обход оболочки выдаёт их в отсортированном порядке. Поэтому в модели сравнений нижняя граница — та же, что у сортировки.
Есть оговорка: если мало, бывают алгоритмы, чувствительные к размеру ответа. Джарвис — , алгоритм Чана — . На собеседовании их обычно достаточно назвать.
Коллинеарные точки: где ломается почти все
Коллинеарные точки — это точки, лежащие на стороне оболочки, но не в её углах. Сначала решите, нужны ли они вам:
- «вершины многоугольника» (площадь, диаметр, проверка точки внутри) — коллинеарные не нужны;
- «все точки на границе» (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) лежат на прямой , но:
print(cross((0.1, 0.3), (0.2, 0.6), (0.7, 2.1))) # 2.7755575615628914e-17
Не ноль. Если координаты дробные, сравнивайте с эпсилоном (cross > eps) или, если это возможно, переведите их в целые умножением.
Переполнение в Java/C++. В Python целые не переполняются. В Java и C++ при координатах до разности бывают до , а их произведение — до . В int это не влезает, нужен long / long long. Сама разность двух произведений доходит до — в 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
Диаметр — самая дальняя пара точек. Она всегда среди вершин оболочки, и её находят вращающимися калиперами за — по сути, два указателя, бегущие по многоугольнику.
Точка внутри выпуклого многоугольника — бинарным поиском по углу из одной вершины за .
Всем этим алгоритмам коллинеарные вершины только мешают, поэтому для них берите версию с <= 0.
На собеседовании
Геометрия встречается реже, чем графы или динамика, но если встречается, то почти всегда в виде оболочки или cross. Что обычно проверяют:
- Можете ли вы вывести
crossи объяснить смысл знака. Это база, без неё дальше не идут. - Знаете ли вы хоть один O(n log n) алгоритм — и почему проход стеком линейный.
- Вырожденные случаи: все точки на прямой, дубликаты, одна точка. Хороший кандидат сам их называет до того, как его спросят.
- Коллинеарные точки: нужны ли они в ответе. Уточните это у интервьюера в самом начале — в Erect the Fence от этого зависит вся корректность.
Хорошая последовательность ответа: «Отсортирую точки по x, построю нижнюю и верхнюю цепочки стеком, поворот проверяю векторным произведением в целых числах. Сложность — из-за сортировки, проход линейный. Точки на сторонах нужны? Тогда сравниваю строго и убираю повторы для случая, когда все точки на одной прямой».
Задачи, на которых стоит потренироваться:
- Erect the Fence (LeetCode 587) — выпуклая оболочка с точками на границе, ровно все ловушки из этой статьи;
- Max Points on a Line (LeetCode 149) — коллинеарность без деления и float;
- Valid Boomerang (LeetCode 1037) — разминка: три точки не на одной прямой — это
cross != 0.
Перед сдачей прогоните своё решение на случайных маленьких наборах против наивного — так ловятся почти все ошибки со знаками и вырожденными случаями.