알고리즘(Algorithm) 실습12

Posted by Patchman
2010.02.15 15:46 Univ Study/알고리즘과 실습


 

12-1. 다음에 주어진 프로그램을 참고해서 주어진 자료에 대한 컨벡스 헐(Convex Hull)을 결정하여 출력하는 프로그램을 완성하고 실습하시오. 또한, N(>20)개의 점을 randon() 함수로 발생하고, 이점들에 대한 컨벡스 헐(Convex Hull)을 구하고, 이 과정에서 실행한 2 점 사이의 수평각 계산 회수와 각의 비교회수 및 Convex Hull 내부 점 수를 count 해서 출력하시오. 단, 수평각들을 sort하는 알고리즘은 임의로 선택하고, x와 y좌표값은 100보다 작게 한다.

 

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

 

#define Nmax 30

 

// 점(point) 구조체

struct point

{

int x;

int y;

char c;

};

 

 

class Polygon

{

private :

 

int computeCount; // 수평각 계산 회수

int compareCount; // 각의 비교 회수

int innerDot; // 볼록껍질 내부 점의 개수

int wrapped_count; // 볼록껍질의 꼭지점 수

 

public :

 

Polygon(struct point *poly, int N);// Polygon 생성자

void printPoly(struct point *poly, int N); // 점들의 좌표 출력

float ComputeAngle(struct point p1, struct point p2); // 수평각 계산

int PointWrapping(struct point P[], int n); // 볼록껍질 구하기(짐꾸리기 알고리즘)

void Polygon::Swap(struct point *a, struct point *b); // Swap 함수

};

 

 

 

 

Polygon::Polygon(struct point *poly, int N)

{

wrapped_count=0; computeCount=0; compareCount=0; innerDot=0;

 

cout<<"-----------------------------------------\n\n";

cout << "\n주어진 점들의 좌표\n";

 

printPoly(poly, N-1); // 점들의 초기값

 

// 리턴된 볼록껍질의 꼭지점 수를 wrapped_count에 저장

wrapped_count = PointWrapping(poly, N);

 

cout << "\n점 집합의 볼록 껍질\n";

printPoly(poly, wrapped_count-1); // PointWrapping에서 구성된 점집합을 출력

 

// 마지막 인덱스에 복사된 볼록껍질의 첫번째 점을 출력해서 연결시킨다.

cout << " -> " << poly[N].c << "[" << poly[N].x << "," << poly[N].y << "]" << "\n";

 

// Convex Hull 내부의 점의 개수(전체 점의 개수 - wrapping된 점의 개수)

innerDot = N - wrapped_count;

 

// 연산 카운터 출력

cout << "수평각 계산 회수 : " << computeCount;

cout << "각의 비교 회수 : " << compareCount;

cout << "Convex Hull 내부 점의 수 : " << innerDot ;

cout<<"------------------------------------------\n\n";

}

 

// 점들의 좌표 출력 함수

void Polygon::printPoly(struct point *poly, int N)

{

for(int i=0; i<N; i++)

{

cout << poly[i].c << "[" << poly[i].x << "," << poly[i].y << "]" << " -> ";

}

cout << poly[N].c << "[" << poly[N].x << "," << poly[N].y << "]";

}

 

// 수평각 계산 함수

float Polygon::ComputeAngle(struct point p1, struct point p2)

{

int dx, dy, ax, ay;

double t;

 

computeCount++; // 수평각 계산회수 카운터 증가

 

dx = p2.x - p1.x; ax = abs(dx);

dy = p2.y - p1.y; ay = abs(dy);

 

t = (ax+ay == 0) ? 0 : (float)dy/(ax+ay);

 

if(dx < 0) t=2-t; else if(dy<0) t=4+t;

return (float)t*90.0;

}

 

// 볼록껍질 구하기(짐꾸리기 알고리즘)

int Polygon::PointWrapping(struct point P[], int n)

{

int i, NumVertex;

float MinAngle, MaxAngle, Angle;

int FirstPoint, NextPoint;

 

FirstPoint=0;

 

// 기준점 찾기(Y가 최소인 점)

for(i=1; i<n; i++) if(P[i].y < P[FirstPoint].y) FirstPoint=i;

 

NumVertex=-1;

 

P[n]= P[FirstPoint]; // 첫번째 꼭지점 복사본 저장

 

MaxAngle=0.0;

NextPoint=FirstPoint;

 

// 다음 꼭지점을 찾는 루프, 다음꼭지점을 배열의 왼쪽으로 밀어둠

do{

 

NumVertex++;

Swap(&P[NumVertex], &P[NextPoint]);

NextPoint=n;

MinAngle=MaxAngle;

MaxAngle=360.0;

 

for(i = NumVertex+1; i <= n; i++)

{

Angle = ComputeAngle(P[NumVertex], P[i]);

 

// 직전에 구한 각 보다 크면서 최소인 각을 찾는다.

if(Angle > MinAngle && Angle < MaxAngle)

{

compareCount++; // 비교연산 카운터 증가

NextPoint=i;

MaxAngle = Angle;

}

}

}while(NextPoint != n);

 

// 볼록껍질의 꼭지점 수를 리턴한다.

// 현재 프로그램에서 출력부분과, 내부점의 계산을 위해

// 꼭지점 수에 1을 더한값을 리턴한다.

return NumVertex+1;

}

 

// PointWrapping 에서 데이터 교환에 사용하는 함수

void Polygon::Swap(struct point *a, struct point *b)

{

struct point temp[1];

 

temp[0].c = a->c;

temp[0].x = a->x;

temp[0].y = a->y;

 

a->c = b->c;

a->x = b->x;

a->y = b->y;

 

b->c = temp[0].c;

b->x = temp[0].x;

b->y = temp[0].y;

}

 

 

void main()

{

//주어진 값으로 점의 위치 초기화

struct point poly1[] = { 3, 4, 'A',

1, 2, 'B',

2, 5, 'C',

2, 6, 'D',

9, 3, 'E',

5, 3, 'F',

6, 4, 'G',

8, 4, 'H',

-1, -1, '-' };

 

 

 

cout<<"[ 주어진 자료 ]";

Polygon POLY1(poly1, 8);

 

struct point *poly2;

 

poly2 = new struct point[Nmax]; // Nmax 의 개수 만큼 point 생성

 

srand((int)time(NULL));

 

for(int i=0; i<=Nmax; i++)

{

poly2[i].x = rand()%100;

poly2[i].y = rand()%100;

poly2[i].c = i-1 + 'A';

}

 

poly2[Nmax].x = -1; poly2[Nmax].y = -1; // Nmax번 자리 초기화

 

cout<<"\n\n[ Random" << "(" << Nmax << ") ]\n";

Polygon POLY2(poly2, Nmax);

}

 

 

 

 

  ▣ 결과 출력

 

   

 

'Univ Study > 알고리즘과 실습' 카테고리의 다른 글

알고리즘(Algorithm) 실습12  (0) 2010.02.15
알고리즘(Algorithm) 실습11  (0) 2010.02.15
알고리즘(Algorithm) 실습10  (0) 2010.02.15
알고리즘(Algorithm) 실습8  (0) 2010.02.15
알고리즘(Algorithm) 실습7  (0) 2010.02.15
알고리즘(Algorithm) 실습6  (0) 2010.02.15