Построение выпуклой оболочки методом Дейкстры и звёздчатого многоугольника на Си(C++)


Добавил:DMT
Дата создания:29 апреля 2008, 17:46
Дата обновления:29 апреля 2008, 17:46
Просмотров:5783 последний сегодня, 7:32
Комментариев: 3
Исходник программы - построение выпуклой оболочки методом Дейкстры и звёздчатого многоугольника на Си(C++)
Код на C++
  1. #include <graphics.h>
  2. #include <conio.h>
  3. #include <math.h>
  4. #include <stdlib.h>
  5. #define PI 3.14159
  6.  
  7. struct Point // класс точки
  8. {
  9. double x, y; // координаты точки
  10. int code(Point q); // код четверти, в которой лежит точка q
  11. double operator*(Point q); // векторное произведение
  12. Point operator-(Point q); // разность векторов
  13. };
  14.  
  15. int Point::code(Point q) // код четверти, в которой лежит точка q
  16. {
  17. // начало координат находится в точке (x, y)
  18. if(q.x - x >= 0 && q.y - y >= 0) return 0;
  19. if(q.x - x < 0 && q.y - y >= 0) return 1;
  20. if(q.x - x >= 0 && q.y - y < 0) return 3;
  21. if(q.x - x < 0 && q.y - y < 0) return 2;
  22. }
  23.  
  24. double Point::operator*(Point q)
  25. {
  26. return x * q.y - y * q.x; // векторное произведение
  27. }
  28. Point Point::operator-(Point q) // разность векторов
  29. {
  30. Point t; t.x = x - q.x; t.y = y - q.y; return t;
  31. }
  32.  
  33. int operator<(Point p, Point q)
  34. {
  35. Point t; // сравнение углов радиус-векторов p и q
  36. t.x = 0; t.y = 0; // коды четвертей вычисляются
  37. // относительно (0,0)
  38. if(t.code(p) < t.code(q)) return 1;
  39. if(t.code(p) > t.code(q)) return 0;
  40. return (p * q > 0); // вращение от p к q направлено
  41. // против часовой стрелки
  42. }
  43. int intersect(Point p, Point p1, Point p2)
  44. {
  45. // тест на пересечение луча и отрезка
  46. if(p1.y == p2.y) return 0;
  47. if((p1.y < p2.y ? p2.y : p1.y) <= p.y) return 0;
  48. if((p1.y < p2.y ? p1.y : p2.y) > p.y) return 0;
  49. if(p2.y - p1.y > 0) return
  50. ((p.x - p1.x)*(p2.y - p1.y)-(p2.x - p1.x)*(p.y - p1.y) > 0);
  51. else return
  52. ((p.x - p1.x)*(p2.y - p1.y)-(p2.x - p1.x)*(p.y - p1.y) < 0);
  53. }
  54.  
  55. class SPolygon
  56. {
  57. protected:
  58. int color, n;
  59. Point *p, pC;
  60. public:
  61. SPolygon(int cl):color(cl){} // конструктор по умолчанию
  62. SPolygon(double *x, double *y, int m, int cl);
  63. int isin(Point t);
  64. void show(double xmin, double ymin,
  65. double xmax, double ymax);
  66. };
  67. SPolygon::SPolygon(double *x, double *y, int m, int cl):color(cl)
  68. {
  69. int i, j;
  70. Point t;
  71. p = new Point [m]; n = m;
  72. pC.x = 0; pC.y = 0;
  73. for(i = 0; i < m; i++)
  74. {
  75. pC.x += x[i]; pC.y += y[i];
  76. }
  77. pC.x = pC.x / m; pC.y = pC.y / m;
  78. for(i = 0; i < m; i++)
  79. {
  80. p[i].x = x[i]; p[i].y = y[i];
  81. }
  82. // сортируем точки по возрастанию угла вокруг центра
  83. // тяжести методом вставок
  84. for(i = 1; i < m; i++)
  85. {
  86. t = p[i];
  87. for(j = i - 1; (j >= 0) && ((t - pC) < (p[j] - pC)); j--)
  88. p[j + 1] = p[j];
  89. p[j + 1] = t;
  90. }
  91. }
  92. int SPolygon::isin(Point t)
  93. {
  94. int i, parity = 0;
  95. for(i = 0; i < n; i++)
  96. if(intersect(t, p[i], p[(i + 1)%n]))
  97. parity = 1 - parity;
  98. return parity;
  99. }
  100. void SPolygon::show(double xmin, double ymin,
  101. double xmax, double ymax)
  102. {
  103. int i;
  104. int *coord = new int [2 * n];
  105. setfillstyle(SOLID_FILL, color);
  106. for(i = 0; i < n; i++)
  107. {
  108. coord[2 * i] = (p[i].x - xmin) * getmaxx() / (xmax - xmin);
  109. coord[2*i + 1] = (ymax - p[i].y) * getmaxy() / (ymax - ymin);
  110. }
  111. fillpoly(n, coord);
  112. }
  113.  
  114. class CPolygon:public SPolygon
  115. {
  116. public:
  117. int isin(Point r) {return SPolygon::isin(r);};
  118. void Insert(Point t) //добавление точки
  119. {
  120. int i; int j0, j1, j;
  121. int *del = new int [n]; //число вершин
  122. Point *q = new Point [n + 1]; //формируем многоугольник
  123. if(isin(t)) return; //t-принадлежит
  124. j0 = j1 = 0;
  125. for(i = 0; i < n; i++)
  126. {
  127. if((t - p[i]) * (p[(i + 1)%n] - p[i]) >= 0)
  128. del[i] = 1; //отмечаем видимые стороны
  129. else del[i] = 0;
  130. }
  131. for(i = 0; i < n; i++)
  132. if(del[i] == 1 && del[(i + 1)%n] == 0) break;
  133. j = 0; i = (i + 1)%n; //номер последний невидемой стороны
  134. while(del[i] == 0)
  135. {
  136. q[j++] = p[i];
  137. i = (i + 1)%n;
  138. }
  139. q[j] = p[i];
  140. q[j + 1] = t;
  141. delete []p;
  142. p = new Point [j + 2]; n = j + 2;
  143. for(i = 0; i < n; i++)
  144. p[i] = q[i];
  145. delete []q;
  146. }
  147. CPolygon(double *x, double *y, int m, int cl);
  148. };
  149.  
  150. CPolygon::CPolygon(double *x, double *y, int m, int cl):SPolygon(cl)
  151. {
  152. // выпуклая оболочка методом дейкстры
  153. int i; Point t; p = new Point [3]; n = 3;
  154. for(i = 0; i < 3; i++)
  155. {
  156. p[i].x = x[i]; p[i].y = y[i];
  157. }
  158. if((p[1] - p[0]) * (p[2] - p[1]) < 0)
  159. {
  160. t = p[1]; p[1] = p[2]; p[2] = t;
  161. }
  162. for(i = 3; i < m; i++)
  163. {
  164. t.x = x[i]; t.y = y[i];
  165. Insert(t);
  166. }
  167. }
  168.  
  169. int main()
  170. {
  171. double rad = 150; //радиус окружности и вершины семиугольника
  172. int i, mm = 7;
  173. double *x, *y;
  174. x = new double [2 * mm]; y = new double [2 * mm];
  175.  
  176. for(i = 0; i < mm; i++)
  177. {
  178. // вершины большого семиугольника
  179. x[i] = rad * cos(2 * PI * i / mm);
  180. y[i] = rad * sin(2 * PI * i / mm);
  181. // вершины маленького семиугольника
  182. x[i + mm] = rad * cos(2 * PI * i / mm + PI / mm) / 2;
  183. y[i + mm] = rad * sin(2 * PI * i / mm + PI / mm) / 2;
  184. }
  185. randomize();
  186. for(i = 0; i < 2 * mm; i++)
  187. x[i] += random(100) - 50;
  188.  
  189. CPolygon dom2(x, y, 2 * mm, BLACK); // построение выпуклой
  190. // оболочки
  191. SPolygon dom3(x, y, 2 * mm, LIGHTRED);// построение звездчатого
  192. // полигона
  193.  
  194. int gm, gd = DETECT;
  195. initgraph(&gd, &gm, "..\\bgi"); // инициализация графики
  196.  
  197. setfillstyle(SOLID_FILL, WHITE); // фон - белый
  198.  
  199. bar(0, 0, getmaxx(), getmaxy()); // закраска экрана
  200.  
  201. dom2.show(-300, -300, 300, 300); // вывод выпуклой оболочки
  202. dom3.show(-300, -300, 300, 300); // вывод звездчатого полигона
  203. getch();
  204. closegraph();
  205. return 0;
  206. }
При использовании обязательна ссылка на http://DMTSoft.ru
up

Комментарии для "Построение выпуклой оболочки методом Дейкстры и звёздчатого многоугольника на Си(C++)"


Пользователь: arhangel14
Сообщений: 10
Статус: Пользователь
Зарегистрирован:
14 октября 2008, 3:19
Был:15 января 2009, 20:15
arhangel14
smsup
Дата: 14 октября 2008, 3:57 Сообщение № 1
плз пришлите полный алгоритм на мэйл(arhangel-timur@mail.ru)
sm
Пользователь: DMT
Сообщений: 123
Статус: Программист
Зарегистрирован:
18 октября 2007, 2:35
Был:31 мая, 23:33
DMT
smsup
Дата: 22 октября 2008, 19:53 Сообщение № 2
Исходник отправлен!! Спасибо за помощь проекту!!
Пользователь: arhangel14
Сообщений: 10
Статус: Пользователь
Зарегистрирован:
14 октября 2008, 3:19
Был:15 января 2009, 20:15
arhangel14
smsup
Дата: 22 октября 2008, 22:41 Сообщение № 3
Спасибо вам!))