알고리즘(Algorithm) 실습12
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 |