Makarov Math Suite: Выпуклая оболочка - резинка вокруг облака точек

Представьте доску с вбитыми гвоздиками. Если охватить их резинкой и отпустить её, резинка натянется вокруг самых крайних гвоздиков. Получившийся контур - выпуклая оболочка: наименьшая выпуклая область, содержащая все точки. Выпуклость означает, что отрезок между любыми двумя точками этой области целиком остаётся внутри неё. Для человека внешний контур часто очевиден. Компьютеру нужен алгоритм. Метод Джарвиса обходит границу, последовательно выбирая следующую вершину. Алгоритм Грэхема упорядочивает точки и отбрасывает повороты, нарушающие выпуклость. QuickHull разбивает задачу на части, выделяя наиболее удалённые точки. Разные пути приводят к одной и той же геометрической оболочке, но требуют разного количества проверок. В модуле точки превращены в штырьки, а граница - в натягивающийся пояс. Добавляйте точки внутри и снаружи контура, переключайте алгоритмы, сравнивайте площадь и число проверок ориентации. Точка внутри может вообще не изменить границу, тогда как одна новая внешняя точка перестроит целую её часть. Эта простая задача помогает понять, как компьютер выделяет форму из набора отдельных координат.