Страница 1 из 3

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

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

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

СообщениеДобавлено: 13.05.2009 (Ср) 22:35
MIT
А что тут сложного?
Ищем правую верхнюю точку
правую нижнюю
левую нижнюю
левую верхнюю

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

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

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

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

СообщениеДобавлено: 14.05.2009 (Чт) 20:39
Александр_ФФ
Хакер писал(а):Если точки обязательно идут либо по, либо против часовой стрелки, то выбрать две любые точки, преобразовать прямоугольные координаты в полярные, сравнить Фи, при необходимости развернуть порядок следования (или обхода) точек.

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


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

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

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

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

СообщениеДобавлено: 15.05.2009 (Пт) 12:44
Александр_ФФ
Центр - какая-то точка внутри фигуры. не обязательно геом. центр. А вот какая?
Кажется, у меня есть идея - направление определять большинством одинаково направленых отрезков.

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

СообщениеДобавлено: 15.05.2009 (Пт) 13:32
Хакер
Ну сам-то ты как определяешь, какая?

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

СообщениеДобавлено: 15.05.2009 (Пт) 16:46
Zenitchik
Если многоугольник выпуклый - есть классический способ.
Выбираем самую правую точку и относительно нее ищем в полярных координатах точку с наименьшим Фи. Потом каждую следующую точку ищем тем же методом, но относительно предыдущей.

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

СообщениеДобавлено: 16.05.2009 (Сб) 21:04
Александр_ФФ
Хакер писал(а):Ну сам-то ты как определяешь, какая?

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

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

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

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

СообщениеДобавлено: 17.05.2009 (Вс) 17:06
Александр_ФФ
Хакер писал(а):Если внутрь, то нормаль пересечёт контур фигуры нечётное кол-во раз, если во внешний мир --- чётное.


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

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

СообщениеДобавлено: 18.05.2009 (Пн) 12:21
Zenitchik
Существует точка, лежащая в пределах диапазонов координат обоих отрезков и удовлетворяющая уравнениям содержащих эти отрезки прямых.

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)).

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

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

С чего это? Межет туфли не при чём?

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

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

Изображение

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

Изображение

Я там ещё чего-то придумал, сейчас уже не получается вспомнить, но всё-равно через некоторое время придумал и этому контрпример.
Кажется, что на практике такие случаи маловероятны (особенно когда все координаты double и т.д.), но опыт показывает, что не так уж и маловероятны. Особенно, когда рисует программа (вертикальные, горизонтальные и т.д. линии). Хотя в данном случае рисует человек, поэтому, в принципе, способ приемлем.

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

СообщениеДобавлено: 20.05.2009 (Ср) 1:27
Хакер
Александр Дмитриев писал(а):Вот примерно в таком случае метод покажет, что нормаль направлена наружу:

Изображение

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

Изображение

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

Картинку надо?

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

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

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

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

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

Изображение

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

СообщениеДобавлено: 20.05.2009 (Ср) 22:22
Хакер
Ну деформируй фигуру как-нибудь иначе. Передвинь вершину, возьми возьми другую нормаль.

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

СообщениеДобавлено: 23.05.2009 (Сб) 9:49
Zenitchik
Гениально.
Если нормаль попала в вершину - берется другая нормаль - к тому же отрезку.

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

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

Для этой ломаной можно однозначно сказать, что она идёт против часовой стрелки и что нормаль направлена наружу. Если при проверке пересечения учитывать начало нормали, метод даст неверный ответ. Если его не учитывать, метод даст неверный ответ для такого же многоугольника, но с нормалью, построенной в том же направлении для красного отрезка. Если делать проверку на наложение отрезков одного на другой, то непонятно, в каком направлении в случае наложения двигать один из наложившихся отрезков, а нормаль вообще бессмысленно двигать.

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

СообщениеДобавлено: 23.05.2009 (Сб) 11:25
Хакер
Не согласен насчёт однозначности.

И вообще, дай строгое математическое определение своим понятиям «по часово» и «против». Пока ты этого не сделаешь, решение проблемы будет глупым брутфорсом.

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

СообщениеДобавлено: 23.05.2009 (Сб) 14:33
Nord777
Какие нормали? Какие пересечения? Зачем всё усложнять?
Задача решается просто.
Необходимо вычислить какое направление имеет каждый из углов фигуры(по часовой или против)
Далее подсчитать кол-во углов по часовой и против.
Если больше по часовой - значит вся фигура - по часовой, в противном случае - против.
Вычислить направление угла - не сложно. Тупо проверки и минимум мат. операций.

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

СообщениеДобавлено: 23.05.2009 (Сб) 15:06
Александр Дмитриев
Nord777 писал(а):Если больше по часовой - значит вся фигура - по часовой, в противном случае - против

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

Изображение

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

СообщениеДобавлено: 23.05.2009 (Сб) 15:07
Хакер
Если больше по часовой - значит вся фигура - по часовой, в противном случае - против.

А если одинаково?

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

СообщениеДобавлено: 23.05.2009 (Сб) 15:12
Хакер
Ладно, предлагаю свой вариант с учётом своей трактовки понятия «по часовой».

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

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

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


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

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

СообщениеДобавлено: 23.05.2009 (Сб) 15:53
Хакер
Зачем? Проще всего превратить в треугольник, «коллапсируя» все смежные рёбра, пока их не станет 3.

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

Единственное, надо проверять при коллапсировании результат, чтобы не допустить ситуацию, когда в конце концов все три вершины окажутся на одной линии

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

СообщениеДобавлено: 23.05.2009 (Сб) 15:56
Nord777
Немного подумав, решил ответить, что ты прав, но ты опередил :D

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

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


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

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

И ещё один вариант придумал, двух проходный, но пусть автор пока попробует найти контрпример (если такой существует) к вышеописанному способу с триангуляцией.