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