Сортировка точек на плоскости по/против часовой стрелки

258

26 июля 2017, 22:58

Есть набор точек типа std::pair<int, int>, представляющих собой вершины некоторого многоульника (вообще говоря, невыпуклого). Дана некоторая вершина из набора. Необходимо отсортировать набор так, чтобы он начинался с этой стартовой вершины и далее шёл по/против часовой стрелки.

Answer 1

Предложил было такой вариант... Берем такую функцию - atan2, она вроде как аккуратно углы рассчитывает. Сортируем по углу. Начиная с нужной нам вершины идем до конца массива, потом добираем оставшиеся точки в том же направлении по массиву, но с другого конца.

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

Но если ее нет - задача вообще оказывается неоднозначна. Лень рисовать, представьте себе 5 точек - 4 в вершинах квадрата, по часовой - 1,2,3,4. и 0 - в его центре.

01234 - искомый вариант, если за центр взять, например, половину высоты от 0 на сторону 23. Но точно так же годится 02341 - только точка на высоте от 0 на сторону 34...

Если все равно, какое решение принять - то как вариант, построить выпуклую оболочку, потом выбрать одну из точек - например, нижнюю, а уж потом все остальные отсортировать и построить эдакую "звездочку" :)