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

주어진 폴리곤이 시계방향으로 정렬된 경우는 반시계 방향으로 바꾸어서 정렬시킨 후 작업을 한다. 구현된 알고리즘의 복잡도는 ${\cal O}(N^2)$이다. 

last update: 2012.10.03;

static bool leftSide(CPoint *P, CPoint *A, CPoint *B) ;
더보기
static bool leftSide(CPoint *P, CPoint *A, CPoint *B) {
    // P가 선분(A,B)의 왼쪽 또는 위에 있는가?
    return ((B->x - A->x) * (P->y - A->y) - ( B->y - A->y) * (P->x - A->x)) >=0;
}
static bool insideTriangle (CPoint *P, CPoint *A, CPoint *B, CPoint *C) ;
더보기
static bool insideTriangle (CPoint *P, CPoint *A, CPoint *B, CPoint *C) {    
    // 반시계방향으로 정렬된 삼각형(A,B,C)의 안에 점 P가 있는가?(경계포함);
    if (!leftSide(P, A, B)) return false;
    if (!leftSide(P, B, C)) return false;
    if (!leftSide(P, C, A)) return false;
    return true;
};​
static bool earTest(int a, int b, int c, int nv, int *V, CPoint *points) ;
더보기
static bool earTest(int a, int b, int c, int nv, int *V, CPoint *points) {
    // Check the triangle {V[a], V[b], V[c]} is an Ear; 
    CPoint *A  = &points[V[a]]; 
    CPoint *B  = &points[V[b]]; 
    CPoint *C  = &points[V[c]]; 
    // colinear(A->B->C) or concave인가를 체크; 반시계 방향으로 정렬된 입력점이므로 왼편에
    // 있으면 concave이므로 ear가 안된다;
    if (leftSide(B, A, C)) return false; 
    // 이미 만들어진 삼각형의 꼭지점이 포함되는지 체크한다;
    for (int k = 0; k < nv; ++k) {
        if ((k == a) || (k == b) || (k == c)) continue;
        if (insideTriangle(&points[V[k]], A, B, C)) return false;
    }
    return true;
};
static double polygonArea2(std::vector<CPoint>& pts) ;
더보기
static double polygonArea2(std::vector<CPoint>& pts) {
    double area2 = 0.;
    for (int p = pts.size() - 1, q = 0; q < pts.size(); p = q++)
        area2 += pts[p].x * pts[q].y - pts[p].y * pts[q].x;
    return (area2);
}
/* Polygon should be simple(ccw or cw);*/
bool polygonTriangulation(std::vector<CPoint>& pts, std::vector<Triangle>& triplets) {
    if (pts.size() < 3) return 0;
    triplets.clear(); triplets.reserve(pts.size() - 2);
    std::vector<int> V(pts.size());  // contains vertex indices;
    // 주어진 단순폴리곤을 반시계방향으로 정렬;
    if (polygonArea2(pts) > 0)
        for (int v = pts.size(); v-- > 0;) V[v] = v;
    else 
        for (int v = pts.size(), k = 0; v-- > 0;) V[v] = k++;
    // (pts.size()-2)개 꼭지점을 차례로 제거한다. 
    // 한개의 꼭지점이 제거될때마다 삼각형이 하나씩 생긴다;
    int nv = pts.size();
    int err_detect = 2 * nv;   /* error detection */
    for (int v = nv - 1; nv > 2;  ) {
        // 단순폴리곤이 아닌 경우에 무한루프를 도는 것을 방지;
        if (0 >= (err_detect--)) {
            TRACE("triangulate::ERROR\n");
            return false;
        }
        // <u,v,w>는 연속하는 세 꼭지점의 인덱스임;
        int u = v % nv; 
        v = (u + 1) % nv;
        int w = (v + 1) % nv;
        if (earTest(u, v, w, nv, &V[0], &pts[0])) { 
            triplets.push_back(Triangle(pts[V[u]], pts[V[v]], pts[V[w]]));  
            // 꼭지점 V[v]를 제거함;
            for (int k = v, j = k + 1; j < nv;) V[k++] = V[j++];
            --nv;       
            /* resest error detection counter */
            err_detect = 2 * nv;
        }
    }
    return triplets.size() == (pts.size() - 2); // # of triangle = (# of pts-2);
};

최적화 후:

 
 
 
 
 
 
 
728x90

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

Wu's Line Algorithm  (1) 2008.06.02
Brute Force Triangulation  (1) 2008.05.28
Polygon Triangulation  (4) 2008.05.25
Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
Posted by helloktk
,

코드 제거: 2012년 9월 4일;  코드 구현: http://kipl.tistory.com/13

Polygon의 내부를 겹치지 않게 분할하는 것을 polygon의 삼각화라고 한다. N개의 꼭짓점이 있는 polygon의 경우에 N-2개의 서로 겹치지 않은 삼각형을 내부에 가지게 되며, polygon의 경계와 겹치지 않는  N-3개의 내부 경계 라인을(diagonal)을 가지게 된다. 

사용자 삽입 이미지


분할된 삼각형의 외접원 반지름에 편차가 심한 경우 삼각형의 면적이 균일하게 분할되지 않는다. 이런 경우 인접하는 두 개의 삼각형으로 형성된 사변형에서 현재의 대각 변에 교차되는 대각 변으로 재분할을 시도한다. 이렇게 새로이 만든 삼각형을 검사하여 이전보다 면적이 균일하면 이 분할을 사용한다. 물론 삼각형의 외접원의 반경이 작을 때는 거의 균일한 분할을 얻을 수 있다. Polygon Optimizing을 참고하기 바란다.

*simple 폴리곤이 아닌 경우는 아래의 링크를 참조하기 바란다.

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

 

 

triangulation notes: (몇 개의 사이트는 없어졌다).
Nice lecture notes:
http://arachne.ics.uci.edu/~eppstein/junkyard/godfried.toussaint.html
▶ Narkhede & Manocha's description/code of Seidel's alg:
http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
▶ Some school project notes w/ triangulation overview & diagrams:
http://www.mema.ucl.ac.be/~wu/FSA2716-2002/project.html
▶ Toussaint paper about sleeve-following, including interesting
description & opinion on various other algorithms:
http://citeseer.ist.psu.edu/toussaint91efficient.html
▶ Toussaint outline & links:
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html
http://geometryalgorithms.com/algorithms.htm
▶ History Of Triangulation Algorithms
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Thierry/thierry507webprj/complexity.html
▶ Ear Cutting For Simple Polygons
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian//cutting_ears.html
▶ Intersections for a set of 2D segments
http://geometryalgorithms.com/Archive/algorithm_0108/algorithm_0108.htm
▶ Simple Polygon Triangulation
http://cgafaq.info/wiki/Simple_Polygon_Triangulation
▶ KKT O(n log log n) algo
http://portal.acm.org/citation.cfm?id=150693&dl=ACM&coll=portal&CFID=11111111&CFTOKEN=2222222
▶ Poly2Tri implemenation, good notes and looks like good code, sadly the
license is non-commercial only:(최근에 사이트가 존재하지 않음)
http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html
▶ FIST
http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html
▶ Nice slides on monotone subdivision & triangulation:
http://www.cs.ucsb.edu/~suri/cs235/Triangulation.pdf

▶ Interesting forum post re monotone subdivision in Amanith:
http://www.amanith.org/forum/viewtopic.php?pid=43
 

728x90

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

Brute Force Triangulation  (1) 2008.05.28
Polygon Triangulation (II)  (0) 2008.05.26
Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
Triangulating Monotone Polygon  (0) 2008.05.22
Posted by helloktk
,