주어진 점집합에서 세점을 뽑아서 이들이 이루는 삼각형의 외접원에 다른 점이 하나도 포함하지 않으면  triangulation의 기본삼각형 cell이 된다. nC3개의 주어진 점의 combination에 의해서 생성이 되는 삼각형을 나머지 점들에 대해서 incircle 테스트를 수행하기 떄문에 n^4의 스텝이 필요하게 된다.

/*brute force attack*/
foreach point p1
      foreach point p2
             foreach point p3
                   foreach point p4
                          if(incircle(p1,p2,p3,p4))
                                 iscell=false;
                                 break ;
                   endfor;
                   if(iscell)
                           add(triangle(p1,p2,p3));
              endfor;
       endfor;
endfor;

세점에 의해서 형성이 되는 원은 대수적으로 쉽게 구할 수 있다. 여기서는 좀더 기하학적인 접근을 쓰면, 주어진 평면상의 점들을
   (x, y)-->(x, y, x^2 + y^2);

의 매핑에 의해서 3차원의 파라볼로이드상의 점으로 옮길 수 있다. 파라볼로이드 상의 세점에 의해서 만들어지는 평면과 파라볼로이드 면이 만나는 곡선을 x-y  평면상으로 프로젝션하면 원이 된다는 것을 쉽게 알 수 있다.(incircle 포스팅 참조). 따라서 평면상에서 세점에 의해서 만들어진 원에 주어진 점이 포함된는가를 테스트하는것은 파라볼로이드 위의 점으로 변환했을 때((x, y)-> (x, y, x^2 + y^2)), 변환된 파라볼로이드 위의 세점이 만드는 평면에 주어진 점(파라볼로이드로 변환됨)이 포함된는가만 보면 된다. 

원의 내부점이면 파라볼로이드로 변환된 점은 평면의 아래에 놓이고, 원의 외부점이면 평면의 위에 놓이게 된다. 물론 원 상의 점은 평면에 놓인다. 따라서 평면의 수직벡터 구하고, 삼각형의 한 꼭지점을 기준한 주어진 점의 변위벡터와 내적을 구하면 내적의 값은 평면 위인지 아래인지 또는 평면상에 놓인 점인가에 따라서 부호가 달라진다. 평면의 수직벡터를 고정하면(예제는 아래방향: nz < 0), 평면위에 놓인 점과의 내적은 음수, 평면아래에 놓인 점과의 내적은 양수가 되고, 평면 상의 점과의 내적은 0이다. 

주어진 세점이 만드는 외심원 내부(and 경계)에 들어가는 점이 없으면 이 삼각형을 선택한다.


** 참고 : Computational Geometry in C(2nd Edition) by Joseph O'Rourke

// input  x[0], x[1],....,x[n-1],
// input  y[0], y[1],....,y[n-1];
// calculate z[0]=x[0]^2+y[0]^2, z[1]=x[1]^2+y[1]^2,...;
int dt4(int n, double x[], double y[]) {
    double *z = new double [n] ;
    for(int ii = 0; ii < n; ii++)
        z[ii] = x[ii] * x[ii] + y[ii] * y[ii] ;

    int ntri = 0;
    /* For each triple (i,j,k) */
    for (int i = 0; i < n - 2; i++ )
        for (int j = i + 1; j < n; j++ )
            for (int k = i + 1; k < n; k++ )
                if ( j != k ) {
                    /* Compute normal to triangle (i,j,k)::  outter_product(j-i, k-i)*/
                    double nx = (y[j]-y[i])*(z[k]-z[i]) - (y[k]-y[i])*(z[j]-z[i]);
                    double ny = (x[k]-x[i])*(z[j]-z[i]) - (x[j]-x[i])*(z[k]-z[i]);
                    double nz = (x[j]-x[i])*(y[k]-y[i]) - (x[k]-x[i])*(y[j]-y[i]);
                   
                    /* Only examine faces on bottom of paraboloid: nz < 0. */
                    int flag = (nz < 0);
                    if (flag) {
                        /* For each other point m */
                        for (int m = 0; m < n; m++) {
                            /* Check if m above (i,j,k)::i점을 기준으로 m 과 
                            ** normal 간의 내적으로 체크(내적이 양수이면
                            ** m이 원의 내부에 완전히 들어 있는 경우가 된다. 
                            ** 0인 경우는 원주상에 놓인 경우이므로 배제한다
                            */
                            flag &= ((x[m]-x[i])*nx +  (y[m]-y[i])*ny + (z[m]-z[i])*nz <= 0);
                        }
                    }
                    if (flag) {
                        ntri++;
                        // (i, j, k)가 만드는 원은 다른 점을 포함하지 않으므로 이 삼각형은 한 면을 형성하게 된다.
                        // addTriangle(tri(i, j, k));
                    }
                }
    delete[]  z ;
    return ntri;
}

사용자 삽입 이미지

'Computational Geometry' 카테고리의 다른 글

Wu's Line Algorithm  (1) 2008.06.02
삼각형 외접원의 Inclusion Test  (0) 2008.05.29
Brute Force Triangulation  (0) 2008.05.28
Polygon Triangulation (II)  (0) 2008.05.26
Polygon Triangulation  (4) 2008.05.25
Polygon Fill  (0) 2008.05.22
Posted by helloktk