Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.81/27: Рейтинг темы: голосов - 27, средняя оценка - 4.81
AvengerAlive
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
1

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

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

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

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

Напишите программу обхода двоичных деревьев во внутреннем порядке
Помогите найти ошибку в коде. Задание: Напишите программу обхода двоичных...

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

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

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

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

Это то что требуется?
0
Olga_
842 / 184 / 18
Регистрация: 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 ???
0
AvengerAlive
5 / 5 / 1
Регистрация: 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)
0
Olga_
842 / 184 / 18
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 14:56 5
Так я и предполагала с замкнутой ломанной. А вы уверены, что точки ОБЯЗАТЕЛЬНО образуют выпуклый многоугольник, это важно очень.
0
AvengerAlive
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
24.08.2011, 15:01  [ТС] 6
Да, это единственное что известно. Надо просто найти центр масс фигуры, а для этого надо разбить его на треугольники и по формуле найти. Но все точки разбросаны и треугольники построить не получается. надо точки отсортировать чтобы треугольники построить.
0
Olga_
842 / 184 / 18
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 15:04 7
А вам подсказка нужна или программа? Вроде я знаю как отсортировать.
0
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
24.08.2011, 15:07 8
Есть ведь известный алгоритм построения выпуклой оболочки множества точек. Гугл в помощь.
0
Olga_
842 / 184 / 18
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 15:08 9
Цитата Сообщение от silent_1991 Посмотреть сообщение
Есть ведь известный алгоритм построения выпуклой оболочки множества точек. Гугл в помощь.
Есть масса алгоритмов построения выпуклой оболочки.
0
AvengerAlive
5 / 5 / 1
Регистрация: 30.07.2011
Сообщений: 257
24.08.2011, 15:09  [ТС] 10
желательно код, если есть готовый, но алгоритм тоже не помешает хотя приблизительно знаю, по углу от начала координат и ветора измерять, но как то затрудняюсь записать это...
0
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
24.08.2011, 15:16 11
Olga_, кончено есть масса, но есть и несколько более известных, чем другие. Мне в предыдущем сообщении следовало сказать "алгоритмы".
0
Olga_
842 / 184 / 18
Регистрация: 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/
0
24.08.2011, 15:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.08.2011, 15:21

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

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

Сортировка массива в порядке возрастания и вывод элементов в обратном порядке
нашла на форуме пару примеров, но они не полные и не запускаются, выбрала из...


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

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

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