메뉴 건너뛰기

프로그래밍


[TIP]Convex Hull 알고리즘

파이팅건맨 2000.10.10 00:34 조회 수 : 442

Convex Hull 알고리즘 예제 소스
#include<float.h> #include<stdlib.h> #include<math.h> #include<stdio.h> #define TRUE 1 #define FALSE 0 #define MAX_ANGLE 2*M_PI int maxx, maxy; int angle(int dx, int dy) { int q; int a; if (dx == 0 && dy == 0) return 0; if (dy == 0){ if (dx > 0) return 0; else return 10000; } if (dx == 0){ if (dy > 0) return 5000; else return 15000; } if (dx > 0){ if (dy > 0) q = 0; else q = 3; } else{ if (dy > 0) q = 1; else q = 2; } if ((long)dx*dy > 0) a = (double)dy*dy*5000.0 / ((double)dx*dx + (double)dy*dy) + 0.5; else a = 5000 - (double)dy*dy*5000.0 / ((double)dx*dx + (double)dy*dy) + 0.5; return 5000*q + a; } int jarvis_march(int p[], int n) { int i, j, t, mindex=0, m = 0; double min, a, r; min = p[mindex*2+1]; for (i = 1; i < n; i++){ if (min > p[i*2+1]){ min = p[i*2+1]; mindex = i; } } t = p[0]; p[0] = p[mindex*2]; p[mindex*2] = t; t = p[1]; p[1] = p[mindex*2+1]; p[mindex*2+1] = t; m++; for (i = 1; i < n; i++){ min = angle(p[i*2]-p[i*2-2], p[i*2+1]-p[i*2-1]); mindex = i; for (j = i+1; j < n; j++){ a = angle(p[j*2]-p[i*2-2], p[j*2+1]-p[i*2-1]); if (min > a){ min = a; mindex = j; } } if (p[mindex*2+1] - p[i*2-1] < 0) break; t = p[i*2]; p[i*2] = p[mindex*2]; p[mindex*2] = t; t = p[i*2+1]; p[i*2+1] = p[mindex*2+1]; p[mindex*2+1] = t; m++; } for (; i < n; i++){ min = angle(p[i*2-2]-p[i*2], p[i*2-1]-p[i*2+1]); mindex = i; for (j = i+1; j < n; j++){ a = angle(p[i*2-2]-p[j*2], p[i*2-1]-p[j*2+1]); if (min > a){ min = a; mindex = j; } } r = angle(p[i*2-2]-p[0], p[i*2-1]-p[1]); if (min > r) break; m++; t = p[i*2]; p[i*2] = p[mindex*2]; p[mindex*2] = t; t = p[i*2+1]; p[i*2+1] = p[mindex*2+1]; p[mindex*2+1] = t; } return m; } void convex_hull() { int i = 0, p[100], cn; FILE *fp; fp=fopen("cvdata.dta","r"); if(fp == NULL){ printf("File Not Exist.\n"); return FALSE; } printf("Read Data______________________________\n\n"); while(!feof(fp)){ fscanf(fp,"%d %d\n",&p[i*2], &p[i*2+1]); printf("%d, %d\n",p[i*2],p[i*2+1]); i++; } printf("\n______________________Data Count = %3d\n\n", i); cn = jarvis_march(p, i); for (i = 0; i < cn-1; i++){ printf("[%5d, %5d]\t-\t[%5d, %5d]\n",p[i*2], p[i*2+1], p[i*2+2], p[i*2+3]); } printf("\n______________________Line Count = %3d\n", cn); fclose(fp); } void main(void) { convex_hull(); }

이 게시물이  
AiRPAGE가  
번호 제목 글쓴이 날짜 조회 수
공지 [TIP] PYTHON 에서 "UnicodeDecodeError: 'cp949' codec can't decode byte 0xe2 in position 6987: illegal multibyte sequence" 오류 날때... [52] 파이팅건맨 2016.02.20 236135
공지 [펌] ARM GCC Inline Assembler Cookbook 파이팅건맨 2006.08.18 43355
공지 [TIP] R에서 페이스북 페이지 정보 크롤링 하기 [6] 파이팅건맨 2017.02.11 25842
66 HTTP프로토콜을 이용한 파일 업로드 파이팅건맨 2002.12.24 3043
65 [Tip] CTRL-ALT-DEL키 막는법(NT,2000,XP,98) 파이팅건맨 2002.07.11 539
64 [Tip]Default 스크린세이버 가동 방법 파이팅건맨 2002.07.11 343
63 TCHAR, UNICODE, 그리고 윈도우 NT 파이팅건맨 2002.02.26 492
62 [C]밀리초를 구현하는 방법 파이팅건맨 2001.08.07 981
» [TIP]Convex Hull 알고리즘 파이팅건맨 2000.10.10 442
60 Lex와 Yacc의 사용법 강좌 파이팅건맨 2000.10.09 672
59 [C,ASM]어셈으로 윈도우메세지박스 띄우기 파이팅건맨 2000.08.16 442
58 [C소스]간단한 Hash 구현 파이팅건맨 2000.04.20 705
57 [C소스]사칙연산 파싱(Parsing) 파이팅건맨 2000.04.18 1081
56 [C소스]화일처리관련소스 파이팅건맨 2000.04.06 243
55 [구현]병렬처리기법의 개념 파이팅건맨 2000.03.11 913
54 [ASM&C]Inline ASM- PC Speaker연주. 파이팅건맨 1999.12.13 313
53 [VC소스]Font정보를 이용한 텍스트핑퐁 파이팅건맨 1999.12.12 292
52 [ASM]PC-Speaker연주 파이팅건맨 1999.11.28 262
51 [ASM]4칙연산 계산기 소스 파이팅건맨 1999.11.22 1167
50 [VC소스]이미지 파일 저장 루틴(기초) 파이팅건맨 1999.11.18 415
49 [VC소스]VIEW에 낙서하기 파이팅건맨 1999.11.12 692
48 [C++소스]가중치구하기? 파이팅건맨 1999.10.28 1503
47 [VC소스]윈도우 모양을 마음데로... 파이팅건맨 1999.10.26 502
위로