Кратко о задаче: минимальный по площади выпуклый многоугольник, содержащий все точки множества, — это их выпуклая оболочка (convex hull). Далее — алгоритмы, их сложность и устойчивость к шуму.
Определяющие операции:
- Ориентация тройки точек $A(x_a,y_a),B(x_b,y_b),C(x_c,y_c)$: знак векторного произведения
$$\text{orient}(A,B,C)=(x_b-x_a)(y_c-y_a)-(y_b-y_a)(x_c-x_a).$$ - Площадь выпуклого многоугольника с вершинами по порядку (формула Гаусса / shoelace):
Area=12∣∑i=1h(xiyi+1−xi+1yi)∣, \text{Area}=\tfrac12\left|\sum_{i=1}^{h}(x_i y_{i+1}-x_{i+1} y_i)\right|,
Area=21 i=1∑h (xi yi+1 −xi+1 yi ) , где $h$ — число вершин, $x_{h+1}=x_1$, $y_{h+1}=y_1$.
1) Graham scan
- Идея: выбрать опорную точку (обычно с минимальной $y$), отсортировать все точки по полярному углу относительно опоры, затем проходом по отсортированным точкам строить оболочку стеком, удаляя вогнутые вершины.
- Сложность: сортировка даёт суммарно $O(n\log n)$.
- Память: $O(n)$.
- Устойчивость к шуму / выбросам: чувствителен — одиночные выбросы становятся вершинами оболочки и сильно влияют на результат; число вершин $h$ может быть большим, но время всё равно $O(n\log n)$. Численно чувствителен к точным вычислениям ориентации (коллинеарность, близкие к нулю значения) — рекомендуется использовать строгие предикаты или целочисленную/точную арифметику либо вводить эпсилон для сравнений.
- Обработка коллинеарных точек: нужно явно задать правило (включать концевые точки или все).
2) Jarvis march (gift wrapping)
- Идея: стартуя от крайней точки, последовательно «оборачиваем» множество, на каждой итерации выбирая следующую вершину как ту, для которой все остальные точки лежат по одной стороне от текущего ребра.
- Сложность: выходо-чувствительная $O(nh)$, где $h$ — число вершин оболочки; в худшем случае $O(n^2)$ (когда $h=\Theta (n)$), но выгодна если $h\ll n$.
- Память: $O(n)$ (или $O(1)$ дополнительно).
- Устойчивость к шуму: очень чувствителен к выбросам, так как выбросы увеличивают $h$ и ухудшают время до $O(n^2)$. Та же числовая уязвимость ориентационных тестов.
3) Другие подходы (кратко)
- Quickhull: обычно быстро на практике, среднее время $O(n\log n)$, в худшем $O(n^2)$.
- Разделяй-и-властвуй: гарантированное $O(n\log n)$.
- Chan’s algorithm: оптимален по сложности выходо-чувствительный алгоритм $O(n\log h)$.
- Для больших данных/потоковых: приближённые и онлайн-методы, Grid-simplification, streaming convex hull.
4) Устойчивость к шуму и практические приёмы
- Сам факт: выпуклая оболочка крайне чувствительна к выбросам — даже один удалённый шумовой объект полностью меняет форму и площадь.
- Меры:
- Предварительная фильтрация выбросов (статистические методы, RANSAC, локальные плотностные методы).
- Удаление крайних точек по радиусу/квантили (trimmed hull): вычислить центроид/медиану и исключить $k$ самых удалённых точек.
- Аппроксимации: вычислить приближённую оболочку на выборке точек или на сетке (decimation), либо использовать α‑shape для получения более «локального» контура.
- Использовать точную арифметику или библиотечные устойчивые предикаты (Shewchuk) для надежности геометрических тестов.
- Выбирать алгоритм по характеру данных: если $h$ мало — Jarvis; если требуется гарантированное $O(n\log n)$ — Graham или divide-and-conquer; если нужен выходо-чувствительный оптимум — Chan.
Резюме:
- Задача = выпуклая оболочка. Площадь можно получить за $O(h)$ после построения.
- Graham: $O(n\log n)$, прост и эффективен, чувствителен к шуму и числовым ошибкам.
- Jarvis: $O(nh)$, выгоден при маленьком $h$, в худшем $O(n^2)$, также чувствителен к выбросам.
- Для практики: учитывать распределение точек, применять предобработку выбросов и использовать устойчивые арифметические предикаты.