728x90

// 수퍼 삼각형은 입력 점집합을 모두 포함하도록 충분히 큰 삼각형을 선택한다;
// 삼각화한 후 최외각이 convex가 아니면 수퍼 삼각형을 더 크게 다시 잡아야 함.
// 마지막 수정: 2021.4.7, 코드 간결화;
#define REMOVE_FLAG    (-1)
//
// max num of triangles = 2 * (N - 2) - 1;
// max num of edegs     = 3 * (N - 2);
int inc_delaunay_triangulation(POINT P[], int N, TRIANGLE *V) {
    // 메모리는 입력 점집합의 크기가 (N+3)인 경우를 기준으로 할당되어야 한다;
    int emax = 3 * (N + 1) ;
    EDGE *E = (EDGE *)malloc(sizeof(EDGE) * emax) ;
    set_supertriangle(P, N) ;
    // First element of triangle index is supertriangle vertex;
    push_tri(&V[0], N, N + 1, N + 2);
    int nt = 1;
    for (int i = 0; i < N; i++) {
        int ne = 0;
        /* 추가점(P[i])를 외접원에 포함시키는 삼각형을 모두 찾아 제거한다.
        ** 이들 삼각형의 공유되는 내부 edge를 제외한 나머지 외부 edge와
        ** 추가점으로 새로운 삼각형을 만들어 리스트에 추가한다.
        */ 
        for (int j = 0; j < nt; j++) {
            TRIANGLE *t = &V[j];
            if (incircle(P[t->a], P[t->b], P[t->c], P[i])) {
                // 제거되는 삼각형의 edge는 백업한다; 내부 edge는 중복된다.
                push_edge(&E[ne++], t->a, t->b);
                push_edge(&E[ne++], t->b, t->c);
                push_edge(&E[ne++], t->c, t->a);
                // P[i]를 포함하는 외접원 삼각형은 제거;
                // swap(j, nt-1) to remove triangle at j
                V[j--] = V[--nt];  
            }
        }
        // 중복되어 있는 내부 edge를 제거;
        remove_double_edges(E, ne);
        
        // 외부 edge와 P[i]가 만드는 새 삼각형을 리스트에 추가;
        for (int j = 0; j < ne; j++) {
            if (is_removed_edge(&E[j])) continue;
            push_tri(&V[nt++], E[j].a, E[j].b, i);
        }
    }
    //done with super_triangle;
    free(E);
    return remove_supertriangle_relics(N, V, nt) ;
}
void remove_double_edges(EDGE *E, int ne) {
    for (int j = 0; j < ne - 1; j++)
    	for (int k = j + 1; k < ne; k++)
            if (is_double_edge(&E[j], &E[k])) {
            	pop_edge(&E[j]); pop_edge(&E[k]);
            }
}
void push_tri(TRIANGLE *V, int a, int b, int c) {
    V->a = a; V->b = b; V->c = c;
}
int is_removed_edge(const EDGE *E) {
    return (E->a == REMOVE_FLAG || E->b == REMOVE_FLAG);
};
int is_double_edge(const EDGE* E1, const EDGE* E2) {
    return ((E1->a == E2->a && E1->b == E2->b) ||
            (E1->a == E2->b && E1->b == E2->a)) ;
}
void push_edge(EDGE *E, int a, int b) {
    E->a = a; E->b = b;
}
void pop_edge(EDGE* E) {
    E->a = E->b = REMOVE_FLAG;
}

// 삼각형 중에서 수퍼 삼각형의 꼭지점(N,N+1,N+2)을 가지고 있는 것을 제거;
int remove_supertriangle_relics(int N, TRIANGLE *V, int nt) {
    for (int i = 0; i < nt; i++)
        if (V[i].a >= N || V[i].b >= N || V[i].c >= N)
            // swap(i, nt - 1) to remove triangle at j
            V[i--] = V[--nt];
    return nt;
}

// A,B,C가 만드는 외접원에 D가 들어가는가?;
int incircle(POINT A, POINT B, POINT C, POINT D) {
	POINT AD = A - D, BD = B - D, CD = C - D;
    double ccw = CCW(A, B, C);
    double det = norm2(AD) * cross(BD, CD)
               + norm2(BD) * cross(CD, AD)
               + norm2(CD) * cross(AD, BD)
    if (ccw > 0) return det > 0; //CCW인 경우에..
    else         return det < 0; //CW인  경우에..    
}

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

삼각형 외접원의 Inclusion Test  (0) 2020.12.30
Point in Polygon  (2) 2020.12.14
Incremental Delaunay Triangulation  (1) 2020.12.01
Chain Hull  (2) 2012.09.16
Quick Hull  (2) 2012.09.16
Monotone Cubic Interpolation  (0) 2012.09.09
Posted by helloktk

댓글을 달아 주세요

  1. hgmhc 2020.12.02 20:40 신고  댓글주소  수정/삭제  댓글쓰기

    그 개어렵다는 델로네 삼각분할이군요...
    나중에 배울때 참고하겠습니다^^