polygon triangulation

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]);
            int area3 = CCW(C,A,P[i]);
   
            if (area1 > 0){
            	if ((area2 > 0) && (area3 > 0))
                		noPointInTriangle = FALSE;
			}
            if (area1 < 0){//ABC-->CW-order
            	if ((area2 < 0) && (area3 < 0))
                	noPointInTriangle = FALSE;
			}
		}
        i++;
	}
    return !noPointInTriangle; 
}
 
BOOL IsEar(POINT P[], int Type[], int N, POINT* A, POINT *B, POINT *C){
	//삼각형 ABC가 주어진 폴리곤P의 Ear일 조건을 만족하면 참을 반환;
	//원래의 폴리곤이 convex이면 모든 vertex가 ear일 조건을 만족하나,
	//폴리곤이 concave인 경우에는 몇몇의 vertex는 Ear가 안된다. Ear가 되기
	//위해서는 폴리곤의 다른점들이 삼각형 내부에 포함이 되어서는 안된다.
	//여기서 한점이 삼각형의 내부에 포함되는가의 문제가 생기는데, 이것은
	//CCW를 써서 해결할수 있다.
	If (TriangleContainsPoint(P,Type,N,*A,*B,*C)){
    	return FALSE;
	}else {
     	return TRUE;  
	}
}
 
void PolygonTriangulation(POINT P[], int N) {
	if(N<4) return ;
 
	int *Type=new int [N];
    int i=0;
    SetPointType(P,Type,N);
    while ((i < N) &&(N>3)) {
		if(Type[i]==CONVEX){//necessary condiftion that vertex is ear;
        	int iprev=(i-1+N)%N, inext=(i+1)%N;
 
        	if(IsEar(P,Type,N, &P[iprev], &P[i], &P[inext]){
        		Push_Segment(P[iprev],P[index]);
            	//cutting ear and reconstruct polygon;
            	for(int k=i; k<N-1; k++)
	            	P[k]=P[k+1];                       
 
				//reset point type;
				SetPointType(P,Type,N-1);
				//실제로는 (i)-직전의 convexity만 재조사하면 된다.
				i=-1; N--;
			}
		}
		i++;
	}
   	delete[] Type;
}

See also:
1).O(n log(n)) 복잡도를 갖는 polygon triangulation algorithm;
==>'Fast Polygon Triangulation based on Seidel's Algorithm'.
==>http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
2).Poly2Tri 홈페이지:
==>Fast and Robust Simple Polygon Triangulation With/Without Holes by Sweep Line Algorithm
==>http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html