Не могу придумать алгоритм такой сортировки

Здесь Вы можете найти или обсудить множество различных алгоритмов, их описаний, реализаций на VB и других языках.
Александр_ФФ
Обычный пользователь
Обычный пользователь
 
Сообщения: 93
Зарегистрирован: 23.11.2008 (Вс) 11:09
Откуда: Северодвинск

Не могу придумать алгоритм такой сортировки

Сообщение Александр_ФФ » 13.05.2009 (Ср) 22:12

Пишу программу, застрял на таком блоке:
Пользователь ставит на поле точки мышью, создавая многоугольник (примем, что он простой: без самопересечений и сильной деформации)
точки заносятся в массив А(n,1) =x A(n,2)=y n - порядковый номер точки
Таким образом, точки в массиве будут перечислены по часовой стрелке или против часовой стрелки (как их ставили).
Задача - надо отсортировать массив точек, чтобы они были по часовой стрелке. и образовывали тот же многоугольник
что-то я затупил :roll:

MIT
Мега гуру
Мега гуру
Аватара пользователя
 
Сообщения: 2211
Зарегистрирован: 17.09.2006 (Вс) 22:46

Re: Не могу придумать алгоритм такой сортировки

Сообщение MIT » 13.05.2009 (Ср) 22:35

А что тут сложного?
Ищем правую верхнюю точку
правую нижнюю
левую нижнюю
левую верхнюю
Изображение
You can change your face, but can`t change your mind. No matter what you do.
Создайте еще более понятный интерфейс и мир создаст еще более тупого юзера. (с) Баш

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Хакер » 13.05.2009 (Ср) 22:39

Если точки обязательно идут либо по, либо против часовой стрелки, то выбрать две любые точки, преобразовать прямоугольные координаты в полярные, сравнить Фи, при необходимости развернуть порядок следования (или обхода) точек.

Если точки идут в произвольном порядке, то всё равно преобразовать прямоугольные координаты в полярные и отсортировать точки по Фи (угловой координате).
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Александр_ФФ
Обычный пользователь
Обычный пользователь
 
Сообщения: 93
Зарегистрирован: 23.11.2008 (Вс) 11:09
Откуда: Северодвинск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Александр_ФФ » 14.05.2009 (Чт) 20:39

Хакер писал(а):Если точки обязательно идут либо по, либо против часовой стрелки, то выбрать две любые точки, преобразовать прямоугольные координаты в полярные, сравнить Фи, при необходимости развернуть порядок следования (или обхода) точек.

Если точки идут в произвольном порядке, то всё равно преобразовать прямоугольные координаты в полярные и отсортировать точки по Фи (угловой координате).


Условие: изначально либо по, либо против часовой стрелки.
Вы правы, я так тоже думаю :wink: . Но! полярные координаты относительно какого центра? Среднее геометрическое точек - не всегда катит, например у фигуры "полумесяц" :(
Да и любые две - не очень. там может быть "вмятина" .

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Хакер » 14.05.2009 (Чт) 20:43

Если ты позволяешь себе говорить о часовой стрелки, то значит сам ты всё таки берёшь какую-то точку за ось вращения этой стрелки.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Александр_ФФ
Обычный пользователь
Обычный пользователь
 
Сообщения: 93
Зарегистрирован: 23.11.2008 (Вс) 11:09
Откуда: Северодвинск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Александр_ФФ » 15.05.2009 (Пт) 12:44

Центр - какая-то точка внутри фигуры. не обязательно геом. центр. А вот какая?
Кажется, у меня есть идея - направление определять большинством одинаково направленых отрезков.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Хакер » 15.05.2009 (Пт) 13:32

Ну сам-то ты как определяешь, какая?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Zenitchik
Постоялец
Постоялец
 
Сообщения: 369
Зарегистрирован: 21.12.2006 (Чт) 14:48

Re: Не могу придумать алгоритм такой сортировки

Сообщение Zenitchik » 15.05.2009 (Пт) 16:46

Если многоугольник выпуклый - есть классический способ.
Выбираем самую правую точку и относительно нее ищем в полярных координатах точку с наименьшим Фи. Потом каждую следующую точку ищем тем же методом, но относительно предыдущей.
Знание английского языка - затрудняет понимание кода

Александр_ФФ
Обычный пользователь
Обычный пользователь
 
Сообщения: 93
Зарегистрирован: 23.11.2008 (Вс) 11:09
Откуда: Северодвинск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Александр_ФФ » 16.05.2009 (Сб) 21:04

Хакер писал(а):Ну сам-то ты как определяешь, какая?

Человеческий мозг как-то получше справляется. да мне и не надо точки определять. :wink:
Смысл такой: для каждого отрезка многоугольника можно построить нормаль _|_ к отрезку (вектору). она будет направлена или внутрь фигуры, или наружу. Мне надо всегда наружу. Выход такой: при необходимости переворачивать вектор (т.е. все векторы, т.е. пронумеровать точки многоугольника в обратной последовательности).
Вопрос: как определить, внутрь или наружу направлена нормаль?
она напрямую завистит от способа рисования фигуры (по часовой/против часовой)

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Хакер » 16.05.2009 (Сб) 21:06

Если внутрь, то нормаль пересечёт контур фигуры нечётное кол-во раз, если во внешний мир --- чётное.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Александр_ФФ
Обычный пользователь
Обычный пользователь
 
Сообщения: 93
Зарегистрирован: 23.11.2008 (Вс) 11:09
Откуда: Северодвинск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Александр_ФФ » 17.05.2009 (Вс) 17:06

Хакер писал(а):Если внутрь, то нормаль пересечёт контур фигуры нечётное кол-во раз, если во внешний мир --- чётное.


:D Благодарю!!! Буду доумть, что такое "пересечёт" с программисткой точки зрения. это где-то было на форумах.
Если всё получится - покажу саму прогу

Zenitchik
Постоялец
Постоялец
 
Сообщения: 369
Зарегистрирован: 21.12.2006 (Чт) 14:48

Re: Не могу придумать алгоритм такой сортировки

Сообщение Zenitchik » 18.05.2009 (Пн) 12:21

Существует точка, лежащая в пределах диапазонов координат обоих отрезков и удовлетворяющая уравнениям содержащих эти отрезки прямых.
Знание английского языка - затрудняет понимание кода

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

Re: Не могу придумать алгоритм такой сортировки

Сообщение Александр Дмитриев » 19.05.2009 (Вт) 4:14

Хакер писал(а):Если ты позволяешь себе говорить о часовой стрелки, то значит сам ты всё таки берёшь какую-то точку за ось вращения этой стрелки.

Замкнутая ломаная может идти по часовой стрелке и сама по себе (вне зависимости ни от какой точки отсчёта), ведь так?

Хакер писал(а):Если внутрь, то нормаль пересечёт контур фигуры нечётное кол-во раз, если во внешний мир --- чётное.

Потратил я в своё время на эту идею суммарно часов 10. Ну не прокатывает этот метод в некоторых случаях, хоть как его улучшай!

Предлагаю следующий метод. Все отрезки многоугольника рассматриваем как вектора (и переносим их в начало координат). Суммируем углы между векторами с учётом направления (то есть если поворот от одного вектора к другому идёт против часовой стрелки, то угол считается положительным, если по часовой - отрицательным). Сначала берём угол между первым вектором и вторым, прибавляем к нему угол между вторым и третьим и т.д., в конце прибавляем угол между последним вектором и первым. Если в конечном итоге получится 2*pi, то ломаная кривая идёт против часой стрелки, если же -2*pi, то по часовой. Угол можно вычислить через скалярное произведение (угол = arccos((x1 * y1 + x2 * y2) / (sqrt(x1^2 + y1^2) * sqrt(x2^2 + y2^2)))), направление - через векторное (направление (1, 0, или -1) = sign(x1 * y2 - y1 * x2)).

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Хакер » 19.05.2009 (Вт) 9:20

Александр Дмитриев писал(а):Потратил я в своё время на эту идею суммарно часов 10. Ну не прокатывает этот метод в некоторых случаях, хоть как его улучшай!

С чего это? Межет туфли не при чём?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

Re: Не могу придумать алгоритм такой сортировки

Сообщение Александр Дмитриев » 20.05.2009 (Ср) 0:33

Вот примерно в таком случае метод покажет, что нормаль направлена наружу:

Изображение

Сначала алгоритм посчитает конец одного отрезка, потом - начало другого. Всего получится 2 пересечения. Если при определении пересечения нормалью отрезка не учитывать крайние точки этого отрезка (то есть в проверке, описанной Зенитчиком, поставить строгие неравенства), то пересечений будет 0. Можно ещё придумать учитывать начало отрезка, но не учитывать конец, но в другом контрпримере алгоритм опять будет работать неверно:

Изображение

Я там ещё чего-то придумал, сейчас уже не получается вспомнить, но всё-равно через некоторое время придумал и этому контрпример.
Кажется, что на практике такие случаи маловероятны (особенно когда все координаты double и т.д.), но опыт показывает, что не так уж и маловероятны. Особенно, когда рисует программа (вертикальные, горизонтальные и т.д. линии). Хотя в данном случае рисует человек, поэтому, в принципе, способ приемлем.
Вложения
1.jpg
1.jpg (6.08 Кб) Просмотров: 18472
2.jpg
2.jpg (4.8 Кб) Просмотров: 18474

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Хакер » 20.05.2009 (Ср) 1:27

Александр Дмитриев писал(а):Вот примерно в таком случае метод покажет, что нормаль направлена наружу:

Изображение

Сначала алгоритм посчитает конец одного отрезка, потом - начало другого. Всего получится 2 пересечения. Если при определении пересечения нормалью отрезка не учитывать крайние точки этого отрезка (то есть в проверке, описанной Зенитчиком, поставить строгие неравенства), то пересечений будет 0. Можно ещё придумать учитывать начало отрезка, но не учитывать конец, но в другом контрпримере алгоритм опять будет работать неверно:

Изображение

А всего-то надо: если нормаль попала на вершину (место сочленения двух рёбер), но нужно проверить пересечение нормали с отрезком, концами которого являются необщие концы рассматриваемых рёбер. И трактовать это пересечение как обычное пересечение.

Картинку надо?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Александр_ФФ
Обычный пользователь
Обычный пользователь
 
Сообщения: 93
Зарегистрирован: 23.11.2008 (Вс) 11:09
Откуда: Северодвинск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Александр_ФФ » 20.05.2009 (Ср) 14:28

Ничего себе тема развернулась!
Новое для себя узнал, спасибо участникам :-)
Верно, надо просто сложить все углы и не мучаться. Что-то я сразу не догнал. Александр Дмитриев, выручили!

Потом будут ещё с программой проблемы, буду писать сюда

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

Re: Не могу придумать алгоритм такой сортировки

Сообщение Александр Дмитриев » 20.05.2009 (Ср) 19:13

Хакер Извини, но контрпример

Изображение
Вложения
3.jpg
3.jpg (6.93 Кб) Просмотров: 18435

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Хакер » 20.05.2009 (Ср) 22:22

Ну деформируй фигуру как-нибудь иначе. Передвинь вершину, возьми возьми другую нормаль.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Zenitchik
Постоялец
Постоялец
 
Сообщения: 369
Зарегистрирован: 21.12.2006 (Чт) 14:48

Re: Не могу придумать алгоритм такой сортировки

Сообщение Zenitchik » 23.05.2009 (Сб) 9:49

Гениально.
Если нормаль попала в вершину - берется другая нормаль - к тому же отрезку.
Знание английского языка - затрудняет понимание кода

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

Re: Не могу придумать алгоритм такой сортировки

Сообщение Александр Дмитриев » 23.05.2009 (Сб) 11:18

Изображение

Для этой ломаной можно однозначно сказать, что она идёт против часовой стрелки и что нормаль направлена наружу. Если при проверке пересечения учитывать начало нормали, метод даст неверный ответ. Если его не учитывать, метод даст неверный ответ для такого же многоугольника, но с нормалью, построенной в том же направлении для красного отрезка. Если делать проверку на наложение отрезков одного на другой, то непонятно, в каком направлении в случае наложения двигать один из наложившихся отрезков, а нормаль вообще бессмысленно двигать.
Вложения
4.jpg
4.jpg (5.22 Кб) Просмотров: 18392

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Хакер » 23.05.2009 (Сб) 11:25

Не согласен насчёт однозначности.

И вообще, дай строгое математическое определение своим понятиям «по часово» и «против». Пока ты этого не сделаешь, решение проблемы будет глупым брутфорсом.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Nord777
Гуру
Гуру
Аватара пользователя
 
Сообщения: 1144
Зарегистрирован: 22.02.2004 (Вс) 13:15
Откуда: Подольск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Nord777 » 23.05.2009 (Сб) 14:33

Какие нормали? Какие пересечения? Зачем всё усложнять?
Задача решается просто.
Необходимо вычислить какое направление имеет каждый из углов фигуры(по часовой или против)
Далее подсчитать кол-во углов по часовой и против.
Если больше по часовой - значит вся фигура - по часовой, в противном случае - против.
Вычислить направление угла - не сложно. Тупо проверки и минимум мат. операций.
Microsoft Visual Studio 2008
Microsoft .NET Framework 3.5

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

Re: Не могу придумать алгоритм такой сортировки

Сообщение Александр Дмитриев » 23.05.2009 (Сб) 15:06

Nord777 писал(а):Если больше по часовой - значит вся фигура - по часовой, в противном случае - против

Вот в таком случае направление по часовой стрелке имеют 4 угла, а против - 3 угла, но вся ломаная идёт против часовой:

Изображение
Вложения
5.jpg
5.jpg (6.19 Кб) Просмотров: 18370

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Хакер » 23.05.2009 (Сб) 15:07

Если больше по часовой - значит вся фигура - по часовой, в противном случае - против.

А если одинаково?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Хакер » 23.05.2009 (Сб) 15:12

Ладно, предлагаю свой вариант с учётом своей трактовки понятия «по часовой».

Предлагаю многоугольник итеративно упроситить до треугольника (заменяя два смежных ребра одним единственным), а потом проверить, как нарисован треугольник. С треугольником, я думаю, никаких проблем не выйдет?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Nord777
Гуру
Гуру
Аватара пользователя
 
Сообщения: 1144
Зарегистрирован: 22.02.2004 (Вс) 13:15
Откуда: Подольск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Nord777 » 23.05.2009 (Сб) 15:36

Вот в таком случае направление по часовой стрелке имеют 4 угла, а против - 3 угла, но вся ломаная идёт против часовой
А если одинаково?
Да уж. О таких закидонах я не подумал. :D


Предлагаю многоугольник итеративно упроситить до треугольника (заменяя два смежных ребра одним единственным),
Наверно не два смежных.
Если угол тупой - обьединять, если острый - оставлять. Правда это надо проверять, а то вдруг еще одно исключение появится...
Microsoft Visual Studio 2008
Microsoft .NET Framework 3.5

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Хакер » 23.05.2009 (Сб) 15:53

Зачем? Проще всего превратить в треугольник, «коллапсируя» все смежные рёбра, пока их не станет 3.

Потом для проверки останется выполнить только одно действие: взять любую грань, рассмотреть её как вектор и посмотреть, по какую сторону от неё лежит оставшаяся точка-вершина. Если по правую — значит фигура нечерчена «по часовой».

Единственное, надо проверять при коллапсировании результат, чтобы не допустить ситуацию, когда в конце концов все три вершины окажутся на одной линии
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Nord777
Гуру
Гуру
Аватара пользователя
 
Сообщения: 1144
Зарегистрирован: 22.02.2004 (Вс) 13:15
Откуда: Подольск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Nord777 » 23.05.2009 (Сб) 15:56

Немного подумав, решил ответить, что ты прав, но ты опередил :D
Microsoft Visual Studio 2008
Microsoft .NET Framework 3.5

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Не могу придумать алгоритм такой сортировки

Сообщение Хакер » 23.05.2009 (Сб) 16:35

Да, кстати, при коллапсировании нельзя допускать изменения топологии, т.е. коллапсировать нужно в определённом порядке. На вскидку: составить список вершин и углов, отсоритировать по углу в порядке убывания, убрать последние три пункта из списка, и в путь. После каждого коллапсе одну (устранённую) вершину надо из списка удалять, а для двух других (которые соединили ребром) обновлять угол. При этом, вероятно, придётся изменять их положение в списке.


ADDED: нет, при сортировке по углу тоже возможно нарушение топологии.

Придумал:
Нужно провести триангуляцию фигуры. Коллапсировать можно только те рёбра, которые принадлежат одному триангуляционному треугольнику (тафтология, но всё же). После коллапса полученная новая грань становится частью какого-то другого треугольника. И так до тех пор, пока не останется единственный треугольник.

И ещё один вариант придумал, двух проходный, но пусть автор пока попробует найти контрпример (если такой существует) к вышеописанному способу с триангуляцией.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

След.

Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3

    TopList