Сканирование Грэма
-
Описание метода сканирования Грэма
- Метод находит выпуклую оболочку множества точек на плоскости за время O(n log n)
- Назван в честь Рональда Грэхема, опубликован в 1972 году
- Алгоритм упорядочивает вершины выпуклой оболочки вдоль границы
-
Алгоритм сканирования Грэма
- Поиск точки с наименьшей координатой y, если есть несколько, выбирается точка с наименьшей координатой x
- Сортировка точек по углу, образованному с осью x, используя общий алгоритм сортировки, например, heapsort
- Определение «левого поворота» и «правого поворота» для точек, расположенных на одной прямой
- Определение выпуклости оболочки на основе перекрестного произведения векторов
-
Временная сложность и псевдокод
- Сортировка точек имеет сложность O(n log n), цикл с проверкой «правого поворота» имеет сложность O(n)
- Псевдокод использует функцию ccw для определения направления вращения точек
-
Модификации и численная надежность
- Модификация сканирования Грэма для сортировки по координате x
- Алгоритмы выпуклой оболочки хорошо продуманы и могут выдавать ответ с разумной погрешностью
- Graham-Fortune модификация решает проблемы конечной точности данных