728x90

단순 다각형(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);*/
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);  // contains vertex indices;
    // 주어진 단순폴리곤을 반시계방향으로 정렬;
    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");
            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' 카테고리의 다른 글

Wu's Line Algorithm  (1) 2008.06.02
Brute Force Triangulation  (1) 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

댓글을 달아 주세요

728x90

코드 제거: 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
 

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

Brute Force Triangulation  (1) 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
Triangulating Monotone Polygon  (0) 2008.05.22
Posted by helloktk

댓글을 달아 주세요

  1. 이상민 2008.05.26 12:55  댓글주소  수정/삭제  댓글쓰기

    잘 보았습니다. 이 분야로 졸업논문을 쓰고 있는데 많은 도움이 되었습니다.

  2. 이동기 2009.02.05 16:27  댓글주소  수정/삭제  댓글쓰기

    좋은글 공유해주셔서 감사합니다 잘 보고있습니다^^

    그런데 궁금한게 있습니다.

    이 알고리즘이 시계방향으로 그릴때와 반시계방향으로 그릴때 결과가 다르게 나오나요??

    저만 그런건지;;; 아니면 원래 그런건지 궁금해서요;;

    아. 그리고 마지막 점은 첫번째 점하고 같아야 하나요?

  3. helloktk 2009.02.07 00:09  댓글주소  수정/삭제  댓글쓰기

    코드에서 comment했듯이 위의 코드는 반시계방향의 입력에 대해서만 제대로 작동합니다(CCW 함수를 그렇게 만들었습니다.--> 물론 윈도우 그래픽은 y-방향이 위-아래가 우리가 보통 쓰는 좌표와 반대로 되어 있으므로 윈도우 그래픽상으로는 시계방향으로 나타났니다). 코드를 좀 수정하면 시계방향의 입력 폴리곤은 항상 다시 반시계방향으로 순서를 뒤집어서 만들수 있습니다.


    처음점과 마지막 점은 같지 않습니다. 같은 점(중복점)이 있으면 문제가 발생할 수 있습니다-->이것도 사전에 제거 되어야 합니다.

    제대로 할려면

    1. 입력 폴리곤의 중복점 제거
    2. 입력 폴리곤이 시계방향인지 반시계방향인지를 먼저 체크.
    3. 시계방향이면 점의 배열의 순서를 역으로 함.
    4. ear-clipping 알고리즘 적용

    이런 프로시져를 만들어야 합니다.

  4. YJ 2009.09.29 14:23  댓글주소  수정/삭제  댓글쓰기

    좋은 글 감사합니다. 제 작업에 많은 도움이 되었습니다.