Перейти к содержимому



Построение звёздчатого полигона

звёздчатый полигон star polygon polar angle Алгоритм Грехема

  • Авторизуйтесь для ответа в теме
В этой теме нет ответов

#1 admin

admin

    Администратор

  • Администраторы
  • 76 сообщений

Отправлено 02 Март 2013 - 20:27

Создайте в Visual Studio проект Win32 Project с названием "starpolygon"

Замените текст в созданном проекте на следующий ниже

В тексте замените  IDM_about на  IDM_ABOUT (здесь он автоматически заменился, к сожалению)

В данном примере случайным образом генерируется 20 точек (задано в константе #define NUMP 20)
Находится самая нижняя по Y точка, затем для остальных точек вычисляются полярные углы относительно данной точки и сортируются.

Для построения использован алгоритм Грехема

// starpolygon.cpp
//
#include "stdafx.h"
#include "starpolygon.h"
#include <ctime>
#include <cmath>
#define MAX_LOADSTRING 100
HINSTANCE hInst;
TCHAR szTitle[MAX_LOADSTRING];
TCHAR szWindowClass[MAX_LOADSTRING];
ATOM MyRegisterClass(HINSTANCE hInstance);
BOOL InitInstance(HINSTANCE, int);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK About(HWND, UINT, WPARAM, LPARAM);
int APIENTRY _tWinMain(HINSTANCE hInstance,
					 HINSTANCE hPrevInstance,
					 LPTSTR lpCmdLine,
					 int	 nCmdShow)
{
UNREFERENCED_PARAMETER(hPrevInstance);
UNREFERENCED_PARAMETER(lpCmdLine);
MSG msg;
HACCEL hAccelTable;
LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
LoadString(hInstance, IDC_STARPOLYGON, szWindowClass, MAX_LOADSTRING);
MyRegisterClass(hInstance);
if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}
hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_STARPOLYGON));
while (GetMessage(&msg, NULL, 0, 0))
{
if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}
return (int) msg.wParam;
}
ATOM MyRegisterClass(HINSTANCE hInstance)
{
WNDCLASSEX wcex;
wcex.cbSize = sizeof(WNDCLASSEX);
wcex.style = CS_HREDRAW | CS_VREDRAW;
wcex.lpfnWndProc = WndProc;
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance;
wcex.hIcon = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_STARPOLYGON));
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName = MAKEINTRESOURCE(IDC_STARPOLYGON);
wcex.lpszClassName = szWindowClass;
wcex.hIconSm = LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));
return RegisterClassEx(&wcex);
}
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
HWND hWnd;
hInst = hInstance;
hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
	 CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
if (!hWnd)
{
	 return FALSE;
}
/////// --------------------------------------------
srand((unsigned int)time(NULL));
rand();
/////// --------------------------------------------
ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);
return TRUE;
}
/////// --------------------------------------------
RECT rect;
#define NUMP 20 // number of points
// structure for point + polar angle
struct pnt {
POINT p;
double angle;
};
struct pnt points[NUMP];
double polar(int cx, int cy, int x, int y)
{
double pi; __asm { fldpi } __asm { fstp qword ptr pi }
int xp = abs(x - cx);
int yp = abs(y - cy);
double angle;
if( xp != 0 )
angle = atan((double)yp/xp);
else
return y >= cy ? pi / 2 : 3 * pi / 2;
if (cy > y && cx > x)
angle += pi;
else
{
if( cy > y ) angle = 2*pi - angle;
if( cx > x ) angle = pi - angle;
}
if( yp = 0 ) angle = x >= cx ? 0 : pi;
return angle;
}
int comp(const void *A, const void *B)
{
return (*(struct pnt*)A).angle > (*(struct pnt*)B).angle ? 1 : ( (*(struct pnt*)A).angle == (*(struct pnt*)B).angle ) ? 0 : -1;
}
/////// --------------------------------------------

LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
int wmId, wmEvent;
PAINTSTRUCT ps;
HDC hdc;
switch (message)
{
case WM_COMMAND:
wmId = LOWORD(wParam);
wmEvent = HIWORD(wParam);
// Разобрать выбор в меню:
switch (wmId)
{
case IDM_about:
DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
break;
case IDM_EXIT:
DestroyWindow(hWnd);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
break;
case WM_PAINT:
hdc = BeginPaint(hWnd, &ps);
/////// --------------------------------------------
{
GetClientRect(hWnd,&rect);
// generate random points
for(int i = 0; i < NUMP; i++)
{
points[i].p.x = rand() % (rect.right - 20) + 10;
points[i].p.y = rand() % (rect.bottom - 20) + 10;
SetPixel(hdc, points[i].p.x, points[i].p.y, 0);
}

// find point with max Y
int select = 0,maxy = points[0].p.y;
for(int i = 1; i < NUMP; i++)
{
	 if( points[i].p.y > maxy )
	 {
	 select = i;
	 maxy = points[i].p.y;
	 }
}
POINT tmp;
// if point witn max Y is not the first move it to the first position
if( select > 0 )
{
tmp = points[0].p;
points[0].p = points[select].p;
points[select].p = tmp;
}
// calculate polar angles between 0 & i points
points[0].angle = 0;
for(int i = 1; i < NUMP; i++)
{
points[i].angle = polar(points[0].p.x, points[0].p.y, points[i].p.x, points[i].p.y);
}
// sort points by polar angle
qsort(points,NUMP,sizeof(struct pnt),comp);
// show star plygon
MoveToEx(hdc,points[0].p.x,points[0].p.y,NULL);
for(int i = 1; i < NUMP; i++)
{
LineTo(hdc,points[i].p.x, points[i].p.y);
if(i == NUMP - 1)
{
	 LineTo(hdc,points[0].p.x, points[0].p.y);
}
}
}
/////// --------------------------------------------
EndPaint(hWnd, &ps);
break;
case WM_DESTROY:
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}
// Обработчик сообщений для окна "О программе".
INT_PTR CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
UNREFERENCED_PARAMETER(lParam);
switch (message)
{
case WM_INITDIALOG:
return (INT_PTR)TRUE;
case WM_COMMAND:
if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
{
EndDialog(hDlg, LOWORD(wParam));
return (INT_PTR)TRUE;
}
break;
}
return (INT_PTR)FALSE;
}

Прикрепленные файлы

  • Прикрепленный файл  starpolygon.rar   36,73К   55 Количество загрузок:






Темы с аналогичным тегами звёздчатый полигон, star polygon, polar angle, Алгоритм Грехема

Количество пользователей, читающих эту тему: 0

0 пользователей, 0 гостей, 0 скрытых пользователей

Рейтинг@Mail.ru