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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
papa_doc
Сообщений: n/a
03.06.2011, 21:36     Обход Джарвиса (Алгоритм заворачивания подарка) #1
Не могу придумать как написать прогу. Помогите пожалуйста. Суть такова: Пусть дано множество 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++ Реализовать метод Джариса(алгоритм заворачивания подарка) и нарисовать результат

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

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

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