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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.93
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
#1

Сортировка точек в порядке обхода - C++

24.08.2011, 13:01. Просмотров 3920. Ответов 11
Метки нет (Все метки)

Дано n точек. В массиве a[n][2]. Надо отсортировать точки в порядке обхода по или против часовой стрелки. Нужна помощь.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.08.2011, 13:01
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка точек в порядке обхода (C++):

Напишите программу обхода двоичных деревьев во внутреннем порядке - C++
Помогите найти ошибку в коде. Задание: Напишите программу обхода двоичных деревьев во внутреннем порядке. #include<iostream> ...

Обойти матрицу по спирали и распечатать её элементы в порядке обхода - C++
Задана матрица n*m обойти матрицу по спирали и распечатать её элементы в порядке обхода. Есть у кого-нибудь идеи, как обойти матрицу...

Заданы координаты вершин четырехугольника. Вывести их в порядке обхода по часовой стрелке - C++
Заданы координаты вершин четырехугольника. Вывести их в порядке обхода по часовой стрелке Сабж. Искал по форуму/гуглил - не нашел ответа....

Начиная с центра, обойти по спирали все элементы квадратной матрицы, распечатывая их в порядке обхода - C++
Начиная с центра, обойти по спирали все элементы квадратной матрицы ,распечатывая их в порядке обхода.

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

Разработать алгоритм и написать программу прошивания дерева при симметричном порядке обхода его - C++
Народ интересует такое задание нужно срочно или что по быстрому почитать, чтоб сделать это.

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Mee
14 / 14 / 1
Регистрация: 05.07.2010
Сообщений: 88
24.08.2011, 13:10 #2
Что имеется ввиду под
Цитата Сообщение от AvengerAlive Посмотреть сообщение
отсортировать точки в порядке
приходит в голову только искать углы относительно оси абсцис и упорядочить по возрастанию.

Это то что требуется?
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 13:58 #3
Наверное имеется ввиду, что точки должны соответствовать замкнутой ломанной без самопересечений? Надо конкретнее формулировать. Либо надо сначала ввести упорядоченность на множестве точек и от этого отталкиваться. Либо нужна центральная точка, опираясь на которую можно отсортировать в порядке обхода. Мало информации...

Добавлено через 13 минут
Более подходит предложение Mee, в роли центральной точки O(0,0). Но все равно не понятно что человек хочет...

Добавлено через 12 минут
http://www.cyberforum.ru/cgi-bin/latex.cgi?(x_1,y_1),(x_2,y_2) \in \mathbb{R}^2
http://www.cyberforum.ru/cgi-bin/latex.cgi?(x_1,y_1)\leq(x_2,y_2) \Leftrightarrow ???
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
24.08.2011, 14:52  [ТС] #4
У нас есть массив точек. Надо взять первую точку, и отсортировать массив так, чтобы массив стал из точек которые нам будут встречатся если мы будем обходить этот многоугольник по часовой стрелке. Ну например есть точки (0 0) (1 0) (0 1) (1 1) надо сделать (0 0) (0 1) (1 1) (1 0)
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 14:56 #5
Так я и предполагала с замкнутой ломанной. А вы уверены, что точки ОБЯЗАТЕЛЬНО образуют выпуклый многоугольник, это важно очень.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
24.08.2011, 15:01  [ТС] #6
Да, это единственное что известно. Надо просто найти центр масс фигуры, а для этого надо разбить его на треугольники и по формуле найти. Но все точки разбросаны и треугольники построить не получается. надо точки отсортировать чтобы треугольники построить.
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 15:04 #7
А вам подсказка нужна или программа? Вроде я знаю как отсортировать.
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
24.08.2011, 15:07 #8
Есть ведь известный алгоритм построения выпуклой оболочки множества точек. Гугл в помощь.
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 15:08 #9
Цитата Сообщение от silent_1991 Посмотреть сообщение
Есть ведь известный алгоритм построения выпуклой оболочки множества точек. Гугл в помощь.
Есть масса алгоритмов построения выпуклой оболочки.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
24.08.2011, 15:09  [ТС] #10
желательно код, если есть готовый, но алгоритм тоже не помешает хотя приблизительно знаю, по углу от начала координат и ветора измерять, но как то затрудняюсь записать это...
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
24.08.2011, 15:16 #11
Olga_, кончено есть масса, но есть и несколько более известных, чем другие. Мне в предыдущем сообщении следовало сказать "алгоритмы".
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 15:21 #12
Кода готового пока нет. А алгоритм такой. Берем первую точку массива (x1,y1). Из всех оставшихся точек ищем такую (x0,y0), чтобы все векторные произведения векторов (x0,y0)-(x1,y1) и (x,y)-(x0,y0) были одного знака. Эту точку (x0,y0) ставим на вторую позицию и т.д.

Добавлено через 4 минуты
Вот здесь алгоритмы с реализацией:
http://algolist.manual.ru/maths/geom/convhull/
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.08.2011, 15:21
Привет! Вот еще темы с ответами:

Заданы координаты вершин треугольника. Вывести их в порядке обхода треугольника по часовой стрелке - C++
Заданы координаты вершин треугольника.Вывести их в порядке обхода треугольника по часовой стрелке. Вот код, но правильный ли он?! ...

Сортировка массива в порядке возрастания и вывод элементов в обратном порядке - C++
нашла на форуме пару примеров, но они не полные и не запускаются, выбрала из них более менее подходящий, дальше было много вариантов но не...

Сортировка подсчетом вектора точек - C++
Ребята, нужна помощь! Нужно реализовать сортировку подсчетом для вектора точек. Есть некий шаблон для функции. P.S. идея в том,...

Вывод всех исходных точек в порядке возрастания их расстояний от начала координат - C++
Выведите все исходные точки в порядке возрастания их расстояний от начала координат. Входные данные Программа получает на вход...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
24.08.2011, 15:21
Ответ Создать тему
Опции темы

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