Построение выпуклого многоугольника методом заворачивания подарка + определить принадлежность точки построенному многоугольник. Язык программирования Си - VC++.


Добавил:DMT
Дата создания:1 мая 2008, 17:41
Дата обновления:1 мая 2008, 17:41
Просмотров:9211 последний позавчера, 1:23
Комментариев: 0
Определить базовый класс «множество точек», породить от него класс «многоугольник», а от класса «многоугольник» породить класс «выпуклый многоугольник», конструктор которого строит выпуклую оболочку методом заворачивания подарка.
Написать программу, которая позволяет вводить множество точек, по которым строится выпуклый многоугольник, и определять принадлежность выбранной точки построенному многоугольнику.

Текст программы
Код на C++
  1.  
  2. //Модуль «stdafx.h»:
  3.  
  4. #pragma once
  5.  
  6. #define WIN32_LEAN_AND_MEAN
  7. #include <windows.h>
  8. #include <stdlib.h>
  9. #include <malloc.h>
  10. #include <memory.h>
  11. #include <tchar.h>
  12. #include <math.h>
  13.  
  14. Модуль «CPoint.h»:
  15.  
  16. #ifndef CPOINT_H
  17. #define CPOINT_H
  18.  
  19. #include "stdafx.h"
  20.  
  21. class CPoint
  22. {
  23. private:
  24. float x, y;
  25. public:
  26. CPoint();
  27. CPoint(float _x, float _y);
  28. float operator[](int n);
  29. CPoint operator-(CPoint& p);
  30. float operator*(CPoint& p);
  31. void SetX(float _x);
  32. void SetY(float _y);
  33. void SetXY(float _x, float _y);
  34. float GetX();
  35. float GetY();
  36. };
  37.  
  38. #endif
  39.  
  40. //Модуль «CPoint.cpp»:
  41.  
  42. #include "CPoint.h"
  43.  
  44. CPoint::CPoint() : x(0), y(0) {};
  45. CPoint::CPoint(float _x, float _y) : x(_x), y(_y) {};
  46. float CPoint::operator [](int n)
  47. {
  48. switch (n)
  49. {
  50. case 0:
  51. return x;
  52. case 1:
  53. return y;
  54. default:
  55. return 0;
  56. }
  57. }
  58. CPoint CPoint::operator-(CPoint& p)
  59. {
  60. CPoint np;
  61. np.SetXY(x - p.GetX(), y - p.GetY());
  62. return np;
  63. }
  64. float CPoint::operator*(CPoint& p)
  65. {
  66. return x * p.GetX() + y * p.GetY();
  67. }
  68. float CPoint::GetX()
  69. {
  70. return x;
  71. }
  72. float CPoint::GetY()
  73. {
  74. return y;
  75. }
  76. void CPoint::SetX(float _x)
  77. {
  78. x = _x;
  79. }
  80. void CPoint::SetY(float _y)
  81. {
  82. y = _y;
  83. }
  84. void CPoint::SetXY(float _x, float _y)
  85. {
  86. x = _x;
  87. y = _y;
  88. }
  89.  
  90. //Модуль «CPoints.h»:
  91.  
  92. #ifndef CPOINTS_H
  93. #define CPOINTS_H
  94.  
  95. #include "CPoint.h"
  96.  
  97. class CPoints
  98. {
  99. protected:
  100. CPoint *points;
  101. int n;
  102. public:
  103. CPoints();
  104. CPoints(int _n);
  105. CPoints(CPoint **p, int _n);
  106. virtual ~CPoints();
  107. CPoint* operator[](int ind);
  108. int Count();
  109. };
  110.  
  111. #endif
  112.  
  113. //Модуль «CPoints.cpp»:
  114.  
  115. #include "CPoints.h"
  116.  
  117. CPoints::CPoints() : n(0) {};
  118. CPoints::CPoints(int _n) : n(_n)
  119. {
  120. points = new CPoint[n];
  121. }
  122. CPoints::CPoints(CPoint **p, int _n) : n(_n)
  123. {
  124. points = new CPoint[n];
  125. for (int i = 0; i < n; i++)
  126. points[i].SetXY(p[i]->GetX(), p[i]->GetY());
  127. }
  128. CPoints::~CPoints()
  129. {
  130. delete[] points;
  131. }
  132. CPoint* CPoints::operator [](int ind)
  133. {
  134. return &points[ind];
  135. }
  136. int CPoints::Count()
  137. {
  138. return n;
  139. }
  140.  
  141. //Модуль «CPolygon.h»:
  142.  
  143. #ifndef CPOLYGON_H
  144. #define CPOLYGON_H
  145.  
  146. #include "CPoints.h"
  147.  
  148. class CPolygon : public CPoints
  149. {
  150. private:
  151. void Line(HDC hDC, int x0, int y0, int x1, int y1);
  152. public:
  153. CPolygon();
  154. CPolygon(CPoints &p);
  155. void Show(HDC hDC);
  156. };
  157.  
  158. #endif
  159.  
  160. //Модуль «CPolygon.cpp»:
  161.  
  162. #include "CPolygon.h"
  163.  
  164. CPolygon::CPolygon() { n = 0; }
  165. CPolygon::CPolygon(CPoints &p)
  166. {
  167. n = p.Count();
  168. points = new CPoint[n];
  169. for (int i = 0; i < n; i++)
  170. points[i].SetXY(p[i]->GetX(), p[i]->GetY());
  171. }
  172. void CPolygon::Line(HDC hDC, int x0, int y0, int x1, int y1)
  173. {
  174. MoveToEx(hDC, x0, y0, NULL);
  175. LineTo(hDC, x1, y1);
  176. }
  177. void CPolygon::Show(HDC hDC)
  178. {
  179. for (int i = 1; i < n; i++)
  180. Line(
  181. hDC,
  182. points[i - 1].GetX(),
  183. points[i - 1].GetY(),
  184. points[i].GetX(),
  185. points[i].GetY()
  186. );
  187. Line(
  188. hDC,
  189. points[0].GetX(),
  190. points[0].GetY(),
  191. points[n - 1].GetX(),
  192. points[n - 1].GetY()
  193. );
  194. }
  195.  
  196. //Модуль «CPPolygon.h»:
  197.  
  198. #include "CPolygon.h"
  199.  
  200. class CPPolygon : public CPolygon
  201. {
  202. public:
  203. CPPolygon();
  204. CPPolygon(CPolygon &p);
  205. };
  206.  
  207. //Модуль «CPPolygon.cpp»:
  208.  
  209. #include "CPPolygon.h"
  210. #include <math.h>
  211.  
  212. CPPolygon::CPPolygon() { n = 0; }
  213. CPPolygon::CPPolygon(CPolygon &p)
  214. {
  215. if ( p.Count() <= 0 ) return;
  216. // Поиск первой точки ( минимум по Y )
  217. int k = 0;
  218. for ( int i = p.Count(); --i > 0; )
  219. {
  220. if ( p[k]->GetY() > p[i]->GetY() ) k = i;
  221. else
  222. if ( p[k]->GetY() == p[i]->GetY() && p[k]->GetX() < p[i]->GetX() ) k = i;
  223. }
  224. // Если она не первая в массиве, то сделаем обмен
  225. if ( k )
  226. {
  227. CPoint v = *p[k];
  228. *p[k] = *p[0];
  229. *p[0] = v;
  230. }
  231. // Поиск остальных точек (обход против часовой стрелки)
  232. CPoint w(1, 0);
  233. int l = 0;
  234. double c = -2., q = 0.;
  235. for(;;)
  236. {
  237. int k = 0;
  238. if ( l > 0 )
  239. {
  240. CPoint v = *p[0] - *p[l];
  241. q = v.GetX() * v.GetX() + v.GetY() * v.GetY();
  242. c = w * v;
  243. c *= fabs(c) / q;
  244. }
  245. for ( i = l+1; i < p.Count(); ++i )
  246. {
  247. CPoint v = *p[i] - *p[l];
  248. double tq = v.GetX() * v.GetX() + v.GetY() * v.GetY();
  249. if ( tq > 0 )
  250. {
  251. double tc = w * v;
  252. tc *= fabs(tc) / tq;
  253. if ( c < tc ) c = tc, q = tq, k = i;
  254. else
  255. if ( c == tc && q < tq ) q = tq, k = i;
  256. }
  257. }
  258. if ( k == 0 ) break;
  259. ++l;
  260. if ( k != l )
  261. {
  262. CPoint v = *p[k];
  263. *p[k] = *p[l];
  264. *p[l] = v;
  265. }
  266. w = *p[l] - *p[l-1];
  267. }
  268. n = l + 1;
  269. points = new CPoint[n];
  270. for (int i = 0; i < n; i++)
  271. (points[i]).SetXY(p[i]->GetX(), p[i]->GetY());
  272. }
  273.  
  274. //Модуль «OOP5.cpp»:
  275.  
  276. #include "stdafx.h"
  277. #include "resource.h"
  278. #include "globals.h"
  279. #define MAX_LOADSTRING 100
  280.  
  281. CPoint *Points[MAXPOINTS];
  282. int PointsCount = 0;
  283. bool IsInput = true;
  284. bool IsSelPoint = false;
  285. CPPolygon *poly;
  286.  
  287. HDC hdcComp;
  288. HBITMAP hBitmap;
  289.  
  290. // Global Variables:
  291. HINSTANCE hInst; // current instance
  292. TCHAR szTitle[MAX_LOADSTRING]; // The title bar text
  293. TCHAR szWindowClass[MAX_LOADSTRING]; // the main window class name
  294.  
  295. // Forward declarations of functions included in this code module:
  296. ATOM MyRegisterClass(HINSTANCE hInstance);
  297. BOOL InitInstance(HINSTANCE, int);
  298. LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
  299. LRESULT CALLBACK About(HWND, UINT, WPARAM, LPARAM);
  300.  
  301. void FreeMem()
  302. {
  303. for (int i = 0; i < PointsCount; i++) delete Points[i];
  304. }
  305.  
  306. int APIENTRY _tWinMain(HINSTANCE hInstance,
  307. HINSTANCE hPrevInstance,
  308. LPTSTR lpCmdLine,
  309. int nCmdShow)
  310. {
  311. MSG msg;
  312. HACCEL hAccelTable;
  313.  
  314. // Initialize global strings
  315. LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
  316. LoadString(hInstance, IDC_OOP5, szWindowClass, MAX_LOADSTRING);
  317. MyRegisterClass(hInstance);
  318.  
  319. // Perform application initialization:
  320. if (!InitInstance (hInstance, nCmdShow)) return FALSE;
  321.  
  322. hAccelTable = LoadAccelerators(hInstance, (LPCTSTR)IDC_OOP5);
  323. HDC hdcScreen = CreateDC("DISPLAY", NULL, NULL, NULL);
  324. hdcComp = CreateCompatibleDC(hdcScreen);
  325. hBitmap = CreateCompatibleBitmap(hdcScreen,
  326. GetDeviceCaps(hdcScreen, HORZRES) * 2,
  327. GetDeviceCaps(hdcScreen, VERTRES) * 2);
  328. SelectObject(hdcComp, hBitmap);
  329. HPEN hOldPen, hPen = CreatePen(PS_SOLID, 3, 0);
  330. hOldPen = (HPEN)SelectObject(hdcComp, hPen);
  331.  
  332. while (GetMessage(&msg, NULL, 0, 0))
  333. {
  334. if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
  335. {
  336. TranslateMessage(&msg);
  337. DispatchMessage(&msg);
  338. }
  339. }
  340. FreeMem();
  341. SelectObject(hdcComp, hOldPen);
  342. DeleteObject(hPen);
  343. delete poly;
  344. return (int) msg.wParam;
  345. }
  346.  
  347. ATOM MyRegisterClass(HINSTANCE hInstance)
  348. {
  349. WNDCLASSEX wcex;
  350.  
  351. wcex.cbSize = sizeof(WNDCLASSEX);
  352.  
  353. wcex.style = CS_HREDRAW | CS_VREDRAW;
  354. wcex.lpfnWndProc = (WNDPROC)WndProc;
  355. wcex.cbClsExtra = 0;
  356. wcex.cbWndExtra = 0;
  357. wcex.hInstance = hInstance;
  358. wcex.hIcon = LoadIcon(hInstance, (LPCTSTR)IDI_OOP5);
  359. wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
  360. wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
  361. wcex.lpszMenuName = (LPCTSTR)IDC_OOP5;
  362. wcex.lpszClassName = szWindowClass;
  363. wcex.hIconSm = LoadIcon(wcex.hInstance, (LPCTSTR)IDI_SMALL);
  364.  
  365. return RegisterClassEx(&wcex);
  366. }
  367.  
  368. BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
  369. {
  370. HWND hWnd;
  371.  
  372. hInst = hInstance; // Store instance handle in our global variable
  373.  
  374. hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
  375. CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
  376.  
  377. if (!hWnd) return FALSE;
  378.  
  379. ShowWindow(hWnd, nCmdShow);
  380. UpdateWindow(hWnd);
  381.  
  382. return TRUE;
  383. }
  384.  
  385. LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
  386. {
  387. int wmId, wmEvent, x, y;
  388. PAINTSTRUCT ps;
  389. HDC hdc;
  390. RECT r;
  391.  
  392. switch (message)
  393. {
  394. case WM_COMMAND:
  395. wmId = LOWORD(wParam);
  396. wmEvent = HIWORD(wParam);
  397. // Parse the menu selections:
  398. switch (wmId)
  399. {
  400. case ID_POLYGON_ENDPOLY:
  401. IsInput = false;
  402. break;
  403. case ID_POLYGON_RESET:
  404. FreeMem();
  405. PointsCount = 0;
  406. IsSelPoint = false;
  407. IsInput = true;
  408. break;
  409. case ID_TEST_SELECTPOINT:
  410. IsSelPoint = true;
  411. return 0;
  412. case IDM_EXIT:
  413. PostQuitMessage(0);
  414. return 0;
  415. default:
  416. return DefWindowProc(hWnd, message, wParam, lParam);
  417. }
  418. UpdateScreen(hWnd, hdcComp);
  419. InvalidateRect(hWnd, NULL, NULL);
  420. return 0;
  421. case WM_PAINT:
  422. hdc = BeginPaint(hWnd, &ps);
  423. GetWindowRect(hWnd, &r);
  424. BitBlt(hdc, 0, 0, r.right - r.left, r.bottom - r.top, hdcComp, 0, 0, SRCCOPY);
  425. EndPaint(hWnd, &ps);
  426. return 0;
  427. case WM_SIZE:
  428. break;
  429. case WM_LBUTTONDOWN:
  430. x = LOWORD(lParam);
  431. y = HIWORD(lParam);
  432. if (IsSelPoint)
  433. if (IsIn(x, y))
  434. MessageBox(NULL, "Точка находится внутри многоугольника!", "Info", MB_OK | MB_ICONINFORMATION);
  435. else
  436. MessageBox(NULL, "Точка находится вне многоугольника!", "Info", MB_OK | MB_ICONINFORMATION);
  437. else
  438. if (IsInput && PointsCount < MAXPOINTS)
  439. Points[PointsCount++] = new CPoint(x, y);
  440. break;
  441. case WM_DESTROY:
  442. PostQuitMessage(0);
  443. break;
  444. default:
  445. return DefWindowProc(hWnd, message, wParam, lParam);
  446. }
  447. UpdateScreen(hWnd, hdcComp);
  448. InvalidateRect(hWnd, NULL, NULL);
  449. return 0;
  450. }
  451.  
  452. //Модуль «globals.h»:
  453.  
  454. #include "CPPolygon.h"
  455.  
  456. #define MAXPOINTS 20
  457.  
  458. extern CPoint *Points[MAXPOINTS];
  459. extern int PointsCount;
  460. extern bool IsInput;
  461. extern CPPolygon *poly;
  462.  
  463. extern void UpdateScreen(HWND hWnd, HDC hDC);
  464. extern bool IsIn(int x, int y);
  465.  
  466. //Модуль «globals.cpp»:
  467.  
  468. #include "stdafx.h"
  469. #include "globals.h"
  470. #include "CPolygon.h"
  471.  
  472. void DrawPolygon(HWND hWnd, HDC hdcComp)
  473. {
  474. CPoints pts(&Points[0], PointsCount);
  475. CPolygon p(pts);
  476. delete poly;
  477. poly = new CPPolygon(p);
  478. poly->Show(hdcComp);
  479. }
  480.  
  481. void UpdateScreen(HWND hWnd, HDC hDC)
  482. {
  483. int x, y;
  484. RECT r;
  485. GetWindowRect(hWnd, &r);
  486. PatBlt(hDC, 0, 0, r.right - r.left, r.bottom - r.top, PATCOPY);
  487. for (int i = 0; i < PointsCount; i++)
  488. {
  489. x = Points[i]->GetX();
  490. y = Points[i]->GetY();
  491. MoveToEx(hDC, x, y, 0);
  492. LineTo(hDC, x + 1, y);
  493. }
  494. if (!IsInput && PointsCount) DrawPolygon(hWnd, hDC);
  495. }
  496.  
  497. int sign(int n)
  498. {
  499. if (n > 0)
  500. return 1;
  501. else
  502. if (n < 0)
  503. return -1;
  504. else
  505. return 0;
  506. }
  507.  
  508. float Dis(int x0, int y0, int x1, int y1)
  509. {
  510. return sqrtf((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0));
  511. }
  512.  
  513. float Geron(int x0, int y0, int x1, int y1, int x2, int y2)
  514. {
  515. float da, db, dc, p;
  516. da = Dis(x1, y1, x2, y2);
  517. db = Dis(x0, y0, x2, y2);
  518. dc = Dis(x0, y0, x1, y1);
  519. p = (da + db + dc) / 2;
  520. return sqrtf(fabs(p * (p - da) * (p - db) * (p - dc)));
  521. }
  522.  
  523. bool IsInTriangle(int x0, int y0, int x1, int y1, int x2, int y2, int x, int y)
  524. {
  525. return !(Geron(x0, y0, x1, y1, x2, y2) * 1.0001 <
  526. Geron(x, y, x0, y0, x1, y1) +
  527. Geron(x, y, x0, y0, x2, y2) +
  528. Geron(x, y, x1, y1, x2, y2));
  529. }
  530.  
  531. bool IsIn(int x, int y)
  532. {
  533. if (IsInput) return false;
  534. for (int i = 1; i < poly->Count() - 1; i++)
  535. if (IsInTriangle(
  536. (*poly)[0]->GetX(), (*poly)[0]->GetY(),
  537. (*poly)[i]->GetX(), (*poly)[i]->GetY(),
  538. (*poly)[i + 1]->GetX(), (*poly)[i + 1]->GetY(),
  539. x, y
  540. )) return true;
  541. return false;
  542. }
При использовании обязательна ссылка на http://DMTSoft.ru
up