단순폴리곤의 삼각화 알고리즘의 다른 구현이다. 이전 구현과 같은 Ear-Clipping  알고리즘을 써서 구현한 것이다. 폴리곤의 각 꼭지점을 돌면서 현재 꼭지점의 직전과 직후의 꼭지점들로 만들어지는 삼각형이 Ear인가를 체크해서 Ear이면 삼각형을 하나를 얻고, 현재의 꼭지점은 주어진 폴리곤에서 제거를 한 후에 테스트를 계속 진행한다. nv 개의 꼭지점을 가지는 단순폴리곤의 경우에 nv-2 개의 삼각형으로 분해가 된다. 

알고리즘은 주어진 폴리곤이 시계방향인 경우에는 반시계방향으로 수정하여서 작업을 한다. 구현된 알고리즘의 복잡도는 O(N^2)이다. 

last update: 2012.10.03;

static bool leftSide(CPoint *P, CPoint *A, CPoint *B) {
static bool insideTriangle (CPoint *P, CPoint *A, CPoint *B, CPoint *C) {
static bool earTest(int a, int b, int c, int nv, int *V, CPoint *points) {
static double polygonArea2(std::vector<CPoint>& pts) {
/* Polygon should be simple(ccw or cw);*;
int polygonTriangulation(std::vector<CPoint>& points, std::vector<Triangle>& triplets) {
    int nv = points.size();
    if (nv < 3) return 0;
    triplets.clear();
    triplets.reserve(nv - 2);
    std::vector<int> V(nv) ;
    // 주어진 단순폴리곤을 반시계방향으로 정렬한다;
    if (polygonArea2(points) > 0)
        for (int v = 0; v < nv; ++v) V[v] = v;
    else 
        for (int v = 0; v < nv; ++v) V[v] = nv - 1 - v;
    // nv-2개의 꼭지점을 차례로 제거한다. 한개의 꼭지점이 제거될때마다 삼각형이 하나씩
    // 생긴다;
    int err_detect = 2*nv;   /* error detection */
    for (int v = nv - 1; nv > 2;  ) {
        // 단순폴리곤이 아닌 경우에 무한루프를 도는 것을 방지;
        if (0 >= (err_detect--)) {
            TRACE("triangulate::ERROR\n");
            triplets.clear();
            return 0;
        }
        // <u,v,w>는 연속하는 세꼭지점의 인덱스임;
        int u = v % nv;
        v = (u + 1) % nv;
        int w = (v + 1) % nv;
        if (earTest(u, v, w, nv, &V[0], &points[0])) { 
            triplets.push_back(Triangle(points[V[u]], points[V[v]], points[V[w]]));  
            // 꼭지점 V[v]를 제거함;
            for (int k = v; k < nv - 1; ++k)
                V[k] = V[k + 1];
            --nv;       
            /* resest error detection counter */
            err_detect = 2*nv;
        }
    }
    return triplets.size();
    //number of triangle = (nv-2);
}


최적화 후:





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

삼각형 외접원의 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
Fortune's Sweep Algorithm  (0) 2008.05.22
Posted by helloktk

댓글을 달아 주세요