helloktk의 블로그 | ㅇ http://blog.naver.com/helloktk/80026219095 폴리곤의 내부를 겹치지 않게 분할하는 것을 폴리곤의 삼각화라고 한다. N개의 꼭지점이 있는 폴리곤의 경우에 N-2개의 서로 겹치지 않은 삼각형을 내부에 가지게 되며, 폴리곤의 경계와 겹치지 않는 N-3개의 내부 경계라인을(diagonal)을 가지게 된다. /*Ear-cutting algorithm: not optimized, only for simple polygon, no hole **and counter clockwise ordered ploygon */ // is vertex convex or concave relative to it neighborhood??; void SetPointType(POINT P[], int Type[], int N) { for(int i=0; i<N; i++) { int iprev=(i-1+N) %N ; int inext=(i+1)%N; if(CCW(P[iprev],P[i],P[inext])>0){ Type[i]=CONVEX ; }else{ Type[i]=CONCAVE; } } }; BOOL TriangleContainsPoint(POINT P[], int TYpe[], int N, POINT A, POINT B,POINT C){ BOOL noPointInTriangle=TRUE; int i=0; while ((i < N) && (noPointInTriangle)) { if ((Type[i] ==CONCAVE)&&((A != P[i]) || (B != P[i]) ||(C != P[i]))){ int area1 = CCW(A,B,P[i]); int area2 = CCW(B,C,P[i]...