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

[Александр_ФФ]

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

[MIT]

А что тут сложного?
Ищем правую верхнюю точку
правую нижнюю
левую нижнюю
левую верхнюю

[Хакер]

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

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

[Александр_ФФ]

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

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

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

[Хакер]

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

[Александр_ФФ]

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

[Хакер]

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

[Zenitchik]

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

[Александр_ФФ]

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

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

[Хакер]

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

[Александр_ФФ]

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

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

[Zenitchik]

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

[Александр Дмитриев]

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

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

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

Потратил я в своё время на эту идею суммарно часов 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)).

[Хакер]

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

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

[Александр Дмитриев]

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



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



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

[Хакер]

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



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

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

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

[Александр_ФФ]

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

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

[Александр Дмитриев]

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

[Хакер]

Ну деформируй фигуру как-нибудь иначе. Передвинь вершину, возьми возьми другую нормаль.

[Zenitchik]

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

[Александр Дмитриев]

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

[Хакер]

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

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

[Nord777]

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

[Александр Дмитриев]

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

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

[Хакер]

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

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

[Хакер]

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

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

[Nord777]

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

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

Да уж. О таких закидонах я не подумал.

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

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

[Хакер]

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

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

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

[Nord777]

Немного подумав, решил ответить, что ты прав, но ты опередил

[Хакер]

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


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

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

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