2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Упорядочить вершины многоугольника по(против) часов. стрелке
Сообщение03.04.2009, 20:59 
Аватара пользователя
Привет, вопрос в том чтобы упорядочить вершины многоугольника по или против часовой стрелке. На одном сайте нашел идею:
Код:
Если же многоугольник выпуклый, но вершины перечислены не в порядке обхода, то их придется упорядочить. Сделать это можно, например, отсортировав вершины по углу между положительной полуосью ОХ и вектором (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 - это координаты внутренней точки. Функция работает, только не правильно :D Например если в многоугольнике есть точки которые имеют одинаковую координату 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)))
Использую сортировку пузырьком. Помогите чем можете... :(

 
 
 
 
Сообщение03.04.2009, 21:11 
Аватара пользователя
Я бы работал в полярных координатах (начало координат в центре масс вершин многоугольника) и сортировал бы по $\varphi$ быстрой сортировкой (которая бинарная с рекурсией).

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

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

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

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

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

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group