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


Добавил:DMT
Дата создания:1 мая 2008, 17:41
Дата обновления:1 мая 2008, 17:41
Просмотров:11111 последний вчера, 0:33
Комментариев: 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