기본 콘텐츠로 건너뛰기

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

댓글

이 블로그의 인기 게시물

80040154 오류로 인해 CLSID가 {xxxx-...}인 구성 요소의 COM 클래스 팩터리를 검색하지 못했습니다.

원문보기 .NET 으로 만든 응용프로그램에서 com 객체를 호출한 경우 Windows7 64bit 에서 제목과 같은 에러가 발생했다. Win32 COM 과 .NET 프로그램간의 호환성 때문에 생긴 문제였다. 원인은 .NET 실행시 JIT 컴파일러에 의해 최적화된 기계어로 변환되기 때문.. Win32 COM은 컴파일시.. Win32 COM에 맞춰 빌드 속성에서 하위버전으로 맞춰 컴파일을 다시하는 방법도 있지만 메인 프로젝트가 .NET이라면 참조되는 모든 프로젝트를 다 바꿔야할 노릇.. 또 다른 방법은 COM+를 이용하여 독립적으로 만드는 것이다. 분리시키는 방법은 아래 주소해서 확인할 수 있다. http://support.microsoft.com/kb/281335 나의 경우는 Win32 COM DLL을 64비트 .NET 프로그램에서 참조하니 COM 객체를 제대로 호출하지 못하였습니다. 그래서 .NET 프로그램의 Target Machine을 x86으로 설정하니 제대로 COM 객체를 호출하였습니다.

[Pyinstaller] 실행 파일 관리자 권한 획득하기

고객사에서 일부 사용자에게서 프로그램 오류가 발생한다며 아래와 같이 에러 캡처를 보내왔습니다. 프로그램에서 로그를 남기기 위해 로그 파일을 생성하는데 권한의 문제로 로그 파일을 생성하지 못해 프로그램 오류가 발생한 것 같습니다. 처음에는 Python 코드에서 관리자 권한을 요청하는 코드를 넣으려고 했는데, 실제로 Stackoverflow를 찾아보면 이런 내용이 나옵니다. 프로그램이 관리자 권한으로 실행되지 않았다면 관리자 권한으로 다시 프로그램을 실행시키는 코드입니다. import os import sys import win32com.shell.shell as shell ASADMIN = 'asadmin' if sys.argv[-1] != ASADMIN: script = os.path.abspath(sys.argv[0]) params = ' '.join([script] + sys.argv[1:] + [ASADMIN]) shell.ShellExecuteEx(lpVerb='runas', lpFile=sys.executable, lpParameters=params) sys.exit(0) 하지만 개인적으로 이런 방식은 마음에 들지 않았고 조금 더 찾아보니 Pyinstaller로 exe 파일을 만들 때 옵션을 설정하여 관리자 권한을 요청하도록 할 수 있다고 합니다. --uac-admin을 옵션에 추가하면 프로그램 실행 시 관리자 권한을 요청할 수 있습니다. pyinstaller.exe --uac-admin sample.py 하지만 안타깝게도 이 방식은 원하는 대로 동작하지 않았습니다. 마지막으로 manifest 파일을 이용하여 시도해보았습니다. spec 파일을 이용하여 pyinstaller로 빌드하면 <실행 파일 이름>.manifest 라는 파일이 생성됩니다. 파일에서 아랫부분을 찾아볼 수 있습니다. <security> <re

초간단 프로그램 락 걸기

프로그램에 락을 걸 일이 생겨났다. 하드웨어 락을 걸면 쉬울텐데 그 정도는 아니고 프로그램의 실행 날짜를 제한 해 달라고 한다. 그래서 파일(license.lic)을 가지고 락을 걸리고 결정을 했다. 요구 사항은 아래와 같다. 1. license.lic 파일이 없으면 프로그램을 실행 할수 없게 한다. 2. 지정한 날짜를 넘어서는 프로그램을 실행 할수 없게 한다. 3. 사용자가 시스템 날짜를 되돌렸을때 인식하여 프로그램을 실행 할수 없게 한다. 음.... 1.번 문제는 사용자가 프로그램을 실행하기 위해서 license.lic 파일을 받아야만 한다. license.lic 파일에는 최근 실행 날짜/종료날짜 이런식으로 적도록 한다.(물론 내용은 암호화 한다.) 최근 실행날짜는 프로그램이 실행때마다 업데이트 하도록 하고 시스템 날짜와 비교하여 시스템 날짜가 최근 실행 날짜보다 이전의 날짜면 시스템 날짜를 되돌렸다고 인식하도록 한다.(3.번 문제 해결) 시스템 날짜와 종료 날짜를 비교하여 시스템 날짜가 종료 날짜를 넘으면 프로그램을 실행 할수 없도록 한다.(2.번 문제 해결)