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



Построение выпуклой оболочки

Выпуклая оболочка Hull Polar angle Полярный угол

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

#1 admin

admin

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

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

Отправлено 28 Март 2013 - 21:09

Создайте Win32 проект с именем "Hull" и замените текст шаблона на приведенный.
Замените в тексте "IDM_about" на "IDM_ABOUT" (к сожалению здесь он заменяется автозаменой)

Posted Image

Программа находит верхнюю левую точку из множества, для неё угол отрезка считается равным нулю, затем циклично проверяет полярный угол между данной точкой и остальными, выбирается точка с минимальным положительным углом, точка помечается как вошедшая в оболочку и далее не проверяется.
Найденный угол сохраняется для последующих сравнений.
Далее, для последующих точек, находится разница между полярным углом между текущей точкой и всеми оставшимися и предыдущим углом, находится точка с минимальной положительной разницей.
Алгоритм завершается по достижении начальной точки.


// hull.cpp
//

#include "stdafx.h"
#include "hull.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_HULL, szWindowClass, MAX_LOADSTRING);
MyRegisterClass(hInstance);

if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}

hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_HULL));

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_HULL));
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName = MAKEINTRESOURCE(IDC_HULL);
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;
}

ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);

return TRUE;
}

double polar(int x1, int y1, int x2, int y2)
{
double pi; __asm { fldpi } __asm { fstp qword ptr pi }

// move points to the center of coordinates
double x = x2 - x1;
double y = y2 - y1;

if( x == 0 )
{
if ( y == 0 ) return 0;
if ( y > 0 )
return pi / 2;
else
return 3*pi / 2;
}

if( x < 0 ) return atan(y/x) + pi;

if( x > 0 )
{
double angle = atan(y/x);
if( y >= 0 )
return angle;
else
return angle + 2*pi;
}

return -1;
}

void draw_hull(HDC hdc, POINT * points, int count)
{
int *obr;
obr = (int*)malloc(sizeof(int)*count);
memset(obr,0,sizeof(int)*count);

// draw points
for(int i=0; i<count;i++)
{
SetPixel(hdc, points[i].x, points[i].y, RGB(255,0,0));
Ellipse(hdc,points[i].x-3, points[i].y-3,points[i].x+3, points[i].y+3);
}

double pi; __asm { fldpi } __asm { fstp qword ptr pi }

// find left-top point
int num = 0, tmp_i = points[0].y;
for(int i=1; i<count;i++) if( points[i].y < tmp_i ) { tmp_i = points[i].y; num = i; }
for(int i=0; i<count;i++) if( points[i].y == tmp_i && points[i].x < points[num].x) num = i;
double angle, min = 0, diff_angle, prev_angle = 0, tmp_angle;

int current = num, firstpoint = num;
MoveToEx(hdc,points[current].x,points[current].y,NULL);
do
{
min = 2*pi;
for( int i=0; i < count; i++ )
{
if(current != i && obr[i] == 0 )
{
angle = polar(points[current].x,points[current].y,points[i].x,points[i].y);
diff_angle = angle - prev_angle;
if( diff_angle < min && diff_angle >= 0 )
{
min = diff_angle;
tmp_angle = angle;
num = i;
}
}
}
LineTo(hdc,points[num].x,points[num].y);
prev_angle = tmp_angle;
current = num;
obr[num] = 1;
} while( current != firstpoint );


free(obr);
}

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);
/////// --------------------------------------------
{
RECT rect;
srand((unsigned int)time(NULL));
rand();

GetClientRect(hWnd,&rect);

#define NUMP 20 // number of points
POINT points [NUMP];
// generate random points
for(int i = 0; i < NUMP; i++)
{
points[i].x = rand() % (rect.right - 20) + 10;
points[i].y = rand() % (rect.bottom - 20) + 10;
}

draw_hull(hdc, points, NUMP);

}
/////// --------------------------------------------

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;
}

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

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






Темы с аналогичным тегами Выпуклая оболочка, Hull, Polar angle, Полярный угол

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

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

Рейтинг@Mail.ru