Вычислительная геометрия 📐

Данные в машинном обучении редко бывают «просто числами» — очень часто это буквально точки в пространстве. Эмбеддинги слов после снижения размерности превращаются в облако точек на плоскости, признаки объектов после PCA или t-SNE образуют кластеры со своей формой и границами, а координаты пикселей на изображении — это самая настоящая двумерная геометрия. Когда ты спрашиваешь «какие точки лежат на границе облака данных» или «какая из этих сотен точек — явный выброс, торчащий за пределы основной массы», ты задаёшь геометрический вопрос, и на него есть точный геометрический ответ — выпуклая оболочка набора точек буквально очерчивает его границу.

В компьютерном зрении та же идея работает ещё нагляднее. Когда алгоритм находит контур объекта на изображении — силуэт руки, границу дорожного знака, форму опухоли на медицинском снимке — результатом обычно становится ломаная линия из сотен точек с шумом и мелкими artefacts. Чтобы получить из неё гладкую, устойчивую к шуму огибающую форму, десятилетиями использовался ровно тот инструмент, который ты разберёшь в этом уроке: cv2.convexHull в OpenCV — это не какая-то экзотика, а прямая реализация алгоритма Грэхема, применяемая в промышленных пайплайнах классического компьютерного зрения и по сей день, даже в эпоху нейросетевой сегментации.

Вычислительная геометрия — это ещё и фундамент для куда более широкого класса задач, которые тебе встретятся дальше в области Data Science: обработка облаков точек LiDAR для автономных автомобилей, 3D-реконструкция сцены по набору фотографий, построение мешей для симуляций и рендеринга, поиск ближайших соседей в пространственных индексах. Все эти вещи опираются на один и тот же крошечный набор базовых операций — определить, куда повёрнута тройка точек; понять, пересекаются ли два отрезка; построить оболочку множества точек; посчитать площадь многоугольника. Освоив эти примитивы один раз, ты получаешь ключ сразу к десяткам более сложных алгоритмов: триангуляции Делоне, диаграммам Вороного, k-d деревьям, алгоритмам поиска ближайшей пары точек.

Этот урок закрывает большой блок курса «Алгоритмы и структуры данных» (уроки 251–275), в котором ты прошёл путь от анализа сложности алгоритмов и базовых структур данных через графы, сортировки, динамическое программирование, жадные алгоритмы, backtracking и строковые алгоритмы. Вычислительная геометрия — удачная точка, чтобы завершить этот путь: здесь снова понадобятся и математическая аккуратность (векторное произведение, доказательство корректности), и алгоритмическое мышление (сортировка, стек, анализ сложности), и внимание к граничным случаям, которое ты тренировал весь блок. А сразу за этим уроком курс поворачивает к теории оптимизации — дисциплине, без которой невозможно тренировать ни одну модель машинного обучения.

История

Вычислительная геометрия как отдельная дисциплина внутри теории алгоритмов оформилась на удивление поздно — хотя сама геометрия существует тысячи лет, задача эффективно, с доказанной оценкой сложности, решать геометрические задачи на компьютере возникла только в 1970-е годы вместе с ростом компьютерной графики, систем автоматизированного проектирования (CAD) и первых географических информационных систем. Принято считать датой рождения дисциплины 1975 год, когда Майкл Шеймос (Michael Ian Shamos) защитил докторскую диссертацию под названием «Computational Geometry» — в ней он впервые систематически применил инструментарий анализа алгоритмов (тот самый, что ты изучал весь этот блок курса — big O, доказательства нижних оценок сложности) к классическим геометрическим задачам: построению выпуклой оболочки, поиску ближайшей пары точек, триангуляции. До этого такие задачи решались методами классической, «синтетической» геометрии, без вопроса «а какая у этого алгоритма асимптотическая сложность и можно ли доказать, что быстрее нельзя?».

Алгоритм построения выпуклой оболочки, который ты разберёшь в этом уроке, — один из самых ранних результатов новой дисциплины. Его опубликовал в 1972 году математик Рональд Грэхем (Ronald Graham), и алгоритм Грэхема стал одним из первых геометрических алгоритмов с формально доказанной оценкой сложности $O(n\log n)$, где узким местом оказалась именно сортировка точек — тот же самый инструмент, который ты подробно разбирал в уроках про сортировку слиянием и быструю сортировку. Забавное совпадение: Рональд Грэхем известен и совсем в другой области математики — комбинаторике и теории Рамсея, где его имя носит знаменитое «число Грэма» (Graham's number), одно из крупнейших чисел, когда-либо использовавшихся в серьёзном математическом доказательстве. Это два совершенно разных результата одного и того же учёного, и студенты нередко путают их между собой, хотя ничего общего, кроме фамилии автора, у них нет.

К 1980–90-м годам вычислительная геометрия превратилась в зрелую дисциплину с собственными учебниками, конференциями и десятками алгоритмов для триангуляции, поиска пересечений, построения диаграмм Вороного. А в последние два десятилетия у неё появилось второе дыхание благодаря машинному обучению и робототехнике: обработка облаков точек с LiDAR-сканеров для автономных автомобилей, 3D-реконструкция сцен по фотографиям (structure from motion), построение коллизионных мешей в физических движках игр и симуляциях, планирование пути роботов среди препятствий — все эти современные задачи в основе своей используют ровно те же примитивы, что были формализованы полвека назад: ориентацию точек, пересечение отрезков, выпуклую оболочку.

Базовые примитивы и ориентация трёх точек

Интуиция

Прежде чем решать любую геометрическую задачу на компьютере, нужно договориться, как представлять геометрические объекты в виде данных, с которыми умеет работать код. Точка — это просто пара чисел (x, y), кортеж или маленький класс с двумя полями. Отрезок — это упорядоченная пара точек, его начало и конец. Многоугольник — это список точек-вершин, перечисленных по порядку обхода границы (по часовой стрелке или против неё — направление важно, и ниже станет ясно почему). Ничего сложнее словаря или списка кортежей для этого не нужно — вся сложность вычислительной геометрии не в структурах данных, а в том, какие вопросы про эти структуры мы умеем эффективно отвечать.

Самый частый вопрос, который приходится задавать снова и снова: если стоять в точке $O$ и посмотреть сначала на точку $A$, а потом повернуться в сторону точки $B$ — в какую сторону был этот поворот, влево (против часовой стрелки) или вправо (по часовой стрелке)? Этот, казалось бы, простой вопрос — краеугольный камень вычислительной геометрии: на нём строится и проверка пересечения отрезков, и алгоритм Грэхема, и проверка «точка внутри многоугольника», и десятки других алгоритмов. Отвечает на него одна-единственная формула — двумерное векторное (псевдоскалярное) произведение.

Возьмём два вектора: $\vec{OA} = A - O$ и $\vec{OB} = B - O$. В трёхмерном пространстве их векторное произведение — это вектор, перпендикулярный обоим; но поскольку наши векторы лежат в одной плоскости $XY$, у результата остаётся только одна ненулевая компонента — по оси $Z$. Именно её знак и говорит о направлении поворота:

Если результат положителен — поворот от $\vec{OA}$ к $\vec{OB}$ идёт против часовой стрелки (левый поворот, CCW — counterclockwise). Если отрицателен — по часовой стрелке (правый поворот, CW — clockwise). Если равен нулю — векторы коллинеарны, то есть точки $O$, $A$, $B$ лежат на одной прямой. Ничего сложнее сложения и умножения четырёх чисел для этого не требуется, а информации эта формула даёт на удивление много.

Алгоритм

Определение ориентации трёх точек:

1. Взять точки $O$ (базовая), $A$, $B$ строго в этом порядке.
2. Вычислить псевдоскалярное произведение векторов $\vec{OA}$ и $\vec{OB}$: $\text{cross} = (A_x-O_x)(B_y-O_y) - (A_y-O_y)(B_x-O_x)$.
3. Если $\text{cross} > 0$ — поворот от $\vec{OA}$ к $\vec{OB}$ идёт против часовой стрелки (левый поворот).
4. Если $\text{cross} < 0$ — поворот идёт по часовой стрелке (правый поворот).
5. Если $\text{cross} = 0$ — точки $O$, $A$, $B$ коллинеарны (лежат на одной прямой).

На Python эта проверка укладывается в несколько строк:

def orientation(o, a, b):
    """Знак поворота от вектора OA к вектору OB:
    +1 — против часовой стрелки (CCW),
    -1 — по часовой стрелке (CW),
     0 — точки коллинеарны."""
    cross = (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
    if cross > 0:
        return 1
    elif cross < 0:
        return -1
    return 0

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

Пример 1. Точки $O(0,0)$, $A(4,0)$, $B(2,3)$. Вычисляем: $\text{cross} = (4-0)(3-0) - (0-0)(2-0) = 12 - 0 = 12$. Результат положителен — поворот от $\vec{OA}$ к $\vec{OB}$ идёт против часовой стрелки. Это легко проверить и «на глаз»: вектор $\vec{OA}$ направлен вправо вдоль оси $X$, а точка $B$ находится выше этой оси — значит, поворот действительно влево.

Пример 2. Те же $O(0,0)$, $A(4,0)$, но теперь $B(2,-3)$ — точка ниже оси $X$. Вычисляем: $\text{cross} = (4)(-3) - (0)(2) = -12 - 0 = -12$. Результат отрицателен — поворот по часовой стрелке, ровно как и должно быть для точки, лежащей ниже вектора $\vec{OA}$.

Пример 3. Точки $O(0,0)$, $A(2,2)$, $B(4,4)$ — все три лежат на прямой $y=x$. Вычисляем: $\text{cross} = (2)(4) - (2)(4) = 8 - 8 = 0$. Результат ноль — точки коллинеарны, никакого поворота нет, все три точки выстроены строго на одной прямой.

Обрати внимание: если поменять местами $A$ и $B$ в любом из этих примеров, знак результата сменится на противоположный — поворот от $\vec{OB}$ к $\vec{OA}$ идёт в обратную сторону относительно поворота от $\vec{OA}$ к $\vec{OB}$. Порядок точек в вызове orientation(o, a, b) имеет значение, и путаница в порядке — одна из самых частых причин, по которой геометрический код выдаёт зеркально неверный результат.

Почему это важно

Функция orientation — не побочная мелочь, а рабочая лошадка всего урока: на ней целиком построена проверка пересечения отрезков в следующем разделе, на ней держится каждый шаг алгоритма Грэхема, и она же лежит в основе проверки «находится ли точка внутри выпуклого многоугольника» (для этого достаточно проверить, что точка лежит по одну и ту же сторону от каждого ребра многоугольника, то есть все ориентации имеют одинаковый знак). За пределами игрушечных примеров эта же идея работает в триангуляции Делоне (определение, с какой стороны от ребра находится вершина), в физических движках игр для определения столкновений, и в GIS-системах для определения, попадает ли точка на карте внутрь границ региона.

Проверка пересечения двух отрезков через ориентацию

Интуиция

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

Идея такая: отрезок $p_1q_1$ пересекает отрезок $p_2q_2$ тогда и только тогда, когда выполняются два условия одновременно. Во-первых, точки $p_2$ и $q_2$ должны находиться по разные стороны от прямой, на которой лежит отрезок $p_1q_1$ — иначе говоря, ориентации троек $(p_1, q_1, p_2)$ и $(p_1, q_1, q_2)$ должны иметь разный знак. Во-вторых, симметрично, точки $p_1$ и $q_1$ должны находиться по разные стороны от прямой, содержащей $p_2q_2$. Если оба условия выполнены — отрезки обязательно пересекаются где-то внутри, ведь каждый «протыкает» прямую, содержащую другой.

Отдельно нужно разобрать случай, когда одна из ориентаций равна нулю — то есть три точки коллинеарны. Тогда отрезки могут либо лежать на одной прямой и пересекаться (перекрываться), либо лежать на одной прямой, но не пересекаться (быть разнесены в стороны), либо один отрезок может просто касаться конца другого. Отличить эти случаи помогает дополнительная проверка: лежит ли коллинеарная точка внутри прямоугольника (bounding box), натянутого на концы другого отрезка.

Алгоритм

Проверка пересечения отрезков $p_1q_1$ и $p_2q_2$ через ориентации:

1. Вычислить четыре ориентации: $o_1 = \text{orientation}(p_1, q_1, p_2)$, $o_2 = \text{orientation}(p_1, q_1, q_2)$, $o_3 = \text{orientation}(p_2, q_2, p_1)$, $o_4 = \text{orientation}(p_2, q_2, q_1)$.
2. Общий случай: если $o_1 \neq o_2$ и одновременно $o_3 \neq o_4$ — отрезки пересекаются (концы каждого отрезка лежат по разные стороны от прямой, содержащей другой отрезок).
3. Особые случаи (срабатывают, когда какая-то из ориентаций равна нулю — три точки коллинеарны): дополнительно проверить функцией on_segment, лежит ли коллинеарная точка внутри прямоугольника, натянутого на концы противоположного отрезка.
4. Если ни общий, ни особый случай не подтвердился — отрезки не пересекаются.

def on_segment(p, q, r):
    """Точка q коллинеарна с отрезком pr; проверяем,
    лежит ли она внутри его ограничивающего прямоугольника."""
    return (min(p[0], r[0]) <= q[0] <= max(p[0], r[0]) and
            min(p[1], r[1]) <= q[1] <= max(p[1], r[1]))


def segments_intersect(p1, q1, p2, q2):
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    if o1 != o2 and o3 != o4:
        return True

    if o1 == 0 and on_segment(p1, p2, q1):
        return True
    if o2 == 0 and on_segment(p1, q2, q1):
        return True
    if o3 == 0 and on_segment(p2, p1, q2):
        return True
    if o4 == 0 and on_segment(p2, q1, q2):
        return True

    return False

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

Пример 1 (обычное пересечение). Отрезок 1: $p_1(1,1) \to q_1(4,4)$. Отрезок 2: $p_2(1,4) \to q_2(4,1)$ — это две диагонали квадрата со стороной 3, которые визуально пересекаются в его центре $(2.5, 2.5)$. Считаем: $o_1 = \text{orientation}((1,1),(4,4),(1,4))$: $\text{cross} = (4-1)(4-1) - (4-1)(1-1) = 9 - 0 = 9 > 0$, значит $o_1=1$. $o_2 = \text{orientation}((1,1),(4,4),(4,1))$: $\text{cross} = (3)(1-1) - (3)(4-1) = 0 - 9 = -9 < 0$, значит $o_2=-1$. Уже видно $o_1 \neq o_2$. Проверяем вторую пару: $o_3 = \text{orientation}((1,4),(4,1),(1,1))$: $\text{cross} = (4-1)(1-4) - (1-4)(1-1) = (3)(-3) - (-3)(0) = -9$, значит $o_3=-1$. $o_4 = \text{orientation}((1,4),(4,1),(4,4))$: $\text{cross} = (3)(4-4) - (-3)(4-1) = 0 + 9 = 9$, значит $o_4=1$. И $o_3 \neq o_4$ тоже выполняется. Общее условие сработало — отрезки пересекаются.

Пример 2 (коллинеарные, но непересекающиеся). Отрезок 1: $(0,0) \to (2,0)$. Отрезок 2: $(3,0) \to (5,0)$ — оба лежат на оси $X$, но один занимает интервал $[0,2]$, а другой $[3,5]$, разрыв между ними не перекрывается. Все четыре точки лежат на одной прямой, поэтому все четыре ориентации равны нулю: $o_1=o_2=o_3=o_4=0$. Общее условие $o_1 \neq o_2$ не выполняется — переходим к особым случаям. Проверяем on_segment((0,0), (3,0), (2,0)): попадает ли $x=3$ в диапазон $[\min(0,2), \max(0,2)] = [0,2]$? Нет, $3 > 2$ — условие ложно. Аналогично ложны и остальные три проверки on_segment, потому что интервалы $[0,2]$ и $[3,5]$ действительно не перекрываются. Итог: отрезки не пересекаются — этот пример как раз показывает, зачем нужна дополнительная on_segment-проверка: одних нулевых ориентаций недостаточно, чтобы сделать вывод о пересечении.

Пример 3 (касание в общей вершине). Отрезок 1: $(0,0) \to (2,2)$. Отрезок 2: $(2,2) \to (4,0)$ — оба выходят из общей точки $(2,2)$, как две стороны треугольника. Ориентация $o_1 = \text{orientation}((0,0),(2,2),(2,2))$: точка $p_2=(2,2)$ совпадает с $q_1=(2,2)$, поэтому векторы $\vec{OA}$ и $\vec{OB}$ коллинеарны, $\text{cross}=0$, $o_1=0$. Дальше срабатывает особый случай: on_segment((0,0), (2,2), (2,2)) — попадает ли точка $(2,2)$ в bounding box отрезка от $(0,0)$ до $(2,2)$? Да, это его собственный конец. Условие истинно — отрезки пересекаются ровно в этой общей вершине. Такой edge case легко упустить, если проверять пересечение «на глаз»: формально это вырожденное пересечение в одной точке, а не полноценное скрещивание, но с точки зрения геометрического алгоритма это ровно так же валидное пересечение, и его нужно обрабатывать корректно.

Почему это важно

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

Выпуклая оболочка и алгоритм Грэхема

Интуиция

Представь, что все точки набора — это гвоздики, вбитые в доску, и вокруг них натянута резиновая лента, которая затем отпущена. Лента сожмётся и обтянет только самые «крайние» гвоздики, образовав минимальный выпуклый многоугольник, внутри которого окажутся все остальные точки. Это и есть выпуклая оболочка (convex hull) множества точек — наименьший по площади выпуклый многоугольник, содержащий все точки набора; его вершинами становятся только сами точки исходного набора (никаких новых точек оболочка не добавляет), причём далеко не все точки — большинство точек оказываются «внутри» ленты и на форму оболочки не влияют.

Наивный способ найти оболочку — перебрать все тройки точек и для каждой проверить, лежат ли все остальные точки по одну сторону от прямой через первые две; это работает, но требует порядка $O(n^3)$ операций, что для сколько-нибудь большого набора точек неприемлемо. Алгоритм Грэхема решает ту же задачу за $O(n \log n)$, и вся его хитрость — в правильном порядке обхода точек.

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

Алгоритм

Алгоритм Грэхема (Graham scan):

1. Найти опорную точку $p_0$ — с наименьшей координатой $y$ (а при равенстве $y$ — с наименьшей координатой $x$). Она гарантированно принадлежит выпуклой оболочке, потому что ниже (левее) неё нет ни одной точки.
2. Отсортировать все остальные точки по полярному углу относительно $p_0$ в порядке возрастания; при равенстве угла (несколько точек лежат на одном луче из $p_0$) — отсортировать их по возрастанию расстояния до $p_0$.
3. Завести стек, положить в него $p_0$ и первую точку отсортированного списка.
4. Для каждой следующей точки $p$ из отсортированного списка: пока в стеке ≥ 2 точек и тройка (предпоследняя точка стека, последняя точка стека, $p$) не образует поворот против часовой стрелки (то есть $\text{orientation} \leq 0$) — снять верхнюю точку со стека.
5. Положить $p$ в стек и перейти к следующей точке списка.
6. После обработки всех точек стек содержит вершины выпуклой оболочки в порядке обхода против часовой стрелки.

import math

def convex_hull_graham(points):
    points = list(set(points))
    if len(points) < 3:
        return points

    pivot = min(points, key=lambda p: (p[1], p[0]))

    def polar_key(p):
        dx, dy = p[0] - pivot[0], p[1] - pivot[1]
        return (math.atan2(dy, dx), dx * dx + dy * dy)

    rest = sorted((p for p in points if p != pivot), key=polar_key)

    stack = [pivot]
    for p in rest:
        while len(stack) >= 2 and orientation(stack[-2], stack[-1], p) <= 0:
            stack.pop()
        stack.append(p)

    return stack

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

Пример 1 (квадрат с внутренней точкой, тай-брейк по расстоянию). Точки: $A(0,0)$, $B(2,0)$, $C(2,2)$, $D(0,2)$, и точка $E(1,1)$ строго внутри квадрата. Опорная точка — та, у которой минимальны $y$, а при равенстве $x$: у $A(0,0)$ и $B(2,0)$ одинаковый $y=0$, но у $A$ меньше $x$, значит пивот — $A$.

Сортируем оставшиеся точки по полярному углу относительно $A$: вектор к $B(2,0)$ — угол $0°$; векторы к $E(1,1)$ и $C(2,2)$ оба идут вдоль прямой $y=x$ — угол $45°$ у обоих, но $E$ ближе к $A$ (расстояние $\sqrt2$), а $C$ дальше (расстояние $\sqrt8$), поэтому по правилу тай-брейка $E$ идёт раньше $C$; вектор к $D(0,2)$ — угол $90°$. Итоговый порядок: $B, E, C, D$.

Трассировка стека: [A] → добавляем $B$ (стек < 2 точек, просто кладём) → [A, B]. Далее $E$: проверяем orientation$(A,B,E)$ = $(2-0)(1-0)-(0-0)(1-0) = 2 > 0$ — левый поворот, кладём → [A, B, E]. Далее $C$: проверяем orientation$(B,E,C)$ = $(1-2)(2-0)-(1-0)(2-2) = -2 - 0 = -2 \leq 0$ — не левый поворот, снимаем $E$ → [A, B]. Проверяем снова с новой верхушкой: orientation$(A,B,C)$ = $(2)(2)-(0)(2) = 4 > 0$ — левый поворот, кладём $C$ → [A, B, C]. Далее $D$: orientation$(B,C,D)$ = $(2-2)(2-0)-(2-0)(0-2) = 0+4 = 4 > 0$ — левый поворот, кладём → [A, B, C, D].

Ответ: оболочка — [A(0,0), B(2,0), C(2,2), D(0,2)], то есть ровно квадрат, а внутренняя точка $E$ и «коллинеарный» кандидат правильно отброшены стеком — этот пример наглядно демонстрирует, зачем нужно правило тай-брейка по расстоянию при совпадающих углах.

Пример 2 (восемь точек, полная трассировка с двумя откатами). Возьмём набор из восьми точек: $P_0(0,0)$, $P_1(4,0)$, $P_2(5,2)$, $P_3(4,4)$, $P_4(2,3)$, $P_5(1,4)$, $P_6(0,3)$, $P_7(2,1)$, где $P_4$ и $P_7$ заведомо находятся внутри будущей оболочки. Опорная точка — $P_0(0,0)$ (минимальный $y$, единственная с $y=0$ и минимальным $x$ среди точек с $y=0$).

Считаем полярные углы остальных точек относительно $P_0$: $P_1(4,0)$ — $0°$; $P_2(5,2)$ — $\arctan(2/5) \approx 21.8°$; $P_7(2,1)$ — $\arctan(1/2) \approx 26.6°$; $P_3(4,4)$ — $45°$; $P_4(2,3)$ — $\arctan(3/2) \approx 56.3°$; $P_5(1,4)$ — $\arctan(4/1) \approx 76.0°$; $P_6(0,3)$ — $90°$. Отсортированный порядок: $P_1, P_2, P_7, P_3, P_4, P_5, P_6$.

Трассировка стека, шаг за шагом:

Кладём $P_0$, затем $P_1$: стек [P0, P1]. Кладём $P_2$ (стек короче 2 после пивота не считается, проверка идёт с третьей точки): стек [P0, P1, P2].

Обрабатываем $P_7$: orientation$(P_1, P_2, P_7)$ = $(5-4)(1-0)-(2-0)(2-4) = 1-(-4) = 5 > 0$ — левый поворот, кладём. Стек: [P0, P1, P2, P7].

Обрабатываем $P_3$: orientation$(P_2, P_7, P_3)$ = $(2-5)(4-2)-(1-2)(4-5) = -6-1 = -7 \leq 0$ — не левый, снимаем $P_7$. Стек: [P0, P1, P2]. Проверяем снова: orientation$(P_1, P_2, P_3)$ = $(5-4)(4-0)-(2-0)(4-4) = 4-0=4>0$ — левый, кладём $P_3$. Стек: [P0, P1, P2, P3].

Обрабатываем $P_4$: orientation$(P_2, P_3, P_4)$ = $(4-5)(3-2)-(4-2)(2-5) = -1-(-6) = 5 > 0$ — левый, кладём (пока рано делать выводы — этот кандидат ещё будет проверен на следующем шаге). Стек: [P0, P1, P2, P3, P4].

Обрабатываем $P_5$: orientation$(P_3, P_4, P_5)$ = $(2-4)(4-4)-(3-4)(1-4) = 0-3 = -3 \leq 0$ — не левый, снимаем $P_4$. Стек: [P0, P1, P2, P3]. Проверяем снова: orientation$(P_2, P_3, P_5)$ = $(4-5)(4-2)-(4-2)(1-5) = -2-(-8) = 6 > 0$ — левый, кладём $P_5$. Стек: [P0, P1, P2, P3, P5].

Обрабатываем $P_6$: orientation$(P_3, P_5, P_6)$ = $(1-4)(3-4)-(4-4)(0-4) = 3-0 = 3 > 0$ — левый, кладём. Стек: [P0, P1, P2, P3, P5, P6].

Ответ: финальная оболочка — шестиугольник $P_0(0,0) \to P_1(4,0) \to P_2(5,2) \to P_3(4,4) \to P_5(1,4) \to P_6(0,3)$, а обе внутренние точки $P_4$ и $P_7$ были положены в стек и затем корректно сняты — этот пример показывает главную особенность алгоритма: он не боится временно взять «неправильного» кандидата, потому что следующий шаг всегда может откатить это решение, снимая точки со стека, пока условие поворота против часовой стрелки снова не восстановится.

Пример 3 (вырожденный случай — все точки на одной прямой). Точки $A(0,0)$, $B(1,1)$, $C(2,2)$, $D(3,3)$ лежат на одной прямой $y=x$. Пивот — $A$ (минимальные $y$ и $x$). Все три оставшиеся точки имеют одинаковый полярный угол $45°$, сортируем по расстоянию: $B, C, D$.

Стек: [A] → кладём $B$ → [A, B]. Обрабатываем $C$: orientation$(A,B,C)$ = $(1)(2)-(1)(2) = 0 \leq 0$ — не строго левый (коллинеарны), снимаем $B$. Стек: [A], кладём $C$ → [A, C]. Обрабатываем $D$: orientation$(A,C,D)$ = $(2)(3)-(2)(3)=0 \leq 0$ — снова коллинеарны, снимаем $C$. Стек: [A], кладём $D$ → [A, D].

Ответ: «оболочка» вырождается в отрезок из двух крайних точек [A(0,0), D(3,3)] — когда все входные точки лежат на одной прямой, полноценного многоугольника не существует, и алгоритм корректно возвращает вырожденный случай: две самые удалённые друг от друга точки, а все промежуточные коллинеарные точки последовательно снимаются со стека условием $\text{orientation} \leq 0$.

Почему это важно

Выпуклая оболочка — один из самых прямых мостов между вычислительной геометрией и практическим анализом данных. В задачах обнаружения выбросов (outlier detection) в многомерных данных вершины выпуклой оболочки — это буквально самые «крайние», нетипичные точки набора; приём под названием convex hull peeling («снятие слоёв оболочки») строит оболочку, временно убирает её вершины, строит оболочку заново на оставшихся точках и повторяет процесс — получившиеся «слои» задают понятие глубины точки относительно облака данных (data depth), которое используется в робастной статистике как более устойчивая к выбросам альтернатива обычным перцентилям. В компьютерном зрении cv2.convexHull строит сглаженную огибающую контура объекта на изображении — от неё считают convexity defects (углубления в форме, полезные, например, для распознавания жестов руки по пальцам) и solidity — отношение площади контура к площади его выпуклой оболочки, классическую метрику «заполненности» формы. А для облаков точек LiDAR и задач 3D-реконструкции выпуклая оболочка (её трёхмерный аналог, алгоритм QuickHull) даёт грубую, но очень дешёвую по вычислениям оценку формы и объёма объекта — первый шаг, к которому потом добавляются более точные методы, учитывающие вогнутости поверхности.

Площадь многоугольника: формула шнурков

Интуиция

Если многоугольник — это просто список координат вершин, как посчитать его площадь, не разбивая фигуру вручную на треугольники и трапеции? Оказывается, для этого существует одна компактная формула, которая работает для любого простого (без самопересечений) многоугольника, выпуклого или нет, — формула шнурков (shoelace formula). Название она получила за характерный визуальный узор: если выписать координаты $x$ и $y$ всех вершин в два столбца одну под другой и соединить их крест-накрест линиями, получившийся рисунок напоминает шнуровку ботинка.

Идея формулы очень похожа на то, что ты уже видел в курсе математического анализа при разборе формулы Грина: интеграл по границе области связан с площадью самой области. Формула шнурков — это, по сути, дискретный частный случай той же идеи: вместо интегрирования по гладкой кривой мы суммируем вклад каждой пары соседних вершин многоугольника. Каждое слагаемое $x_i y_{i+1} - x_{i+1} y_i$ — это удвоенная «подписанная» площадь треугольника, образованного началом координат и отрезком $(P_i, P_{i+1})$; суммируя такие вклады по всем рёбрам многоугольника и обходя его по кругу, площади треугольников вне многоугольника взаимно сокращаются, а остаётся ровно удвоенная площадь самой фигуры.

Алгоритм

Формула шнурков для площади многоугольника:

1. Перечислить вершины многоугольника по порядку обхода границы (по часовой или против часовой стрелки) — $P_1, P_2, \dots, P_n$.
2. Для каждой пары соседних вершин (последней и первой — тоже, обход замыкается по кругу) вычислить произведение $x_i y_{i+1} - x_{i+1} y_i$.
3. Просуммировать все такие произведения по всем $n$ рёбрам.
4. Площадь равна половине модуля этой суммы: $S = \frac{1}{2}\left|\sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i)\right|$. Знак суммы без модуля несёт дополнительную информацию — он положителен, если вершины перечислены против часовой стрелки, и отрицателен, если по часовой.

def polygon_signed_area(points):
    """Возвращает площадь со знаком: положительна для обхода
    против часовой стрелки, отрицательна — по часовой."""
    n = len(points)
    total = 0
    for i in range(n):
        x1, y1 = points[i]
        x2, y2 = points[(i + 1) % n]
        total += x1 * y2 - x2 * y1
    return total / 2

def polygon_area(points):
    return abs(polygon_signed_area(points))

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

Пример 1 (прямоугольник, проверка формулы на известном ответе). Вершины в порядке обхода против часовой стрелки: $(0,0), (4,0), (4,3), (0,3)$. Считаем слагаемые: $(0\cdot0-4\cdot0)=0$; $(4\cdot3-4\cdot0)=12$; $(4\cdot3-0\cdot3)=12$; $(0\cdot0-0\cdot3)=0$. Сумма $= 0+12+12+0=24$, площадь $=24/2=12$. Это совпадает с очевидным результатом «ширина × высота» $=4 \times 3 = 12$ — формула шнурков даёт тот же ответ, что и школьная формула площади прямоугольника, что служит хорошей проверкой правильности реализации.

Пример 2 (площадь шестиугольника из предыдущего раздела — callback к трассировке Грэхема). Возьмём ту же оболочку, что была найдена во втором примере предыдущего раздела: $P_0(0,0), P_1(4,0), P_2(5,2), P_3(4,4), P_5(1,4), P_6(0,3)$, обход против часовой стрелки. Считаем шесть слагаемых: $x_0y_1-x_1y_0 = 0\cdot0-4\cdot0=0$; $x_1y_2-x_2y_1 = 4\cdot2-5\cdot0=8$; $x_2y_3-x_3y_2 = 5\cdot4-4\cdot2=12$; $x_3y_5-x_5y_3 = 4\cdot4-1\cdot4=12$; $x_5y_6-x_6y_5 = 1\cdot3-0\cdot4=3$; $x_6y_0-x_0y_6 = 0\cdot0-0\cdot3=0$. Сумма $=0+8+12+12+3+0=35$, площадь $=35/2=17.5$. Это ровно та же оболочка, которую алгоритм Грэхема построил чуть раньше в этом уроке — так формула шнурков превращает список вершин выпуклой оболочки в одно конкретное число, характеризующее размер облака данных или объекта на изображении.

Пример 3 (тот же шестиугольник, но обход по часовой стрелке — проверка знака). Возьмём те же шесть точек в обратном порядке: $P_0(0,0), P_6(0,3), P_5(1,4), P_3(4,4), P_2(5,2), P_1(4,0)$. Считаем сумму: $x_0y_6-x_6y_0=0\cdot3-0\cdot0=0$; $x_6y_5-x_5y_6=0\cdot4-1\cdot3=-3$; $x_5y_3-x_3y_5=1\cdot4-4\cdot4=-12$; $x_3y_2-x_2y_3=4\cdot2-5\cdot4=-12$; $x_2y_1-x_1y_2=5\cdot0-4\cdot2=-8$; $x_1y_0-x_0y_1=4\cdot0-0\cdot0=0$. Сумма $=0-3-12-12-8+0=-35$, а после модуля площадь всё та же $17.5$. Знак суммы без модуля стал отрицательным — ровно потому, что направление обхода поменялось на противоположное (по часовой стрелке). Эта чувствительность к знаку — не баг, а полезное свойство: по одному числу можно сразу определить, в какую сторону перечислены вершины многоугольника, не глядя на координаты глазами.

Почему это важно

Формула шнурков — это дешёвый (линейный по числу вершин) и надёжный способ превратить контур в число, и это число регулярно становится признаком в практических пайплайнах: площадь контура объекта на изображении, площадь земельного участка в геоданных, площадь bounding-полигона облака LiDAR-точек. В связке с площадью ограничивающего прямоугольника (bounding box) она даёт метрику «заполненности» формы (solidity, extent) — классический признак в задачах классической компьютерной зрения до эпохи нейросетей, который до сих пор используется как быстрый sanity-check и вспомогательный признак в гибридных пайплайнах. А знак результата без модуля — простой и надёжный способ проверить ориентацию произвольного многоугольника, что регулярно нужно перед тем, как передать полигон в другой алгоритм, ожидающий определённое направление обхода (например, тот же алгоритм Грэхема формирует оболочку именно против часовой стрелки).

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Вычислить $\text{orientation}(O, A, B)$ для $O(0,0)$, $A(3,0)$, $B(1,2)$ и определить направление поворота.

Задание 2: Определить, коллинеарны ли точки $(1,1)$, $(2,2)$, $(3,3)$.

Задание 3: Реализовать функцию orientation(o, a, b), возвращающую $-1$, $0$ или $1$.

def orientation(o, a, b):
    cross = (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
    if cross > 0:
        return 1
    elif cross < 0:
        return -1
    return 0

Задание 4: Для отрезка от $(0,0)$ до $(4,4)$ определить, лежит ли точка $(2,2)$ на этом отрезке.

Задание 5: Найти самую нижнюю (а при равенстве $y$ — самую левую) точку в наборе $\{(3,4), (1,1), (1,0), (5,2)\}$.

Задание 6: Определить знак площади треугольника $(0,0)$, $(2,0)$, $(0,2)$ по формуле cross-произведения (без деления на 2).

Задание 7: Отсортировать по полярному углу относительно точки $(0,0)$ набор точек $\{(1,0), (0,1), (-1,0), (1,1)\}$.

Задание 8: Посчитать площадь треугольника $(0,0)$, $(4,0)$, $(0,3)$ по формуле шнурков и сверить с $\frac12 \cdot \text{основание} \cdot \text{высоту}$.

Задание 9: Привести два примера реальных задач, где определение ориентации трёх точек используется как базовая операция более сложного алгоритма.

Задание 10: Для многоугольника, заданного вершинами по часовой стрелке, что покажет знак суммы в формуле шнурков без взятия модуля?

Средние задания (11–20)

Задание 11: Проверить, пересекаются ли отрезки $(1,1)$–$(4,4)$ и $(1,4)$–$(4,1)$ через тест ориентаций.

Задание 12: Проверить пересечение коллинеарных отрезков $(0,0)$–$(2,0)$ и $(3,0)$–$(5,0)$.

Задание 13: Проверить пересечение отрезков $(0,0)$–$(2,2)$ и $(2,2)$–$(4,0)$, касающихся в общей вершине.

Задание 14: Для набора точек $A(0,0), B(2,0), C(2,2), D(0,2), E(1,1)$ найти опорную точку и отсортировать остальные по полярному углу (первые три шага алгоритма Грэхема).

Задание 15: Трассировать полный алгоритм Грэхема для набора из задания 14.

Задание 16: Посчитать площадь выпуклого пятиугольника с вершинами $(0,0), (4,0), (5,3), (2,5), (-1,2)$ (обход против часовой стрелки) по формуле шнурков.

Задание 17: Объяснить, почему сортировка точек по полярному углу критична для корректности алгоритма Грэхема.

Задание 18: Дан многоугольник, заданный по часовой стрелке: $(0,0), (0,2), (2,2), (2,0)$. Посчитать площадь по шнуркам и объяснить знак результата.

Задание 19: Дано облако из точек-эмбеддингов после понижения размерности: большинство сгруппировано около $(0,0)$–$(1,1)$, но точка $(9,9)$ явно оторвана от остальных. Как выпуклая оболочка помогает выявить такую точку как кандидата в выбросы?

Задание 20: Оценить сложность алгоритма Грэхема ($O(n\log n)$ на сортировку + $O(n)$ на проход стеком) и сравнить с наивным перебором троек точек $O(n^3)$ для $n=10\,000$.

Продвинутые задания (21–30)

Задание 21: Реализовать полную функцию convex_hull_graham(points) и протестировать её на наборе из задания 14.

import math

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

def convex_hull_graham(points):
    points = list(set(points))
    if len(points) < 3:
        return points
    pivot = min(points, key=lambda p: (p[1], p[0]))
    def key(p):
        dx, dy = p[0]-pivot[0], p[1]-pivot[1]
        return (math.atan2(dy, dx), dx*dx + dy*dy)
    rest = sorted((p for p in points if p != pivot), key=key)
    stack = [pivot]
    for p in rest:
        while len(stack) >= 2 and orientation(stack[-2], stack[-1], p) <= 0:
            stack.pop()
        stack.append(p)
    return stack

convex_hull_graham([(0,0),(2,0),(2,2),(0,2),(1,1)])

Задание 22: Что должен вернуть алгоритм Грэхема, если все входные точки коллинеарны?

Задание 23: Объяснить, зачем при равном полярном угле у нескольких точек нужно сортировать их по возрастанию расстояния от опорной точки, а не по убыванию.

Задание 24: В чём ограничение формулы шнурков для самопересекающегося (непростого) многоугольника?

Задание 25: Смоделировать «convex hull peeling» (снятие слоёв) для набора точек: построить оболочку, убрать её вершины, построить оболочку заново на оставшихся точках. Для чего используется такая процедура?

Задание 26: Сравнить алгоритм Грэхема $O(n\log n)$ с алгоритмом Джарвиса (jarvis march / gift wrapping) $O(nh)$, где $h$ — число вершин итоговой оболочки. Когда какой выгоднее?

Задание 27: Описать псевдокод пайплайна классического компьютерного зрения, использующего выпуклую оболочку для определения контура объекта.

1. Захватить изображение и перевести в оттенки серого.
2. Выделить объект бинаризацией/пороговой обработкой (thresholding).
3. Найти контуры бинарной маски (cv2.findContours) — списки точек границы.
4. Для каждого контура построить выпуклую оболочку (cv2.convexHull) —
   алгоритм Грэхема, применённый к точкам контура.
5. Посчитать площадь контура и площадь его оболочки (формула шнурков),
   вычислить solidity = площадь_контура / площадь_оболочки.
6. Использовать оболочку и solidity как признаки для дальнейшей
   классификации формы объекта.

Задание 28: Почему выпуклая оболочка в 3D (алгоритм QuickHull) важна для грубой оценки формы облака точек LiDAR, и в чём её принципиальное ограничение?

Задание 29: Реализовать проверку «точка $P$ внутри выпуклого многоугольника» через сумму ориентаций относительно всех его рёбер.

def point_in_convex_polygon(polygon, p):
    n = len(polygon)
    signs = set()
    for i in range(n):
        a, b = polygon[i], polygon[(i + 1) % n]
        o = orientation(a, b, p)
        if o != 0:
            signs.add(o)
    return len(signs) <= 1

Задание 30: Даны координаты контура объекта на изображении (список точек границы) и его bounding box. Посчитать площадь контура через шнурки, площадь bounding box и оценить solidity — заполненность формы.

Частые ошибки

Ошибка 1. Путают знак ориентации из-за разных соглашений о направлении оси $Y$.

Как выглядит: код, написанный и протестированный в математических координатах (ось $Y$ вверх), даёт «перевёрнутый» результат при работе с координатами пикселей изображения, где ось $Y$ традиционно направлена вниз.

Почему возникает: формула orientation не знает, в какой системе координат её используют — знак поворота относителен к выбранному направлению осей, и переход от математических координат к экранным/пиксельным меняет интерпретацию знака на противоположную.

Как правильно: явно фиксировать, в какой системе координат работает код (и по возможности приводить входные данные к одному соглашению перед вызовом геометрических функций), либо документировать, что «CCW» в этом конкретном модуле означает «CCW в экранных координатах», а не в привычных математических.

Ошибка 2. Забывают отдельно обработать коллинеарные точки при проверке пересечения отрезков.

Как выглядит: код проверяет только общее условие $o_1 \neq o_2$ и $o_3 \neq o_4$, без ветки для случая, когда какая-то из ориентаций равна нулю, и пропускает реальные пересечения на общей прямой.

Почему возникает: общее условие кажется исчерпывающим, потому что покрывает подавляющее большинство «обычных» случаев пересечения, а вырожденные коллинеарные случаи легко упустить, если не тестировать код на специально подобранных edge case.

Как правильно: всегда добавлять проверку on_segment для случаев, когда одна из четырёх ориентаций равна нулю, как показано в примере 2 и 3 раздела про пересечение отрезков.

Ошибка 3. Выбирают опорную точку для алгоритма Грэхема без учёта тай-брейка по $x$.

Как выглядит: функция поиска опорной точки использует только min(points, key=lambda p: p[1]), и при наличии нескольких точек с одинаковым минимальным $y$ результат оказывается непредсказуемым (зависит от порядка точек во входном списке).

Почему возникает: про необходимость тай-брейка легко забыть, если тестировать код только на наборах, где минимальный $y$ достигается ровно в одной точке.

Как правильно: всегда использовать составной ключ сортировки key=lambda p: (p[1], p[0]), гарантирующий детерминированный выбор опорной точки даже при совпадении $y$-координат.

Ошибка 4. Забывают правило тай-брейка по расстоянию при равных полярных углах.

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

Почему возникает: на случайных «размытых» тестовых наборах точки редко оказываются строго коллинеарными, и ошибка долго не проявляется, пока не встретятся реальные данные с такой структурой (например, точки на прямых границах прямоугольных объектов).

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

Ошибка 5. Используют нестрогое условие поворота там, где нужно строгое (или наоборот) при снятии точек со стека в алгоритме Грэхема.

Как выглядит: условие снятия со стека записано как orientation(...) < 0 вместо orientation(...) <= 0 (или наоборот), из-за чего коллинеарные точки на границе оболочки то остаются в результате, то теряются непредсказуемым образом.

Почему возникает: разница между < и <= кажется малозначительной деталью и легко упускается при переносе псевдокода в реальный код.

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

Ошибка 6. Забывают взять модуль в формуле шнурков и получают отрицательную площадь.

Как выглядит: функция возвращает отрицательное число для многоугольника, вершины которого перечислены по часовой стрелке, и это значение по ошибке используется дальше как есть, без проверки на отрицательность.

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

Как правильно: явно разделять две функции — одну, возвращающую подписанную площадь (полезна для определения направления обхода), и другую, берущую модуль результата для получения физической площади.

Ошибка 7. Применяют формулу шнурков к самопересекающемуся контуру и ожидают корректный результат.

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

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

Как правильно: перед вычислением площади проверять контур на отсутствие самопересечений (используя проверку пересечения отрезков для каждой пары непоследовательных рёбер) либо предварительно очищать контур от самопересечений специализированными методами.

Главное запомнить

• Точка — пара координат, отрезок — упорядоченная пара точек, многоугольник — список вершин в порядке обхода границы; вся сложность вычислительной геометрии не в структурах данных, а в вопросах, которые мы умеем эффективно задавать про эти структуры.

• Ориентация трёх точек $\text{orientation}(O,A,B)$ через знак псевдоскалярного произведения $(A_x-O_x)(B_y-O_y)-(A_y-O_y)(B_x-O_x)$ — базовый примитив: положительный знак значит поворот против часовой стрелки, отрицательный — по часовой, ноль — коллинеарность.

• Пересечение двух отрезков проверяется через четыре ориентации: общий случай — когда концы каждого отрезка лежат по разные стороны от прямой, содержащей другой; особый случай — коллинеарные точки требуют дополнительной проверки попадания в bounding box (on_segment).

• Выпуклая оболочка — минимальный выпуклый многоугольник, содержащий все точки набора; алгоритм Грэхема строит её за $O(n\log n)$: находит опорную точку, сортирует остальные по полярному углу (с тай-брейком по расстоянию), затем проходит их стеком, снимая точки при не-левом повороте.

• Тай-брейк по расстоянию при равных полярных углах и тай-брейк по $x$ при равном минимальном $y$ у опорной точки — детали, без которых алгоритм Грэхема даёт неверный результат на данных с коллинеарными точками.

• Формула шнурков $S=\frac12\left|\sum(x_iy_{i+1}-x_{i+1}y_i)\right|$ вычисляет площадь простого многоугольника за линейное время по списку его вершин; знак суммы без модуля показывает направление обхода — положительный для CCW, отрицательный для CW.

• Выпуклая оболочка напрямую используется для обнаружения выбросов в многомерных данных через convex hull peeling (снятие слоёв), задающее понятие глубины точки относительно облака данных.

• В компьютерном зрении cv2.convexHull строит сглаженную огибающую контура объекта, а отношение площади контура к площади его оболочки (solidity) — классический признак формы в задачах классического и гибридного компьютерного зрения.

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

Связь с темами курса

Что нужно было знать до этого урока

Этот урок опирается на весь пройденный блок алгоритмов сразу с нескольких сторон: понимание нотации $O(\cdot)$ из начала блока понадобилось, чтобы оценить выигрыш алгоритма Грэхема $O(n\log n)$ над наивным перебором $O(n^3)$; сортировка (уроки про сортировку слиянием и быструю сортировку) буквально стала одним из двух этапов алгоритма Грэхема; а работа со стеком, знакомая по проверке скобочных последовательностей и другим задачам блока, — вторым его этапом. Идея «разделяй и властвуй» и аккуратная работа с граничными случаями, которую ты тренировал в backtracking и строковых алгоритмах, здесь понадобились для обработки вырожденных геометрических случаев — коллинеарных точек, общих вершин отрезков, самопересекающихся контуров.

Что изучить дальше

Этим уроком заканчивается большой блок курса «Алгоритмы и структуры данных» (уроки 251–275) — от базового анализа сложности алгоритмов и классических структур данных, через графы и алгоритмы на них, сортировки, парадигмы динамического программирования, жадных алгоритмов, разделяй-и-властвуй и backtracking, строковые алгоритмы и, наконец, вычислительную геометрию. Это целый законченный набор инструментов для того, чтобы писать эффективный, доказуемо корректный код на самых разных типах данных — числах, графах, строках, координатах. Следующий урок 276 открывает новый большой блок курса — теорию оптимизации, дисциплину, без которой невозможно тренировать ни одну модель машинного обучения: именно оптимизационные алгоритмы (градиентный спуск и его многочисленные модификации) находят те самые параметры моделей, которые минимизируют функцию потерь на обучающих данных. Алгоритмическое мышление, которое ты нарабатывал весь этот блок — анализ сложности, доказательство корректности, аккуратная работа с граничными случаями, — станет фундаментом и для понимания того, как и почему сходятся (или не сходятся) методы оптимизации.

Где это нужно в жизни

🤖 ML/AI и обнаружение выбросов. Выпуклая оболочка и её послойное «снятие» (convex hull peeling) — рабочий инструмент робастной статистики и анализа многомерных данных: точки, попадающие в первые слои оболочки, — естественные кандидаты в выбросы, а глубина точки относительно облака данных используется как более устойчивая к экстремальным значениям альтернатива стандартным перцентилям.

📷 Компьютерное зрение. cv2.convexHull и связанные с ним признаки (площадь контура через шнурки, solidity, convexity defects) — десятилетиями проверенный инструментарий классического компьютерного зрения, который до сих пор применяется как вспомогательный и легко интерпретируемый слой в гибридных пайплайнах поверх нейросетевой сегментации.

🚗 LiDAR и 3D-реконструкция. Трёхмерная выпуклая оболочка (алгоритм QuickHull) даёт быструю грубую оценку формы и объёма объектов в облаках точек — первый, самый дешёвый шаг обработки данных с LiDAR-сканеров в автономных транспортных средствах и робототехнике, до применения более точных, но затратных методов реконструкции поверхности.

🗺️ Геоинформационные системы. Проверка пересечения отрезков и формула шнурков лежат в основе операций над географическими полигонами — определения пересечения границ участков, расчёта площади регионов на карте, построения буферных зон вокруг объектов.

Интересные факты

• Вычислительная геометрия как формальная дисциплина внутри теории алгоритмов родилась в 1975 году благодаря докторской диссертации Майкла Шеймоса «Computational Geometry», где он впервые систематически применил анализ асимптотической сложности к классическим геометрическим задачам.

• Алгоритм Грэхема опубликован в 1972 году математиком Рональдом Грэхемом — тем самым, чьим именем названо «число Грэма» (Graham's number) из совершенно другой области математики, комбинаторики и теории Рамсея; это два независимых результата одного автора, которые часто путают из-за совпадения фамилии.

• Формула шнурков была известна ещё во времена Гаусса (иногда её называют формулой Гаусса для площади) — название «shoelace» (шнурок) она получила гораздо позже, из-за визуального сходства схемы перемножения координат крест-накрест с узором шнуровки ботинка.

• cv2.convexHull в библиотеке OpenCV — одна из самых часто используемых функций классического компьютерного зрения, применяемая для анализа формы объектов на изображениях за десятилетия до появления современных нейросетевых методов сегментации, и остающаяся в строю до сих пор как быстрый и интерпретируемый инструмент.

• Задача построения выпуклой оболочки — один из самых фундаментальных примитивов вычислительной геометрии: на ней прямо или косвенно строятся триангуляция Делоне, диаграммы Вороного и алгоритмы поиска ближайшей пары точек, то есть значительная часть всей дисциплины вырастает из одной этой задачи.

Лайфхаки

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

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

• Для отладки геометрического кода визуализируй точки, отрезки и построенную оболочку через matplotlib — ошибки в сортировке по полярному углу или в условии снятия точек со стека почти всегда мгновенно заметны на графике, но с трудом ловятся по одним числам.

• Не переписывай вычислительную геометрию с нуля в продакшен-коде — используй проверенные библиотеки (scipy.spatial.ConvexHull, shapely, OpenCV), устойчивые к числовым ошибкам плавающей точки и накопившие десятилетия исправленных edge case.

• При работе с координатами в формате чисел с плавающей точкой сравнивай результат cross-произведения не со строгим нулём, а с небольшим порогом-эпсилон — иначе ошибки округления могут ложно превратить почти-коллинеарные точки в «коллинеарные» или наоборот.

• Для задач обнаружения выбросов не ограничивайся одним первым слоем выпуклой оболочки — рассмотри послойное снятие оболочки (convex hull peeling), оно даёт куда более информативную картину структуры данных, чем единственная внешняя граница.

• Перед вычислением площади многоугольника формулой шнурков на реальных, потенциально зашумлённых контурах — сначала проверь отсутствие самопересечений, иначе результат перестанет соответствовать интуитивно понимаемой площади фигуры.

На этом уроке закрывается большой блок курса, посвящённый алгоритмам и структурам данных, — двадцать пять уроков пути от анализа сложности и базовых структур до графов, сортировок, динамического программирования, backtracking, строковых алгоритмов и, наконец, геометрии. Ты прошёл путь от «как посчитать, сколько операций сделает код» до «как за $O(n\log n)$ построить выпуклую оболочку сотен точек» — и на каждом шаге училось одно и то же алгоритмическое мышление: разбить задачу на понятные примитивы, доказать их корректность на конкретных примерах, а затем собрать из них решение сложной задачи. Эти навыки никуда не денутся — они станут фундаментом для следующего большого поворота курса, к теории оптимизации, где ты увидишь, как те же принципы строгого анализа применяются уже не к дискретным структурам, а к непрерывным функциям, которые обучаются минимизировать модели машинного обучения. Поздравляю с завершением блока — впереди новый, не менее интересный виток курса.