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(); }
#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(); }