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



Триангуляция Делоне

Триангуляция Делоне Полярный угол

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

#1 admin

admin

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

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

Отправлено 29 Март 2013 - 19:22

Изображение

Создайте Win32 проект с названием "delone" и замените текст на приведенный, затем
замените IDM_about на IDM_ABOUT (заменился автозаменой здесь)

Данная программа испольует метод противолежащих углов

Цитата

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)*(y1*x2 - x1*y2) <= 0
где из каждой координаты вычтены координаты проверяемой точки x0,y0

Приведенный пример требует дальнейшей оптимизации.

Триангуляция строится внутри выпуклой оболочки.

// delone.cpp
//
#include "stdafx.h"
#include "delone.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_DELONE, szWindowClass, MAX_LOADSTRING);
MyRegisterClass(hInstance);
if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}
hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_DELONE));
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_DELONE));
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName = MAKEINTRESOURCE(IDC_DELONE);
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;
}

struct rebro
{
int p1;
int p2;
short int fl;
struct rebro * next;
};
int rcount = 0;
struct rebro * first = NULL;
void createlist()
{
first = NULL;
rcount = 0;
}
void inslast(struct rebro * current)
{
struct rebro * ins = new(struct rebro);
memcpy(ins,current,sizeof(struct rebro));
if( first == NULL)
{
first = ins;
first->next = first;
}
else
{
struct rebro * cursor = first;
while(cursor->next != first) cursor = cursor->next;
cursor->next = ins;
ins->next = first;
}
rcount++;
}
void clearlist()
{
if( first == NULL) return;
struct rebro *cursor = first, *cursor2;
while(cursor->next != first) {
cursor2 = cursor->next;
delete cursor;
cursor = cursor2;
}
first = NULL;
rcount = 0;
}
struct rebro * get_elem(int n)
{
if(rcount == 0 || n > rcount) return NULL;
struct rebro * cursor = first;
for(int i=1; i <= n; i++) cursor = cursor->next;
return cursor;
}

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 triangle(HDC hdc, POINT * points, int count)
{
// вначале строим выпуклую оболочку
int *obr;
obr = (int*)malloc(sizeof(int)*count);
memset(obr,0,sizeof(int)*count);
struct rebro * toadd;
double pi; __asm { fldpi } __asm { fstp qword ptr pi }
createlist();
// 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;
do
{
	 min = 2*pi;
	 num = -1;
	 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;
	 }
	 }
	 }
	 if( num == -1 ) break;
	 // add ребро
	 toadd = new(struct rebro);
	 toadd->p1 = current;
	 toadd->p2 = num;
	 toadd->fl = 1; // у данного отрезка может быть только один треугольник
	 inslast(toadd);
	 delete toadd;
	 //
	 prev_angle = tmp_angle;
	 current = num;
	 obr[num] = 1;
} while( current != firstpoint );
free(obr);
// выпуклая оболочка построена
// далее проходимся по отрезкам, пока есть свободные точки точки или отрезки с fl = 1
// проверяем условие Делоне с помощью проверки суммы противолежащих углов
rebro *tmp, *tmp2, *tmp3;
current = 0;
while(current < rcount)
{
tmp = get_elem(current);
if(tmp->fl != 2)
{
	 for(int i=0; i < count; i++)
	 {// get point
	 if(i == tmp->p1 || i == tmp->p2 ) continue;
	 // проверка условия делоне
	 int x1 = points[tmp->p1].x, x2 = points[tmp->p2].x, x3 = points[i].x;
	 int y1 = points[tmp->p1].y, y2 = points[tmp->p2].y, y3 = points[i].y;
	 bool bad_triangle = false;
	 double xc,yc,x01,y01,x02,y02,x03,y03;
	 double radius;
	 for(int k = 0; k < count; k++)
	 {
	 if(k != tmp->p1 && k != tmp->p2 && k != i )
	 {
	 int x0 = points[k].x, y0 = points[k].y;
	 x01 = x1 - x0; y01 = y1 - y0;
	 x02 = x2 - x0; y02 = y2 - y0;
	 x03 = x3 - x0; y03 = y3 - y0;
	 if((x01*x01 + y01*y01)*(y02*x03 - x02*y03)
		 + (x02*x02 + y02*y02)*(x01*y03 - y01*x03)
		 + (x03*x03 + y03*y03)*(y01*x02 - x01*y02) <= 0 )
	 {
		 bad_triangle = true;
		 break;
	 }
	 }
	 }
	 if(!bad_triangle)
	 {
	 bool found1 = false;
	 bool found2 = false;
	 for(int j=0;j<rcount;j++)
	 {
	 tmp2 = get_elem(j);
	 if((tmp2->p1 == tmp->p1 && tmp2->p2 == i || tmp2->p1 == i && tmp2->p2 == tmp->p1))
	 {
		 if( tmp2->fl < 2 )
		 tmp2->fl++;
		 found1 = true;
	 }
	 if((tmp2->p1 == tmp->p2 && tmp2->p2 == i || tmp2->p1 == i && tmp2->p2 == tmp->p2))
	 {
		 if( tmp2->fl < 2 )
		 tmp2->fl++;
		 found2 = true;
	 }
	 }
	 if(!found1)
	 {
	 toadd = new(struct rebro);
	 toadd->p1 = tmp->p1;
	 toadd->p2 = i;
	 toadd->fl = 1; // у данного отрезка может быть только один треугольник
	 inslast(toadd);
	 delete toadd;
	 }
	 if(!found2)
	 {
	 toadd = new(struct rebro);
	 toadd->p1 = i;
	 toadd->p2 = tmp->p2;
	 toadd->fl = 1; // у данного отрезка может быть только один треугольник
	 inslast(toadd);
	 delete toadd;
	 }
	 if( tmp->fl < 2 ) tmp->fl++;
	 }
	 }
}
current++;
}

// 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);
}
// вывод полученных отрезков
for(int i=0; i < rcount; i++)
{
tmp = get_elem(i);
if(tmp != NULL)
{
	 //Sleep(100);
	 MoveToEx(hdc,points[tmp->p1].x,points[tmp->p1].y,NULL);
	 LineTo(hdc,points[tmp->p2].x,points[tmp->p2].y);
}
}
clearlist();
}
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 50 // 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;
}
triangle(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;
}






Темы с аналогичным тегами Триангуляция, Делоне, Полярный угол

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

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

Рейтинг@Mail.ru