"-//W3C//DTD HTML 4.01 Transitional//EN\" \"http://www.w3.org/TR/html4/loose.dtd\"><html><head><title>D:\\DreamFactory\\poly2.cpp.html</title><meta name=\"Generator\" content=\"Vim/7.1\"><meta http-equiv=\"content-type\" content=\"text/html; charset=KS_C_5601-1987\"></head><body bgcolor=\"#000000\" text=\"#cccccc\">  1 #include <string.h>
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4
  5 #define MIN(x,y) ( x > y ? y : x )
  6 #define MAX(x,y) ( x > y ? x : y )
  7
  8
  9 struct point
 10 {
 11     double x,y;
 12 };
 13
 14 struct line
 15 {
 16     point a,b;
 17 };
 18
 19 point* SplitPoint(char* szPoly,int& cnt);
 20 bool InsidePolyCheck(point* poly, int polycnt, double x, double y);
 21 int Direction (point A, point B, point C);
 22 bool CrossCheck(line l1,line l2);
 23 bool check(char* szPoly, double x, double y);
 24
 25 int main(void)
 26 {
 27 //  clock_t before;
 28 //  before = clock();
 29     char szPoly[]="10,10|10,70|30,70|30,30|50,30|50,70|70,70|70,10|";
 30     
 31     if(check(szPoly,11,50))
 32         printf("내부\\n");
 33     else
 34         printf("외부\\n");
 35     system("pause");
 36     return 0;
 37 }
 38 bool check(char* szPoly, double x, double y)
 39 {
 40     int cnt;
 41     bool IsInside=false;
 42     point* arrPoly;
 43     arrPoly=SplitPoint(szPoly, cnt);
 44     
 45
 46     if(InsidePolyCheck(arrPoly, cnt, x, y))
 47         IsInside=true;
 48     else
 49         IsInside=false;
 50     delete [] arrPoly;
 51     return IsInside;
 52 }
 53
 54
 55 point* SplitPoint(char* szPoly,int& cnt)
 56 {
 57     char* pPoly=szPoly;
 58     char dem[]=",|";
 59     cnt=0;
 60
 61     while(*pPoly)
 62     {
 63         if(*pPoly==\',\')
 64             cnt++;          
 65         pPoly++;
 66     }
 67 //  printf("cnt = %d\\n",cnt);
 68     pPoly=strtok(szPoly,dem);
 69
 70     point* arrPoly=arrPoly=new point[cnt];
 71     cnt=0;
 72     while(pPoly!=NULL)
 73     {      
 74         arrPoly[cnt].x=atof(pPoly);
 75         pPoly=strtok(NULL,dem);
 76         
 77         arrPoly[cnt].y=atof(pPoly);
 78         pPoly=strtok(NULL,dem);
 79         cnt++;
 80     }  
 81     return arrPoly;    
 82 }
 83
 84
 85 bool InsidePolyCheck(point* poly, int polycnt, double x, double y)
 86 {
 87     double fareast=0;
 88     int i;
 89     int CrossCnt=0;
 90     for(int i=0; i<polycnt;i++)
 91     {
 92         if(poly[i].x>fareast)             // 최외각 좌표를 구함. (폴리곤 외부의 점을 추출)
 93             fareast=poly[i].x;
 94     }
 95     point orign1 = { x , y };
 96     point orign2 = { fareast+1, y };
 97     line orign = {orign1,orign2};           // 체크할 라인.
 98     for(i=0; i<polycnt-1;i++)
 99     {
100         line ln={poly[i],poly[i+1]};
101         try
102         {
103             if(CrossCheck(ln,orign))
104                 CrossCnt++;
105         }
106         catch (int* dir)
107         {
108 //          printf("익셉션\\n");
109             return true;        
110         }      
111     }
112     
113     line ln={poly[i],poly[0]};             // 마지막 점과 첫 점.
114     try
115     {
116         if(CrossCheck(ln,orign))
117             CrossCnt++;
118     }
119     catch (int* dir)
120     {
121         return true;
122     }
123
124     if(CrossCnt%2)                         // 홀수면 내부 짝수면 외부
125         return true;
126     else
127         return false;
128 }
129
130
131 bool CrossCheck(line l1,line l2) // 선분 교차 체크
132 {
133     if((MIN(l1.a.x,l1.b.x) > l2.a.x) && (MIN(l1.a.x,l1.b.x) > l2.b.x)) // 둘다 작으면
134         return false;    
135     if((MIN(l1.a.y,l1.b.y) > l2.a.y) && (MIN(l1.a.y,l1.b.y) > l2.b.y))
136         return false;    
137     if((MAX(l1.a.x,l1.b.x) < l2.a.x) && (MAX(l1.a.x,l1.b.x) < l2.b.x)) // 둘다 크면
138         return false;    
139     if((MAX(l1.a.y,l1.b.y) < l2.a.y) && (MAX(l1.a.y,l1.b.y) < l2.b.y))
140         return false;    
141
142     /* 입력: l1, l2 : 교차상태를검사할두선분
143     출력: l1, l2가서로교차하면TRUE, 아니면FALSE. */
144     if(    (Direction(l1.a, l1.b, l2.a) * Direction(l1.a, l1.b, l2.b) <= 0) &&
145         (Direction(l2.a, l2.b, l1.a) * Direction(l2.a, l2.b, l1.b) <= 0))
146         return true;
147     return false;
148 }
149
150 int Direction (point A, point B, point C) {
151     /* 입력: A,B, C : 세점의좌표  /    출력: Dir */
152     double dxAB, dxAC, dyAB, dyAC;
153     dxAB = B.x - A.x;
154     dyAB = B.y - A.y;
155     dxAC = C.x - A.x;
156     dyAC = C.y - A.y;
157     int Dir=0;
158
159     if((dxAB * dyAC) < (dyAB * dxAC)) /* 시계방향*/
160         Dir = 1;
161     if((dxAB * dyAC) > (dyAB * dxAC)) /* 반시계*/
162         Dir = -1;
163     if((dxAB * dyAC) == (dyAB * dxAC)) /* 일직선*/
164     {
165         if((dxAB == 0) && (dyAB == 0))
166             Dir = 0;
167         else if(((dxAB*dxAC)<0) || ((dyAB*dyAC)<0))
168             Dir = -1;
169         else if((dxAB*dxAB + dyAB*dyAB)>=(dxAC*dxAC + dyAC*dyAC)) // <- 요놈이 접점. //Dir = 0;          
170             throw &Dir;
171         else 
172             Dir = 1;
173     }
174     return Dir;
175 }
</body></html>