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

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

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

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

03.06.2011, 21:36. Просмотров 1631. Ответов 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++
Здравствуйте! Нужно реализовать метод Джариса(алгоритм заворачивания подарка) и нарисовать результат, что я и сделал #include...

Алгоритм Джарвиса - C++
нужен еще один алгоритм для курсовой работы. Добавлено через 40 минут вот нашел один,ток не пойму как вводить,пожалуйста помогите. ...

Алгоритм Джарвиса - C++
Нужно найти точки принадлежащие выпуклой оболочке с помощью обхода Джарвиса. У меня в программе два цикла один находит точки от...

Нужно написать обход шахматной доски конем. На одну позицию можно стать один раз. Обеспечить алгоритм бектрекингу - C++
Добрый вечер! очень прошу помогите реализовать программу на с \ с + +.

Реализация Алгоритма Грэхема и Джарвиса на С++ - C++
Ищу того, кто сделает за деньги с комментариями к каждой строке. В ЛС цену и за какое время.

Разница между понятиями "Обход в прямом направлении" и "Итерационный прямой обход" - C++
Ребятаа, обьясните чем различается: Обход в прямом направлении и Итерационный прямой обход Добавлено через 10 минут НароооД,...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.06.2011, 21:36
Привет! Вот еще темы с ответами:

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab () { int s1 = 0; int s2 =...

Алгоритм Джарвиса - C (СИ)
Должен записать в массив к номера точек выпуклой оболочки, которые лежат в хаотичном порядке в массиве set Выводит бред - даже первую...

Алгоритм Джарвиса. Прорисовывается еще одна линия, получается треугольник и программа намертво виснет - C#
Имеется программа, реализующая нахождение МВО методом Джарвиса с возможностью сгенерировать набор точек рандомно или выставить их вручную....

Алгоритм поиска в ширину и обход всех точек - Java SE
Привет всем ! Возникла проблема с задачей, нужно помощь... Необходимо реализовать программу реализующая алгоритм поиска, почитав...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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