Почему Грэм и QuickHull иногда дают разные списки вершин?

Все **крайние** точки лежат на границе выпуклой оболочки, но при многих точках на **одной прямой** разные алгоритмы по-разному выбирают, какие из них оставить **вершинами** многоугольника. Грэм с тестом **≤ 0** обычно оставляет только **концы** коллинеарного участка; QuickHull без дополнительной фильтрации может включать **промежуточные** точки на ребре. Сама **выпуклая оболочка** как множество на плоскости совпадает; отличается лишь полигональное представление.

Что означает голубая ломаная в режиме Грэма?

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

Насколько это устойчиво численно?

Используются обычные **float64** и векторные произведения. Если точки почти совпадают или лежат почти на одной прямой, ориентация может «дрожать»; при добавлении точек действует небольшой **зазор** от соседей, чтобы не создавать случайные дубликаты.

Как QuickHull делит точки?

После выбора **L** и **R** точки **строго слева** от ориентированной прямой **LR** участвуют в построении **верхней** цепочки, **строго справа** — **нижней**. На каждом шаге из оставшихся выбирается точка **C**, **наиболее удалённая** от текущего ребра **AB** (по модулю ориентированной площади), затем рекурсия продолжается для множеств снаружи треугольников **ABC**, пока с внешней стороны ребра не останется точек.

Выпуклая оболочка (Грэм и QuickHull)

Выпуклая оболочка конечного множества точек на плоскости — это наименьший выпуклый многоугольник, содержащий все точки; эквивалентно — пересечение всех выпуклых надмножеств. Симулятор реализует два классических построения порядка O(n log n). Скан Грэма выбирает опорную точку (самую нижнюю, при равенстве y — самую левую), сортирует остальные по полярному углу относительно опоры (при равенстве угла — по расстоянию) и обходит список, поддерживая стек: перед добавлением очередной точки из стека выталкиваются вершины, пока ориентация последней тройки не станет строго левой при обходе против часовой стрелки (в терминах векторного произведения: удаляются случаи cross ≤ 0, то есть правый поворот или ровная тройка). Кадры фиксируют стек и точку «в рассмотрении» для пошагового показа. QuickHull берёт крайние по x точки L и R, делит множество на точки выше и ниже ориентированной прямой LR и рекурсивно добавляет на каждом ребре точку с наибольшим модулем ориентированной площади треугольника (через |cross|); точки на отрезке отбрасываются как внутренние для ребра. При коллинеарностях разные реализации могут по-разному выбирать подмножество вершин на одной стороне; интерфейс показывает, совпадают ли множества индексов вершин у Грэма и QuickHull. Взаимодействие: клик по пустому месту добавляет точку (с защитой от почти совпадающих), перетаскивание рядом с точкой двигает её; число точек и seed задают случайное облако.

Для кого: Студенты курсов дискретной математики, алгоритмов и вычислительной геометрии; все, кто сравнивает инкрементальное построение с «разделяй и властвуй».

Ключевые понятия

Выпуклая оболочка
Скан Грэма
QuickHull
Полярная сортировка
Монотонный стек
Ориентация тройки (cross)
Разделяй и властвуй
Коллинеарность

Как это работает

Выпуклая оболочка — наименьший выпуклый многоугольник, содержащий все точки. Грэм: опорная точка, полярная сортировка, стек и проверка поворота через cross; QuickHull: крайние по x, рекурсия по самой удалённой от ребра точке (площадь ∝ |cross|). Коллинеарности могут дать разные списки вершин при одной и той же оболочке.

Часто задаваемые вопросы

Почему Грэм и QuickHull иногда дают разные списки вершин?: Все крайние точки лежат на границе выпуклой оболочки, но при многих точках на одной прямой разные алгоритмы по-разному выбирают, какие из них оставить вершинами многоугольника. Грэм с тестом ≤ 0 обычно оставляет только концы коллинеарного участка; QuickHull без дополнительной фильтрации может включать промежуточные точки на ребре. Сама выпуклая оболочка как множество на плоскости совпадает; отличается лишь полигональное представление.
Что означает голубая ломаная в режиме Грэма?: Это текущий стек кандидатов в вершины оболочки на выбранном шаге — частичная оболочка после обработки соответствующего префикса отсортированного списка. Розовое кольцо — точка, которая сейчас рассматривается для включения.
Насколько это устойчиво численно?: Используются обычные float64 и векторные произведения. Если точки почти совпадают или лежат почти на одной прямой, ориентация может «дрожать»; при добавлении точек действует небольшой зазор от соседей, чтобы не создавать случайные дубликаты.
Как QuickHull делит точки?: После выбора L и R точки строго слева от ориентированной прямой LR участвуют в построении верхней цепочки, строго справа — нижней. На каждом шаге из оставшихся выбирается точка C, наиболее удалённая от текущего ребра AB (по модулю ориентированной площади), затем рекурсия продолжается для множеств снаружи треугольников ABC, пока с внешней стороны ребра не останется точек.