Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
papa_doc
Сообщений: n/a
#1

Обход Джарвиса (Алгоритм заворачивания подарка) - C++

03.06.2011, 21:36. Просмотров 1585. Ответов 0
Метки нет (Все метки)

Не могу придумать как написать прогу. Помогите пожалуйста. Суть такова: Пусть дано множество P = {p1,p2,...pn} точек. В качестве начальной берётся самая левая нижняя точка p1 (ее можно найти за O(n) обычным проходом по всем точкам), она точно является вершиной выпуклой оболочки. Затем для каждой точки pi ищется против часовой стрелки точка pi + 1 путём нахождения за O(n) среди оставшихся точек (+ самая левая нижняя) точки с наименьшим полярным углом pi − 1pipi + 1. Она и будет следующей вершиной выпуклой оболочки. При этом сам угол не обязательно вычислять, достаточно вычислить векторное произведение (обобщением векторного произведения для двумерного случая является псевдоскалярное произведение) между лучами pip'i + 1 и pip''i + 1, где p'i + 1 найденный на данный момент минимум, p''i + 1 претендент (первым минимумом может быть выбрана любая точка). Если векторное произведение отрицательно, то найден новый минимум. Если равно нулю, то есть p'i + 1 и p''i + 1 лежат на одной прямой, то минимум та, которая лежит дальше от точи pi. Алгоритм продолжается пока . Почему алгоритм остановится? Потому что самая левая нижняя точка в любом случае принадлежит выпуклой оболочке.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2011, 21:36     Обход Джарвиса (Алгоритм заворачивания подарка)
Посмотрите здесь:
C++ Реализовать метод Джариса(алгоритм заворачивания подарка) и нарисовать результат
Алгоритм Джарвиса C++
C++ Алгоритм Джарвиса
Нужно написать обход шахматной доски конем. На одну позицию можно стать один раз. Обеспечить алгоритм бектрекингу C++
Реализация Алгоритма Грэхема и Джарвиса на С++ C++
Разница между понятиями "Обход в прямом направлении" и "Итерационный прямой обход" C++
обход C++
обход дерева C++
Обход матрицы C++
C++ обход дерева
Обход дерева) C++
Обход матрицы C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru