Алгоритмы и структуры данных

Выпуклая оболочка с использованием алгоритма Грэхема

Метод поиска выпуклой оболочки набора точек в двумерном пространстве. Выпуклая оболочка — это наименьший выпуклый многоугольник, охватывающий все заданные точки.

Алгоритм:
1. Найдите самую нижнюю точку P0, сравнивая Y всех точек. В случае равенства по Y выберите тот, у которого X меньше.
2. Отсортируйте оставшиеся n-1 точек по углам вокруг P0 против часовой стрелки. Если углы одинаковы, сначала отдайте приоритет ближайшей точке.
3. Удалите точки с одинаковым углом, оставив только самую дальнюю от P0. Пусть размер нового массива будет m.
4. Если m меньше 3, верните «Выпуклая оболочка невозможна».
5. Создайте пустой стек «S» и поместите первые три точки в «S».
6. Обрабатываем оставшиеся m-3 точки одну за другой. Для каждой точки:
⁃ Пока ориентация двух верхних точек в стеке и «points[i]» не против часовой стрелки, извлекайте точки из стека
⁃ Положите «points[i]» в «S».
7. Стек «S» теперь содержит точки выпуклой оболочки.

Сложность: O(nLogn)

www.tgoop.com/the_algorithms/4677

5.2K viewsJan 22, 2024 at 09:00

Выпуклая оболочка с использованием алгоритма Грэхема

Метод поиска выпуклой оболочки набора точек в двумерном пространстве. Выпуклая оболочка — это наименьший выпуклый многоугольник, охватывающий все заданные точки.

Алгоритм:
1. Найдите самую нижнюю точку P0, сравнивая Y всех точек. В случае равенства по Y выберите тот, у которого X меньше.
2. Отсортируйте оставшиеся n-1 точек по углам вокруг P0 против часовой стрелки. Если углы одинаковы, сначала отдайте приоритет ближайшей точке.
3. Удалите точки с одинаковым углом, оставив только самую дальнюю от P0. Пусть размер нового массива будет m.
4. Если m меньше 3, верните «Выпуклая оболочка невозможна».
5. Создайте пустой стек «S» и поместите первые три точки в «S».
6. Обрабатываем оставшиеся m-3 точки одну за другой. Для каждой точки:
⁃ Пока ориентация двух верхних точек в стеке и «points[i]» не против часовой стрелки, извлекайте точки из стека
⁃ Положите «points[i]» в «S».
7. Стек «S» теперь содержит точки выпуклой оболочки.

Сложность: O(nLogn)

BY Алгоритмы и структуры данных