Упорядочить вершины многоугольника по(против) часов. стрелке

[Banks]

Привет, вопрос в том чтобы упорядочить вершины многоугольника по или против часовой стрелке. На одном сайте нашел идею:

Если же многоугольник выпуклый, но вершины перечислены не в порядке обхода, то их придется упорядочить. Сделать это можно, например, отсортировав вершины по углу между положительной полуосью ОХ и вектором (Xi-Xm, Yi-Ym).

Где Xm и Ym-любая точка внутри многоугольника. Для определения этой точки я написал функцию, там вроде без проблем. А вот с сортировкой возникли проблемы:

void polygon::sorting(double x_int,double y_int)
{
   double temp;
   for(int i=0; i < number; i++)
   {
      for(int j = number-1; j > i; j-- )
      {
         if ( acos((x[j-1]-x_int)/sqrt((x[j-1]-x_int)*(x[j-1]-x_int)+(y[j-1]-y_int)*(y[j-1]-y_int))) < acos((x[j]-x_int)/sqrt((x[j]-x_int)*(x[j]-x_int)+(y[j]-y_int)*(y[j]-y_int))))
         {
            temp=x[j-1]; x[j-1]=x[j]; x[j]=temp;
            temp=y[j-1]; y[j-1]=y[j]; y[j]=temp;
         }


      }
   }
   
   return;
}

double x_int,double y_int - это координаты внутренней точки. Функция работает, только не правильно Например если в многоугольнике есть точки которые имеют одинаковую координату x, но разную y. В этом случае

acos((x[j-1]-x_int)/sqrt((x[j-1]-x_int)*(x[j-1]-x_int)+(y[j-1]-y_int)*(y[j-1]-y_int))) = acos((x[j]-x_int)/sqrt((x[j]-x_int)*(x[j]-x_int)+(y[j]-y_int)*(y[j]-y_int)))

Использую сортировку пузырьком. Помогите чем можете...

[Droog_Andrey]

Я бы работал в полярных координатах (начало координат в центре масс вершин многоугольника) и сортировал бы по $\varphi$ быстрой сортировкой (которая бинарная с рекурсией).

[Dandan]

acos возвращает значения в интервале $[0, \pi]$, так что для симметричных относительно внутренней точки вершин acos вернет одинаковые значения. Таким образом упорядочить не получится. Нужно использовать atan2 (да и проще выйдет).

[Pavia]

В модуле Math должна быть функция ArcTan2(y,x) вычисляет ArcTan(Y/X), но возращает в отличии от такого варианта правильный угол для заданного квадранта.
Возращаемое значение лижит в диапазоне от -Pi до +Pi.

Во-первых это удобно, во-вторых аппаратно реализованно.

[ha]

Вообще-то никакой сортировки для этого делать не надо. Нужно просто посчитать площадь многоугольника. А затем по знаку определить ориентацию.
Указание. Ориентированная площадь треугольника с координатами $(0,0),\ (x_1,y_1),\ (x_2,y_2)$ равна $(x_1y_2-x_2y_1)/2$.

[Dandan]

ha, перечитайте условие внимательно. Нужно как раз отсортировать, а не определить какая ориентация. Хотя для определения ориентации (по заданному порядку обхода вершин) несомненно ваш алгоритм верен.