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

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

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

Алгоритм:

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/4967

4.08K viewsAug 19 at 09:04

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

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

Алгоритм:

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 Алгоритмы и структуры данных