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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.93
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
24.08.2011, 13:01     Сортировка точек в порядке обхода #1
Дано n точек. В массиве a[n][2]. Надо отсортировать точки в порядке обхода по или против часовой стрелки. Нужна помощь.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mee
 Аватар для Mee
14 / 14 / 1
Регистрация: 05.07.2010
Сообщений: 88
24.08.2011, 13:10     Сортировка точек в порядке обхода #2
Что имеется ввиду под
Цитата Сообщение от AvengerAlive Посмотреть сообщение
отсортировать точки в порядке
приходит в голову только искать углы относительно оси абсцис и упорядочить по возрастанию.

Это то что требуется?
Olga_
 Аватар для 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_
 Аватар для 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_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
24.08.2011, 15:04     Сортировка точек в порядке обхода #7
А вам подсказка нужна или программа? Вроде я знаю как отсортировать.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
24.08.2011, 15:07     Сортировка точек в порядке обхода #8
Есть ведь известный алгоритм построения выпуклой оболочки множества точек. Гугл в помощь.
Olga_
 Аватар для 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
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
24.08.2011, 15:16     Сортировка точек в порядке обхода #11
Olga_, кончено есть масса, но есть и несколько более известных, чем другие. Мне в предыдущем сообщении следовало сказать "алгоритмы".
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.08.2011, 15:21     Сортировка точек в порядке обхода
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
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/
Yandex
Объявления
24.08.2011, 15:21     Сортировка точек в порядке обхода
Ответ Создать тему
Опции темы

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