Выпуклая оболочка

Ниже все землетрясения силой от пяти баллов за 2015–2025 годы — больше девятнадцати тысяч точек. Карту материков никто не рисовал, но она проступает сама: эпицентры лежат вдоль границ тектонических плит, и Тихий океан обведён огненным кольцом. Выберите регион, и алгоритм построит вокруг его эпицентров забор — самый короткий выпуклый многоугольник, внутри которого все точки. Посмотрите, на скольких из них этот забор держится.

Из почти двухсот эпицентров Тянь-Шаня и Памира забор держат десять — остальные внутри. Такой многоугольник называют выпуклой оболочкой. Если вбить гвозди в точки и натянуть вокруг резинку, она примет форму выпуклой оболочки.

Идея

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

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

Налево или направо

Всё, что алгоритму нужно знать о геометрии, — в какую сторону поворачивает путь O → A → B. Ответ даёт знак псевдоскалярного (векторного) произведения векторов OA и OB:

Больше нуля — поворот налево, меньше — направо, ноль — три точки на одной прямой. Ни углов, ни тригонометрии, ни деления: только умножения и вычитания. Для целых координат ответ точный, и это важно — сравнивать углы через atan2 значит пустить в алгоритм погрешность плавающей точки. Подробнее о векторах и ориентации — векторы и ориентация.

Почему получается оболочка

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

Условие «≤ 0» в цикле выбрасывает и точки, лежащие ровно на ребре: в ответе только настоящие углы. Если по задаче нужны все точки на границе, ставят «< 0» — но тогда аккуратнее с совпадающими точками.

Код

Обе половины — одной функцией, в Python и Go почти дословно. Площадь — по формуле шнурков: сумма векторных произведений соседних вершин.

А это первая сцена в цифрах: эпицентры Тянь-Шаня и Памира из каталога USGS, переведённые из градусов в километры — на широте сорок градусов градус долготы короче градуса широты почти на четверть, и без поправки забор вышел бы сплющенным.

Сколько это стоит

Сортировка — O(n log n), проход — O(n): каждая точка не больше одного раза кладётся в стек и не больше одного раза вынимается. Итого O(n log n).

Быстрее в общем случае нельзя, и это красиво доказывается: если бы оболочку умели строить быстрее, то и сортировать умели бы быстрее n log n. Положите числа x₁, …, x_n на параболу — точки (x_i, x_i²). Все они окажутся на оболочке, и обход оболочки перечислит их по порядку. А сортировку сравнениями быстрее n log n не сделать.

Зато можно выиграть, когда на оболочке мало точек. Алгоритм «заворачивания подарка» Джарвиса (1973) работает за O(n·h), где h — число вершин оболочки: для эпицентров Тянь-Шаня, где h = 10, это лучше. А алгоритм Чена (1996) — за O(n log h), что лучше и того, и другого. Нажмите в песочнице «Все на окружности»: там h = n, и это худший случай для Джарвиса.

Где пригождается

• Геоданные. Контур облака GPS-точек, зона покрытия станций, область, где наблюдалось явление, — первое, что считают, получив набор координат.
• Столкновения. Физические движки проверяют сначала, пересекаются ли выпуклые оболочки объектов: с выпуклыми фигурами всё считается гораздо проще.
• Самая далёкая пара. Две самые далёкие точки множества всегда лежат на оболочке, и найти их можно вращающимися калиперами за линейное время после построения оболочки. Это вторая задача.
• Статистика. Снимая оболочки слой за слоем, как луковицу, получают «глубину» точки в облаке — устойчивый к выбросам аналог медианы для плоскости.

История

В конце шестидесятых лучшие известные способы строили оболочку за время порядка n². Рональд Грэхем работал тогда в Bell Labs, и, как обычно пересказывают эту историю, там понадобились оболочки наборов из многих тысяч точек, для которых квадратичный алгоритм был слишком медленным. Грэхем отсортировал точки по углу вокруг самой нижней и прошёл по ним со стеком; статья 1972 года первой дала оценку O(n log n). Сам он, по воспоминаниям, считал её проходной работой, а она стала одной из самых цитируемых в его жизни. Эндрю в 1979 году заменил сортировку по углу на сортировку по координате: без углов код проще и не страдает от погрешностей.

Задачи

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